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

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

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

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

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