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

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

Мы получили дробь, которая является целой. Покажем, что она делится на кроме некоторых случаев.

Предположим, что не делится на В этом случае достаточно доказать, что делит числитель дроби. Посмотрим на его первое слагаемое: а — это сумма всех остатков при делении на кроме и то есть она сравнима с по модулю Тогда всё слагаемое сравнимо с Докажем теперь, что кратно

Если знаменатель делится на то кратно (в этом случае не делит ), откуда и То есть либо либо (тогда ). В первом случае остаток во втором — потому что в сумме нет слагаемых. Иначе не делится на а числитель делится, так как Следовательно, при остаток

Если же делится на то то есть Этот случай уже рассмотрен.