Существование первообразных корней по определённым модулям

Эта статья находится в разработке!

Теорема о существовании первообразных корней по модулям [math]2\text{, }4 \text{, }p^n \text{, }2 \cdot p^n[/math]

Теорема:

По модулям [math]2\text{, }4 \text{, }p^n \text{, }2 \cdot p^n[/math] существуют первообразные корни ([math]p[/math] — простое, нечетное).

Доказательство:

[math]\triangleright[/math]

Легко проверить, что число 1 является первообразным корнем по модулю 2, а число 3 — по модулю 4. Далее будем считать, что [math]p\in \mathbb{P}\text{, }p\gt 2[/math]. Сначала разберем случай [math]p^2[/math]. Пусть [math]g[/math] — первообразный корень по модулю [math]p\text{, }k=ord_{p^2}(g)[/math]. Тогда [math]g^k=1(p^2)[/math], следовательно [math]g^k=1(p)[/math], и значит [math]k\vdots (p-1)[/math]. Также заметим, что [math]\phi(p^2)=p(p-1)\vdots k[/math]. Получаем два случая — [math]k=p-1[/math], и [math]k=p(p-1)[/math]. Во втором случае получается что [math]g[/math] — первообразный корень по модулю [math]p^2[/math]. Теперь рассмотрим первый случай: применим предыдущие рассуждения к числу [math]g+p[/math] (это возможно, так как [math]g+p\equiv g (p)[/math]). [math](g+p)^{p-1}=g^{p-1}+c^{1}_{p-1}g^{p-2}p+...[/math] — заметим, что все слагаемые, начиная с третьего содержат множитель [math]p^2[/math] — поэтому обнуляются по модулю [math]p^2[/math]. [math]g^{p-1}=1(p^2)[/math], а [math]c^{1}_{p-1}g^{p-2}p=p(p-1)g^{p-2}\neq 0(p^2)[/math], значит [math](g+p)^{p-1}\neq 1(p^2)[/math], значит число [math]k[/math], для [math]g+p[/math] не может быть равно [math]p-1[/math], тогда [math]g+p[/math] — первеобразный корень по модулю [math]p^2[/math]. Аналогичным образом, если имеется первообразный корень по модулю [math]p^a[/math] отыскивается первообразный корень по модулю [math]p^{a+1}[/math]. Таким образом остается разобрать случай [math]2\cdot p^n[/math]. Пусть [math]g[/math] — первообразный корень по модулю [math]p^n[/math]. Утверждается, что нечетное из [math]g[/math] и [math]g+p^n[/math] — первообразный корень по модулю [math]2\cdot p^n[/math]. Переобозначим это нечетное число за [math]g[/math], для удобства. Пользуяся свойствами функции Эйлера, получим [math]\phi (2\cdot p^n)=\phi(2)\cdot\phi(p^n)=\phi(p^n)[/math]. По определению [math]g[/math] имеем [math]ord_{p^n}(g)=\phi(p^n)[/math], а так же [math](g;2\cdot p^n)=1[/math]. Отсюда очевидно получаем [math]ord_{2\cdot p^n}(g)\geqslant ord_{p^n}(g)=\phi(p^n)=\phi(2 \cdot p^n)[/math]. Но порядок числа по любому взаимнопростому с этим числом модулю не может превосходить значения функции Эйлера от этого модуля, то есть [math]ord_{2\cdot p^n}(g)\leqslant \phi(2\cdot p^n)=\phi(p^n)[/math]. Получаем [math]ord_{2 \cdot p^n}(g)=\phi(2 \cdot p^n)[/math], что и требовалось доказать.

[math]\triangleleft[/math]

Утверждение (Об отсутствии первообразных корней по остальным модулям):

Первообразных корней по модулям кроме [math]2\text{, }4 \text{, }p^n \text{, }2 \cdot p^n[/math] ([math]p[/math] — простое, нечетное) не существует.

[math]\triangleright[/math]

Предположим обратное. Выберем такой модуль [math]n[/math]. [math]n=p_1^{k_1}\cdot p_2^{k_2}\cdot ...\cdot p_m^{k_m}[/math]. Пусть [math]g[/math] — первообразный корень по модулю [math]n[/math]. [math]\phi(n)=\phi(p_1^{k_1})\cdot \phi(p_2^{k_2})\cdot ... \cdot \phi(p_m^{k_m})=(p_1-1)p_1^{k_1-1} \cdot (p_2-1)p_2^{k_2-1}\cdot ... \cdot (p_m-1)p_m^{k_m-1}[/math]. Верна следующая система уравнений: [math] \begin{cases} g^{(p_1-1)p_1^{k_1-1}}=1(mod~ p_1^{k_1})\\ g^{(p_2-1)p_2^{k_2-1}}=1(mod~ p_2^{k_2})\\ \dots\\ g^{(p_m-1)p_m^{k_m-1}}=1(mod~ p_m^{k_m})\\ \end{cases} \\ [/math] Однако, очевидно, что [math]\forall i~z=\phi(n)/2= \frac{(p_1-1)p_1^{k_1-1} \cdot (p_2-1)p_2^{k_2-1}\cdot ... \cdot (p_m-1)p_m^{k_m-1}}{2} \vdots (p_i-1)p_i^{k_i-1}[/math]. Тогда получим следующую систему: [math] \begin{cases} g^z=1(mod~ p_1^{k_1})\\ g^z=1(mod~ p_2^{k_2})\\ \dots\\ g^z=1(mod~ p_m^{k_m})\\ \end{cases} \\ [/math] Но тогда [math]g^z=1(mod~ n)[/math]. Но по определению [math]ord_n(g)=\phi(n)[/math], а [math]z\lt \phi(n)[/math] — получили противоречие. Осталось разобрать случай [math]p=2^k,~ k\gt 2[/math]. Мы докажем, что для модулей такого вида выполняется [math]a^{\frac{\phi(2^k)}{2}}=a^{2^{k-2}}=1(mod~2^k)[/math]. Очевидно это будет означать, что таким модулям первообразных корней нет. Доказательство построим по индукции. 1) База: [math]k=3[/math]. Легко простым перебором убедиться, что [math]a^2\equiv 1(mod~8)[/math]. 2) Шаг индукции: пусть доказано, что [math]a^{2^{k-2}}=1(mod~2^k)[/math]. Докажем, что [math]a^{2^{k-1}}=1(mod~2^{k+1})[/math]. Рассмотрим это сравнение: [math]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})[/math]. Теперь докажем, что последнее сравнение верно. Из предположения индукции следует, что либо [math]a^{2^{k-2}}-1=0(mod~2^{k+1})[/math] — и тогда получаем требуемое, либо [math]a^{2^{k-2}}-1=2^{k}(mod~2^{k+1})[/math]. В этом случае рассмотрим второй сомножитель — либо [math]a^{2^{k-2}}+1=2(mod~2^{k+1})[/math] — тогда умножая на полученное значение для первого получим [math](a^{2^{k-2}}-1)\cdot(a^{2^{k-2}}+1)=2^{k}\cdot 2=2^{k+1}=0(mod~2^{k+1})[/math], либо [math]a^{2^{k-1}}+1=2^{k}+2(mod~2^{k+1})[/math] — тогда в произведении получим [math](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})[/math]. Получается, что в любом случае сравнение, которое требовалось доказать выполняется. Значит выполняется и [math]a^{2^{k-1}}=1(mod~2^{k+1})[/math]. Мы доказали базу и шаг индукции, следовательно, доказали само утверждение.

[math]\triangleleft[/math]