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

Докажем индукцией по что Нетрудно убедиться, что — первообразный корень по модулю

Предположим, что утверждение верно для всех Пусть тогда кратно Ясно, что чётное, иначе не будет давать остаток при делении на То есть Заметим, что

По предположению Вторая же скобка делится на но не делится на поскольку кратно при (случаи, когда можно рассмотреть отдельно). Таким образом, степень вхождения в равна Значит, для делимости на необходимо, чтобы было не меньше Следовательно, что и требовалось.