63
правки
Изменения
м
Нет описания правки
|id=t
|statement=
Пусть <math>g</math> - — первообразный корень по модулю <math>p</math><tex>\in\mathbb{P}</tex>. Тогда <math>g</math><sup>a</sup> - — ''первообразный корень по модулю <math>p</math> <math>\Leftrightarrow</math> НОД<math>(a;p-1)=1</math>.''<br>
|proof=
Так как g<sup>a</sup> - — первообразный корень, значит (g<sup>a</sup>)<sup>φ(p)</sup>=1, но p<tex>\in\mathbb{P}</tex>, поэтому φ(p)=p-1, значит (g<sup>a</sup>)<sup>p-1</sup>=1, и это же справедливо для g: g<sup>p-1</sup>=1. Пусть НОД(a;p-1)=k, k>1, тогда <math>1=g^{p-1}=(g^{p-1})^{\frac{a}{k}}=(g^{\frac{p-1}{k}})^a=(g^a)^{\frac{p-1}{k}}</math>. Но, по определению ord, <math>p-1</math> - — минимальная степень, в которую следует возвести <math>g^a</math>, чтобы получить единицу, а <math>\frac{p-1}{k}<p-1</math>. Получили противоречие, теорема доказана.
*Теперь докажем обратную теорему:
Пусть существует k такое, что <math>g^{a\cdot k}=1</math>, и <math>k<p-1</math>. Но <math>g^{p-1}=1</math>, значит <math>g^{a\cdot k}=g^{p-1}</math>. Следовательно либо <math>(a*k) \vdots (p-1)</math>, либо <math>(p-1) \vdots (a*k)</math>. Но по определению первообразного корня, и ord, <math>p-1 \leqslant a*k</math>, то есть <math>(a*k) \vdots (p-1)</math>, а так как НОД<math>(a; p-1)=1</math>, то <math>k \vdots (p-1) \Rightarrow p-1 \leqslant k</math>, что противоречит нашему предположению. Обратная теорема доказана.
|statement=Количество различных первообразных корней по модулю p равно φ(p-1).
|proof=
Пусть g - — первообразный корень.<br>
Во-первых, при <math>a=k*(p-1)+b \text{, }b<p-1 \colon g^a=(g^{p-1})^{k}*g^b=1\cdot g^{b}</math>. Таким образом есть смысл рассматривать только первообразные корни, образованные из исходного, путем возведения в степень не выше <math>p-1</math>.<br>
Во-вторых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов <math>\mathbb{Z}/p \mathbb{Z}</math> циклична (то есть <math>\exists a\in\mathbb{Z}/p\mathbb{Z}\colon\forall b\in\mathbb{Z}/p\mathbb{Z} \text{ } \exists k\colon a^k=b</math>).<br>
По доказанной обратной теореме <math>\forall a \colon с (a \text{; } p-1)=1 \Rightarrow g^a</math> - — первообразный корень. С другой стороны для любого другого a, по прямой теореме <math>g^a</math> не является первообразным корнем. Но по определению <math>\varphi(p-1)</math> равно количеству <math>a \colon </math> НОД <math>(a;p-1)=1</math>. Очевидно, для всех <math>a<p-1\text{, }g^a</math> различны. Теорема доказана.
}}
|proof=
Сначала разберем случай <math>p^2</math>.
Пусть <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>
}}
[[Категория: Теория чисел]]
