Изменения
→Первообразные корни
|proof=
Пусть g — первообразный корень.<br>
Во-первых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов <tex>\mathbb{Z}/p \mathbb{Z}</tex> циклична (то есть <tex>\exists a\in\mathbb{Z}/p\mathbb{Z}\colon\forall b\in\mathbb{Z}/p\mathbb{Z} \text{ } \exists k\colon a^k=b</tex>).<br>Во-вторых, при <tex>a=k\cdot (p-1)+b \text{, }b<p-1 \colon g^a=(g^{p-1})^{k}\cdot g^b=1\cdot g^{b}</tex>. Таким образом есть смысл рассматривать только первообразные корни, образованные из исходного, путем возведения в степень не выше <tex>p-1</tex>.<br>Во-вторых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов <tex>\mathbb{Z}/p \mathbb{Z}</tex> циклична (то есть <tex>\exists a\in\mathbb{Z}/p\mathbb{Z}\colon\forall b\in\mathbb{Z}/p\mathbb{Z} \text{ } \exists k\colon a^k=b</tex>).<br>
По доказанной обратной теореме <tex>\forall a \colon с (a \text{; } p-1)=1 \Rightarrow g^a</tex> — первообразный корень. С другой стороны для любого другого a, по прямой теореме <tex>g^a</tex> не является первообразным корнем. Но по определению <tex>\varphi(p-1)</tex> равно количеству <tex>a \colon </tex> НОД <tex>(a;p-1)=1</tex>. Очевидно, для всех <tex>a<p-1\text{, }g^a</tex> различны. Теорема доказана.
}}
