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

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