|
|
| (не показаны 4 промежуточные версии 3 участников) |
| Строка 12: |
Строка 12: |
| | |id=t | | |id=t |
| | |statement= | | |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> | + | Пусть <tex>g</tex> — первообразный корень по модулю <tex>p</tex><tex>\in\mathbb{P}</tex>. Тогда <tex>g</tex><sup>a</sup> — ''первообразный корень по модулю <tex>p</tex> <tex>\Leftrightarrow</tex> НОД<tex>(a;p-1)=1</tex>.''<br> |
| | |proof= | | |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, тогда < tex>1=g^{p-1}=(g^{p-1})^{\frac{a}{k}}=(g^{\frac{p-1}{k}})^a=(g^a)^{\frac{p-1}{k}}</ tex>. Но, по определению ord, < tex>p-1</ tex> — минимальная степень, в которую следует возвести < tex>g^a</ tex>, чтобы получить единицу, а < tex>\frac{p-1}{k}<p-1</ tex>. Получили противоречие, теорема доказана. |
| − | *Теперь докажем обратную теорему:
| + | \cdot Теперь докажем обратную теорему: |
| − | Пусть существует 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 такое, что < tex>g^{a\cdot k}=1</ tex>, и < tex>k<p-1</ tex>. Но < tex>g^{p-1}=1</ tex>, значит < tex>g^{a\cdot k}=g^{p-1}</ tex>. Следовательно либо < tex>(a \cdot k) \vdots (p-1)</ tex>, либо < tex>(p-1) \vdots (a \cdot k)</ tex>. Но по определению первообразного корня, и ord, < tex>p-1 \leqslant a \cdot k</ tex>, то есть < tex>(a \cdot k) \vdots (p-1)</ tex>, а так как НОД< tex>(a; p-1)=1</ tex>, то < tex>k \vdots (p-1) \Rightarrow p-1 \leqslant k</ tex>, что противоречит нашему предположению. Обратная теорема доказана. |
| | }} | | }} |
| | {{Теорема | | {{Теорема |
| Строка 23: |
Строка 23: |
| | |proof= | | |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> | + | Во-первых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов <tex>\mathbb{Z}/p \mathbb{Z}</tex> циклична (то есть <tex>\exists a\in\mathbb{Z}/p\mathbb{Z}\colon\forall b\in\mathbb{Z}/p\mathbb{Z} \text{ } \exists k\colon a^k=b</tex>).<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>
| + | Во-вторых, при <tex>a=k\cdot (p-1)+b \text{, }b<p-1 \colon g^a=(g^{p-1})^{k}\cdot g^b=1\cdot g^{b}</tex>. Таким образом есть смысл рассматривать только первообразные корни, образованные из исходного, путем возведения в степень не выше <tex>p-1</tex>.<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> различны. Теорема доказана. | + | По доказанной обратной теореме < tex>\forall a \colon с (a \text{; } p-1)=1 \Rightarrow g^a</ tex> — первообразный корень. С другой стороны для любого другого a, по прямой теореме < tex>g^a</ tex> не является первообразным корнем. Но по определению < tex>\varphi(p-1)</ tex> равно количеству < tex>a \colon </ tex> НОД < tex>(a;p-1)=1</ tex>. Очевидно, для всех < tex>a<p-1\text{, }g^a</ tex> различны. Теорема доказана. |
| | }} | | }} |
| | | | |
| − | ===Теорема о существовании первообразных корней по модулям <tex>2\text{, }4 \text{, }p^n \text{, }2 \cdot p^n</tex>===
| |
| − | {{Теорема
| |
| − | |id=the
| |
| − | |statement= По модулям <tex>2\text{, }4 \text{, }p^n \text{, }2 \cdot p^n</tex> существуют первообразные корни (<tex>p</tex> — простое, нечетное).
| |
| − | |proof=
| |
| − | Легко проверить, что число 1 является первообразным корнем по модулю 2, а число 3 — по модулю 4. Далее будем считать, что <tex>p\in \mathbb{P}\text{, }p>2</tex>.
| |
| − | Сначала разберем случай <math>p^2</math>.
| |
| − | Пусть <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>, что и требовалось доказать.
| |
| − | }}
| |
| − | {{Утверждение
| |
| − | |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> — получили противоречие.
| |
| − | <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>
| |
| − | Мы доказали базу и шаг индукции, следовательно, доказали само утверждение.
| |
| − | }}
| |
| | | | |
| | [[Категория: Теория чисел]] | | [[Категория: Теория чисел]] |
