Изменения

Пусть <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)^{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)</tex>. Итак, мы умеем находить такое <tex>g</tex>, что <tex>g^{p-1}\equiv1(p)</tex>, и <tex>g^{p-1}=1+u_0p(p^2)</tex>. Возводя это равенство в степень <tex>p^k</tex>, получаем <tex>^{p^k(p-1)\equiv 1+u_kp^{k+1}(p^{k+2})}</tex>

}}