Показатели и первообразные корни

Предположим противное, пусть По условию то есть — нечётное, а значит Делимость на равносильна сравнению Возведём его в квадрат: Далее запишем его следующим образом: После применения МТФ последнее сравнение превратится в Следовательно,

кратно Отсюда вытекают два случая.

Если первая скобка кратна то Также ранее мы выяснили, что Таким образом, зная, что если и то получаем:

Осталось заметить, что не делится на потому что по нашему предположению. Следовательно, этот НОД равен либо либо То есть либо либо но при это невозможно.

Если вторая скобка кратна то Домножим сравнение на и получим: Условие позволяет заменить в последнем сравнении на и получить следующее: Снова приходим к первой задаче, только в этом случае нужно посмотреть на и аналогичным способом убедиться, что он может быть лишь или что приводит к противоречию.