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