Изменения

Пусть <tex>g</tex> — первообразный корень по модулю <tex>p\text{, }k=ord_{p^2}(g)</tex>. Тогда <tex>g^k=1(p^2)</tex>, следовательно <tex>g^k=1(p)</tex>, и значит <tex>k\vdots (p-1)</tex>. Также заметим, что <tex>\phi(p^2)=p(p-1)\vdots k</tex>. Получаем два случая — <tex>k=p-1</tex>, и <tex>k=p(p-1)</tex>. Во втором случае получается что <tex>g</tex> — первообразный корень по модулю <tex>p^2</tex>. Теперь рассмотрим первый случай: обратим внимание на число применим предыдущие рассуждения к числу <tex>g+p</tex> (это возможно, так как <tex>g+p\equiv g (p)</tex>). <tex>(g+p)^{p-1}=g^{p-1}+c^{1}_{p-1}g^{p-2}p+...</tex> — заметим, что все слагаемые, начиная с третьего содержат множитель <tex>p^2</tex> — поэтому обнуляются по модулю <tex>p^2</tex>. <tex>g^{p-1}=1(p^2)</tex>, а <tex>c^{1}_{p-1}g^{p-2}p=p(p-1)g^{p-2}\neq 0(p^2)</tex>, значит <tex>(g+p)^{p-1}\neq 1(p^2)</tex>, и из аналогичных соображений значит число <tex>(g+p)^{p(p+1)}=1(p^2)k</tex>. Итак, мы умеем находить такое для <tex>g+p</tex>, что не может быть равно <tex>g^{p-1}\equiv1(p)</tex>, и тогда <tex>g^{+p-1}=1+u_0p(</tex> — первеобразный корень по модулю <tex>p^2)</tex>. Возводя это равенство в степень Аналогичным образом, если имеется первообразный корень по модулю <tex>p^ka</tex>, получаем отыскивается первообразный корень по модулю <tex>^{p^k(p-1)\equiv 1+u_kp^{ka+1}(p^{k+2})}</tex>.