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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (страница помечена как страница в разработке)
(→‎Количество первообразных корней)
Строка 2: Строка 2:
  
 
==Первообразные корни==
 
==Первообразные корни==
−
===Количество первообразных корней===
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Число <tex>g</tex> называется '''первообразным корнем''' по модулю <tex>n</tex>, если <tex>ord(g)= \phi(n)</tex>.
+
Вычет <tex>g</tex> называется '''первообразным корнем''' по модулю <tex>n</tex>, если <tex>ord(g)= \phi(n)</tex>.
 
}}
 
}}
  
 
Где <tex>ord(n)</tex> — [[порядок числа]] <tex>n</tex>, а <tex>\phi(n)</tex> — [[функция Эйлера]].<br />
 
Где <tex>ord(n)</tex> — [[порядок числа]] <tex>n</tex>, а <tex>\phi(n)</tex> — [[функция Эйлера]].<br />
  
−
* '''Теорема'''. Пусть <math>g</math> - первообразный корень по модулю <math>p</math><tex>\in\mathbb{P}</tex>. Тогда <math>g</math><sup>a</sup> - ''первообразный корень по модулю <math>p</math> <math>\Leftrightarrow</math> НОД<math>(a;p-1)=1</math>.''<br>
+
{{Теорема
−
** '''Доказательство (прямая теорема)'''<br>
+
|id=t
 +
|statement=
 +
Пусть <math>g</math> - первообразный корень по модулю <math>p</math><tex>\in\mathbb{P}</tex>. Тогда <math>g</math><sup>a</sup> - ''первообразный корень по модулю <math>p</math> <math>\Leftrightarrow</math> НОД<math>(a;p-1)=1</math>.''<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, тогда <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}<p-1</math>. Получили противоречие, теорема доказана.
 
Так как 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, тогда <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}<p-1</math>. Получили противоречие, теорема доказана.
−
** '''Доказательство (обратная теорема)'''<br>
+
*Теперь докажем обратную теорему:
 
Пусть существует k такое, что <math>g^{a\cdot k}=1</math>, и <math>k<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>, что противоречит нашему предположению. Обратная теорема доказана.
 
Пусть существует k такое, что <math>g^{a\cdot k}=1</math>, и <math>k<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>, что противоречит нашему предположению. Обратная теорема доказана.
−
* '''Следствие''' ''Количество различных первообразных корней по модулю p равно φ(p-1).''<br>
+
}}
−
'''Доказательство'''<br>
+
{{Теорема
 +
|about=О количестве первообразных корней
 +
|statement=Количество различных первообразных корней по модулю p равно φ(p-1).
 +
|proof=
 
Пусть g - первообразный корень.<br>
 
Пусть g - первообразный корень.<br>
 
Во-первых, при <math>a=k*(p-1)+b \text{, }b<p-1 \colon g^a=(g^{p-1})^{k}*g^b=1\cdot g^{b}</math>. Таким образом есть смысл рассматривать только первообразные корни, образованные из исходного, путем возведения в степень не выше <math>p-1</math>.<br>
 
Во-первых, при <math>a=k*(p-1)+b \text{, }b<p-1 \colon g^a=(g^{p-1})^{k}*g^b=1\cdot g^{b}</math>. Таким образом есть смысл рассматривать только первообразные корни, образованные из исходного, путем возведения в степень не выше <math>p-1</math>.<br>
 
Во-вторых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов <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>).<br>
 
Во-вторых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов <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>).<br>
 
По доказанной обратной теореме <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<p-1\text{, }g^a</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<p-1\text{, }g^a</math> различны. Теорема доказана.
 +
}}
  
 
===Теорема о существовании первообразных корней по модулям <math>4 \text{, }p^n \text{, }2 \cdot p^n</math>===
 
===Теорема о существовании первообразных корней по модулям <math>4 \text{, }p^n \text{, }2 \cdot p^n</math>===

Версия 23:52, 27 июня 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]4 \text{, }p^n \text{, }2 \cdot p^n[/math]

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Первообразные_корни&oldid=1954»