Тайны чисел: Математическая одиссея - страница 24

Сначала математики думали, что если у 2^>p остаток от деления на p равен 2, то число p должно быть простым. Но, как оказалось, этот тест не гарантирует простоты. Так, 341 = 34 × 11 не является простым, но тем не менее остаток 2^>341 от деления на 341 равен 2. Данный пример был открыт лишь в 1819 г., и, возможно, братья-близнецы знали, что требуется более изощренный тест, который исключил бы 341. Ферма выяснил, что в тесте можно не ограничиваться степенями 2. Он доказал, что если число p – простое, то для любого числа n, меньшего p, остаток от деления n^>p на p равен n. Значит, если вы найдете какое-либо число n, для которого тест проваливается, то необходимо отбросить p как самозванца, не являющегося простым.

Например, остаток от деления 3^>341 на 341 равен не 3, а 168. Конечно, близнецы никак не могли прогонять тест, используя все числа, меньшие их кандидата на роль простого, – потребовалось бы слишком много времени. Однако, как оценил великий венгерский кудесник простых чисел Пал Эрдёш (хотя он не мог доказать это строго), шанс того, что число, меньшее 10^>150, пройдет тест Ферма один раз и не окажется простым, настолько низок, как 1 из 10^>43. Вероятно, для близнецов один прогон теста был достаточен, чтобы заявить о нахождении простого числа.

В этой игре для двух участников знание простых чисел-близнецов может дать вам преимущество.

Запишите числа от 1 до 100 либо загрузите поле для игры в классики с веб-сайта «Тайн 4исел». Первый игрок берет фишку и кладет ее на простое число, отстоящее от квадрата 1 не более чем на 5 шагов. Затем фишку берет второй игрок, он должен положить ее на большее простое число, отстоящее от предыдущего положения фишки не более чем на 5 шагов. Далее снова делает ход первый игрок, ему необходимо переместить фишку на еще большее простое число, которое удалено не более чем на 5 шагов. Проигравшим считается тот участник, который не может сделать ход по правилам. Правила таковы: 1) фишку нельзя передвигать более чем на 5 шагов; 2) ее нужно класть на простое число; 3) нельзя ходить назад либо оставаться на месте.

Рис. 1.21. Пример игры в классики с простыми числами с максимальным перемещением в 5 шагов

На рис. 1.21 показан типичный сценарий. Игрок 1 проиграл, потому что игрок 2 положил фишку на 23, а среди пяти следующих за 23 числами нет простых. Мог ли игрок 1 сделать более удачный начальный ход? Если вы приглядитесь внимательнее, то поймете, что после того, как пройдено 5, выбора уже не остается. Кто бы ни положил фишку на 5, должен в итоге оказаться победителем, так как впоследствии он сможет переместить фишку с 19 до 23, оставив оппонента без хода. Так что начальный ход имеет решающее значение.