Первообразные корни — различия между версиями
Haliullin (обсуждение | вклад) (Новая страница: «==Первообразные корни== ===Количество первообразных корней=== * '''Определение.''' ''<math>g</math> наз…») |
Haliullin (обсуждение | вклад) м (→Количество первообразных корней) |
||
| Строка 4: | Строка 4: | ||
Где <math>ord</math> - порядок числа, а φ - функция Эйлера.<br> | Где <math>ord</math> - порядок числа, а φ - функция Эйлера.<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> | * '''Теорема'''. Пусть <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> | + | ** '''Доказательство (прямая теорема)'''<br> |
Так как 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> | + | ** '''Доказательство (обратная теорема)'''<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> | * '''Следствие (из обратной теоремы)''' ''Количество различных первообразных корней по модулю p равно φ(p-1).''<br> | ||
| Строка 14: | Строка 14: | ||
Во-вторых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов <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>=== | ||
Версия 01:38, 18 июня 2010
Первообразные корни
Количество первообразных корней
- Определение. называется первообразным корнем по модулю n, если φ
Где - порядок числа, а φ - функция Эйлера.
- Теорема. Пусть - первообразный корень по модулю . Тогда a - первообразный корень по модулю НОД.
- Доказательство (прямая теорема)
- Доказательство (прямая теорема)
Так как ga - первообразный корень, значит (ga)φ(p)=1, но p, поэтому φ(p)=p-1, значит (ga)p-1=1, и это же справедливо для g: gp-1=1. Пусть НОД(a;p-1)=k, k>1, тогда . Но, по определению ord, - минимальная степень, в которую следует возвести , чтобы получить единицу, а . Получили противоречие, теорема доказана.
- Доказательство (обратная теорема)
- Доказательство (обратная теорема)
Пусть существует k такое, что , и . Но , значит . Следовательно либо , либо . Но по определению первообразного корня, и ord, , то есть , а так как НОД, то , что противоречит нашему предположению. Обратная теорема доказана.
- Следствие (из обратной теоремы) Количество различных первообразных корней по модулю p равно φ(p-1).
Доказательство
Пусть g - первообразный корень.
Во-первых, при . Таким образом есть смысл рассматривать только первообразные корни, образованные из исходного, путем возведения в степень не выше .
Во-вторых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов циклична (то есть ).
По доказанной обратной теореме - первообразный корень. С другой стороны для любого другого a, по прямой теореме не является первообразным корнем. Но по определению равно количеству НОД . Очевидно, для всех различны. Теорема доказана.
