Лемма об уточнении показателя

Рассмотрим остатки степеней двойки по модулю Покажем,что двойка — первообразный корень по модулю Заметим, что делится на только если делится на (проверка остатков степеней по модулю Пусть Теперь по LTE То есть откуда и

Таким образом, двойка — действительно первообразный корень по этому модулю. Следовательно, по модулю степени двойки дают различных остатков — в точности те, что взаимно просты с (так как степень двойки не кратна пяти). Значит, существуют степени двойки, сравнимые по модулю с То есть существуют степени двойки, сравнимые по модулю с

(домножаем все предыдущие степени и их остатки на это можно сделать, поскольку и взаимно просты).

Заметим теперь, что каждый следующий остаток отличается от предыдущего не более чем на Значит, на каждом шаге -ая с конца цифра соответствующей степени двойки увеличивается не более, чем на а отсюда следует, что такими шагами мы получим на местах с по любую комбинацию цифр. Собственно, выберем степень двойки, на которой мы получили данную комбинацию — она и будет искомой, которая получается дописыванием цифр.