Первообразные корни — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о существовании первообразных корней по модулям 4 \text{, }p^n \text{, }2 \cdot p^n)
Строка 37: Строка 37:
 
Пусть <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>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>, что и требовалось доказать.
 
Таким образом остается разобрать случай <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>, что и требовалось доказать.
 +
}}
 +
{{Утверждение
 +
|id=utv
 +
|about=Об отсутствии первообразных корней по остальным модулям
 +
|statement=Первообразных корней по модулям кроме <tex>2\text{, }4 \text{, }p^n \text{, }2 \cdot p^n</tex> (<tex>p</tex> — простое, нечетное) не существует.
 +
|proof=
 +
Предположим обратное. Выберем такой модуль <tex>n</tex>. <tex>n=p_1^{k_1}\cdot p_2^{k_2}\cdot ...\cdot p_m^{k_m}</tex>. Пусть <tex>g</tex> — первообразный корень по модулю <tex>n</tex>. <tex>\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}</tex>. Верна следующая система уравнений:
 +
<br>
 +
<tex>
 +
\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}
 +
\\
 +
</tex>
 +
<br>
 +
Однако, очевидно, что <tex>\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}</tex>. Тогда получим следующую систему:
 +
<br>
 +
<tex>
 +
\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}
 +
\\
 +
</tex>
 +
<br>
 +
Но тогда <tex>g^z=1(mod~ n)</tex>. Но по определению <tex>ord_n(g)=\phi(n)</tex>, а <tex>z<\phi(n)</tex> — получили противоречие.
 
}}
 
}}
  
 
[[Категория: Теория чисел]]
 
[[Категория: Теория чисел]]

Версия 09:59, 22 сентября 2010

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

Первообразные корни

Определение:
Вычет [math]g[/math] называется первообразным корнем по модулю [math]n[/math], если [math]ord(g)= \phi(n)[/math].


Где [math]ord(n)[/math]порядок числа [math]n[/math], а [math]\phi(n)[/math]функция Эйлера.

Теорема:
Пусть [math]g[/math] — первообразный корень по модулю [math]p[/math][math]\in\mathbb{P}[/math]. Тогда [math]g[/math]aпервообразный корень по модулю [math]p[/math] [math]\Leftrightarrow[/math] НОД[math](a;p-1)=1[/math].
Доказательство:
[math]\triangleright[/math]

Так как ga — первообразный корень, значит (ga)φ(p)=1, но p[math]\in\mathbb{P}[/math], поэтому φ(p)=p-1, значит (ga)p-1=1, и это же справедливо для g: gp-1=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}\lt p-1[/math]. Получили противоречие, теорема доказана.

  • Теперь докажем обратную теорему:
Пусть существует k такое, что [math]g^{a\cdot k}=1[/math], и [math]k\lt 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], что противоречит нашему предположению. Обратная теорема доказана.
[math]\triangleleft[/math]
Теорема (О количестве первообразных корней):
Количество различных первообразных корней по модулю p равно φ(p-1).
Доказательство:
[math]\triangleright[/math]

Пусть g — первообразный корень.
Во-первых, при [math]a=k*(p-1)+b \text{, }b\lt p-1 \colon g^a=(g^{p-1})^{k}*g^b=1\cdot g^{b}[/math]. Таким образом есть смысл рассматривать только первообразные корни, образованные из исходного, путем возведения в степень не выше [math]p-1[/math].
Во-вторых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов [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]).

По доказанной обратной теореме [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\lt p-1\text{, }g^a[/math] различны. Теорема доказана.
[math]\triangleleft[/math]

Теорема о существовании первообразных корней по модулям [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)\lt tex\gt . По определению \lt tex\gt 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]\triangleleft[/math]