63
правки
Изменения
→Теорема о существовании первообразных корней по модулям 2\text{, }4 \text{, }p^n \text{, }2 \cdot p^n
<br>
Но тогда <tex>g^z=1(mod~ n)</tex>. Но по определению <tex>ord_n(g)=\phi(n)</tex>, а <tex>z<\phi(n)</tex> — получили противоречие.
<br>
Осталось разобрать случай <tex>p=2^k,~ k>2</tex>. Мы докажем, что для модулей такого вида выполняется <tex>a^{\frac{\phi(2^k)}{2}}=a^{2^{k-2}}=1(mod~2^k)</tex>. Очевидно это будет означать, что таким модулям первообразных корней нет.
<br>
Доказательство построим по индукции.<br>
1) База: <tex>k=3</tex>. Легко простым перебором убедиться, что <tex>a^2\equiv 1(mod~8)</tex>.
<br>
2) Шаг индукции: пусть доказано, что <tex>a^{2^{k-2}}=1(mod~2^k)</tex>. Докажем, что <tex>a^{2^{k-1}}=1(mod~2^{k+1})</tex>. Рассмотрим это сравнение:
<br>
<tex>a^{2^{k-1}}=1(mod~2^{k+1})\Leftrightarrow a^{2^{k-1}}-1=0(mod~2^{k+1})\Leftrightarrow (a^{2^{k-2}}-1)\cdot(a^{2^{k-2}}+1)=0(mod~2^{k+1})</tex>.
<br>
Теперь докажем, что последнее сравнение верно. Из предположения индукции следует, что либо <tex>a^{2^{k-2}}-1=0(mod~2^{k+1})</tex> — и тогда получаем требуемое, либо <tex>a^{2^{k-2}}-1=2^{k}(mod~2^{k+1})</tex>. В этом случае рассмотрим второй сомножитель - либо <tex>a^{2^{k-2}}+1=2(mod~2^{k+1})</tex> - тогда умножая на полученное значение для первого получим <tex>(a^{2^{k-2}}-1)\cdot(a^{2^{k-2}}+1)=2^{k}\cdot 2=2^{k+1}=0(mod~2^{k+1})</tex>, либо <tex>a^{2^{k-1}}+1=2^{k}+2(mod~2^{k+1})</tex> - тогда в произведении получим <tex>(a^{2^{k-2}}-1)\cdot(a^{2^{k-2}}+1)=2^{k}\cdot(2^{k}+2)=2^{2\cdot k}+2^{k+1}=0(mod~2^{k+1})</tex>. Получается, что в любом случае сравнение, которое требовалось доказать выполняется. Значит выполняется и <tex>a^{2^{k-1}}=1(mod~2^{k+1})</tex>.
<br>
Мы доказали базу и шаг индукции, следовательно, доказали само утверждение.
}}
[[Категория: Теория чисел]]
