Малая теорема Ферма

Сначала проверим, не может ли равняться или Припишем к карточке цифру если Петя сказал, что не делится, то Если же Петя сказал, что делится, повторим эту же операцию ещё раз. Если на доске было написано число делящееся на то следующим шагом будет написано число если теперь Петя опять ответит положительно, то делится на откуда иначе Абсолютно аналогично поступаем с (только приписывать будем цифру

Далее считаем, что и Обозначим все простые, меньшие кроме и через Рассмотрим

По малой теореме Ферма делится на каждое из чисел в частности на Будем приписывать справа к числу раз цифру а потом цифру Пусть на доске было записано число Тогда после всех таких операций будет написано число

То есть мы умеем уменьшать остаток числа при делении на на Рано или поздно мы получим положительный ответ. Далее опять будем уменьшать остаток на пока второй раз не получим положительный ответ. Тогда между двумя положительными ответами мы сделали ровно шагов, откуда найдем наше