Теорема о цикличности мультипликативной группы поля Z/pZ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
В этом разделе мы будет рассматривать элементы мультипликативной группы поля <math>\mathbb{Z}/p \mathbb{Z}</math>, то есть вычетов по модулю <math>p</math>, причем <math>p \in \mathbb{P}</math>.
+
В этом разделе мы будет рассматривать элементы мультипликативной группы поля <tex>\mathbb{Z}/p \mathbb{Z}</tex>, то есть вычетов по модулю <tex>p</tex>, причем <tex>p \in \mathbb{P}</tex>.
 
Прежде чем доказывать теорему, докажем две леммы.
 
Прежде чем доказывать теорему, докажем две леммы.
 
{{Лемма
 
{{Лемма
Строка 5: Строка 5:
 
|about=1
 
|about=1
 
|statement=
 
|statement=
<math>ord(a*b)=LCM(ord(a), ord(b))</math>, где <tex>ord(a)</tex> {{---}} [[порядок числа]] по модулю p, а <tex>LCM</tex> {{---}} наименьшее общее кратное двух чисел (least common multiple).
+
<tex>ord(ab)=lcm(ord(a), ord(b))</tex>, где <tex>ord(a)</tex> {{---}} [[порядок числа]] по модулю p, а <tex>lcm</tex> {{---}} [[наименьшее общее кратное]] двух чисел (least common multiple).
 
|proof=
 
|proof=
Рассмотрим <math>(ab)^k \equiv 1(p)</math>. Так как группа абелева {{---}} можем записать <math>a^{k}*b^{k} \equiv 1(p)</math>. Очевидно <math>a^{k*ord(a)}*b^{k*ord(a)}\equiv 1(p)</math>, однако из определения порядка числа следует <math>a^{ord(a)}\equiv 1(p)</math>, а значит <math>a^{k*ord(a)}\equiv 1(p)</math>. Отсюда делаем вывод, что <math>b^{k*ord(a)}\equiv 1(p)</math>. Значит <math>k*ord(a)\vdots ord(b)</math>. Аналогичным образом доказывается <math>k*ord(b)\vdots ord(a)</math>. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.
+
Рассмотрим <tex>(ab)^k \equiv 1 \pmod p</tex>. Так как группа абелева {{---}} можем записать <tex>a^{k}b^{k} \equiv 1 \pmod p</tex>. Очевидно <tex>a^{k \cdot ord(a)}b^{k \cdot ord(a)}\equiv 1 \pmod p</tex>, однако из определения порядка числа следует <tex>a^{ord(a)}\equiv 1 \pmod p</tex>, а значит <tex>a^{k \cdot ord(a)}\equiv 1 \pmod p</tex>. Отсюда делаем вывод, что <tex>b^{k \cdot ord(a)}\equiv 1 \pmod p</tex>. Значит <tex>k \cdot ord(a)\vdots ord(b)</tex>. Аналогичным образом доказывается <tex>k \cdot ord(b)\vdots ord(a)</tex>. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.
 
}}
 
}}
 
{{Лемма
 
{{Лемма
Строка 13: Строка 13:
 
|about=2
 
|about=2
 
|statement=
 
|statement=
Пусть <math>ord(a)=x*y</math>, НОД<math>(x,y)=1</math>. Тогда <math>ord(a^x)=y</math>.
+
Пусть <tex>ord(a)=xy</tex> и <tex>gcd(x,y)=1</tex>. Тогда <tex>ord(a^x)=y</tex>.
 
|proof=
 
|proof=
Очевидно, что <math>(a^x)^y=1(p)</math>. Требуется доказать только тот факт, что <math>y</math> - минимальное такое число. Предположим, что <math>ord(a^x)=f</math>. Значит <math>a^{x*f}=1(p)</math>. Однако, по условию теоремы имеем <math>a^{x*y}=1(p)</math>, причем <math>x*y</math> - минимальное такое число. Получаем <math>x*y\leqslant x*f</math>, значит <math>y\leqslant f</math>, что и требовалось доказать.
+
Очевидно, что <tex>(a^x)^y=1 \pmod p</tex>. Требуется доказать только тот факт, что <tex>y</tex> {{---}} минимальное такое число. Предположим, что <tex>ord(a^x)=f</tex>. Значит <tex>a^{xf}=1 \pmod p</tex>. Однако, по условию леммы имеем <tex>a^{xy}=1(p)</tex>, причем <tex>xy</tex> {{---}} минимальное такое число. Получаем <tex>xy\leqslant xf</tex>, значит <tex>y\leqslant f</tex>, что и требовалось доказать.
 
}}
 
}}
 
{{Теорема
 
{{Теорема

Версия 08:22, 28 июня 2010

В этом разделе мы будет рассматривать элементы мультипликативной группы поля [math]\mathbb{Z}/p \mathbb{Z}[/math], то есть вычетов по модулю [math]p[/math], причем [math]p \in \mathbb{P}[/math]. Прежде чем доказывать теорему, докажем две леммы.

Лемма (1):
[math]ord(ab)=lcm(ord(a), ord(b))[/math], где [math]ord(a)[/math]порядок числа по модулю p, а [math]lcm[/math]наименьшее общее кратное двух чисел (least common multiple).
Доказательство:
[math]\triangleright[/math]
Рассмотрим [math](ab)^k \equiv 1 \pmod p[/math]. Так как группа абелева — можем записать [math]a^{k}b^{k} \equiv 1 \pmod p[/math]. Очевидно [math]a^{k \cdot ord(a)}b^{k \cdot ord(a)}\equiv 1 \pmod p[/math], однако из определения порядка числа следует [math]a^{ord(a)}\equiv 1 \pmod p[/math], а значит [math]a^{k \cdot ord(a)}\equiv 1 \pmod p[/math]. Отсюда делаем вывод, что [math]b^{k \cdot ord(a)}\equiv 1 \pmod p[/math]. Значит [math]k \cdot ord(a)\vdots ord(b)[/math]. Аналогичным образом доказывается [math]k \cdot ord(b)\vdots ord(a)[/math]. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.
[math]\triangleleft[/math]
Лемма (2):
Пусть [math]ord(a)=xy[/math] и [math]gcd(x,y)=1[/math]. Тогда [math]ord(a^x)=y[/math].
Доказательство:
[math]\triangleright[/math]
Очевидно, что [math](a^x)^y=1 \pmod p[/math]. Требуется доказать только тот факт, что [math]y[/math] — минимальное такое число. Предположим, что [math]ord(a^x)=f[/math]. Значит [math]a^{xf}=1 \pmod p[/math]. Однако, по условию леммы имеем [math]a^{xy}=1(p)[/math], причем [math]xy[/math] — минимальное такое число. Получаем [math]xy\leqslant xf[/math], значит [math]y\leqslant f[/math], что и требовалось доказать.
[math]\triangleleft[/math]
Теорема (О цикличности мультипликативной группы поля [math]\mathbb{Z}/p \mathbb{Z}[/math].):
Мультипликативная группа поля [math]\mathbb{Z}/p \mathbb{Z}[/math] циклична.
Доказательство:
[math]\triangleright[/math]
Итак, нам требуется доказать существование порождающего элемента для нашей группы - то есть такого элемента [math]g[/math], что [math]\forall a: 1\leqslant a\leqslant p-1 ;\exists x: g^x=a(p)[/math]. Пусть [math]k=LCM(ord(i))[/math] по всем [math]i:0\leqslant i\leqslant p-1[/math]. Пусть теперь [math]k=p_1^{k_1}+p_2^{k_2}+...+p_m^{k_m}[/math]. [math]\exists a:{ }ord(a)\vdots p_i^{k_i}[/math] - следует из определения [math]k[/math]. Значит [math]ord(a)=x*p_i^{k_i}[/math], тогда по второй лемме [math]ord(a^x)=p_i^{k_i}[/math]. Таким образом мы можем найти такое число, что его порядок равен [math]p_i^{k_i}[/math]. Пусть [math]ord(a_i)=p_i^{k_i}[/math]. Тогда [math]h= \prod^m_{i=1}a_i[/math] - искомый элемент. И правда - [math]ord(h)=k[/math] - по первой лемме. Очевидно порядок числа не может быть больше [math]p-1[/math], значит [math]k\leqslant p-1[/math]. С другой стороны [math] x^k=1(p)[/math] - выполняется для всех ненулевых вычетов по модулю [math]p[/math], которых [math]p-1[/math] штук, а количество решений этого сравнения - [math]k[/math]. Таким образом [math]p-1\leqslant k[/math]. Значит [math]k=p-1[/math], что и требовалось.
[math]\triangleleft[/math]