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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
 
(не показаны 4 промежуточные версии 3 участников)
Строка 5: Строка 5:
 
|about=1
 
|about=1
 
|statement=
 
|statement=
<tex>ord(ab)=lcm(ord(a), ord(b))</tex>, где <tex>ord(a)</tex> {{---}} [[порядок числа]] по модулю p, а <tex>lcm</tex> {{---}} [[наименьшее общее кратное]] двух чисел (least common multiple).
+
<tex>ord(ab)=ord(a)ord(b)</tex> , если <tex>gcd(ord(a),ord(b))=1</tex>, где <tex>ord(a)</tex> {{---}} [[порядок числа]] по модулю p.
 
|proof=
 
|proof=
Рассмотрим <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>. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.
+
Рассмотрим <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>. Из этих двух фактов и из взаимной простоты <tex>ord(a)</tex> и <tex>ord(b)</tex> следует, что <tex>k\vdots ord(a)\cdot ord(b)</tex>. Значит порядок <tex>a\cdot b</tex> не может быть меньше <tex>k</tex>.
 +
<br>
 +
<tex>(a\cdot b)^{ord(a)\cdot ord(b)}=a^{ord(a)\cdot ord(b)}\cdot b^{ord(a)\cdot ord(b)}=1^{ord(b)}\cdot 1^{ord(a)}(mod~p)=1</tex>. Значит <tex>(a\cdot b)^{ord(a)\cdot ord(b)}=1(mod~p)</tex>, и <tex>ord(a)\cdot ord(b)</tex> — минимальное такое число. Лемма доказана
 
}}
 
}}
 
{{Лемма
 
{{Лемма
Строка 13: Строка 15:
 
|about=2
 
|about=2
 
|statement=
 
|statement=
Пусть <tex>ord(a)=xy</tex> и <tex>gcd(x,y)=1</tex>. Тогда <tex>ord(a^x)=y</tex>.
+
Пусть <tex>ord(a)=xy</tex>. Тогда <tex>ord(a^x)=y</tex>.
 
|proof=
 
|proof=
 
Очевидно, что <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>, что и требовалось доказать.
 
Очевидно, что <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>, что и требовалось доказать.

Текущая версия на 21:38, 9 октября 2011

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

Лемма (1):
[math]ord(ab)=ord(a)ord(b)[/math] , если [math]gcd(ord(a),ord(b))=1[/math], где [math]ord(a)[/math]порядок числа по модулю p.
Доказательство:
[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]ord(a)[/math] и [math]ord(b)[/math] следует, что [math]k\vdots ord(a)\cdot ord(b)[/math]. Значит порядок [math]a\cdot b[/math] не может быть меньше [math]k[/math].

[math](a\cdot b)^{ord(a)\cdot ord(b)}=a^{ord(a)\cdot ord(b)}\cdot b^{ord(a)\cdot ord(b)}=1^{ord(b)}\cdot 1^{ord(a)}(mod~p)=1[/math]. Значит [math](a\cdot b)^{ord(a)\cdot ord(b)}=1(mod~p)[/math], и [math]ord(a)\cdot ord(b)[/math] — минимальное такое число. Лемма доказана
[math]\triangleleft[/math]
Лемма (2):
Пусть [math]ord(a)=xy[/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 \pmod p[/math]. Пусть [math]k=lcm(ord(i))[/math] по всем [math]i:0 \lt i\leqslant p-1[/math]. Пусть теперь [math]k=p_1^{k_1}p_2^{k_2} \cdots p_m^{k_m}[/math]. Тогда из определения [math]k[/math] и свойств [math]lcm[/math] следует, что [math]\exists a:{ }ord(a)\vdots p_i^{k_i}[/math]. Значит, [math]ord(a)=x \cdot p_i^{k_i}[/math] для некоторого [math]x[/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 \pmod p[/math] выполняется для всех ненулевых вычетов по модулю [math]p[/math], которых [math]p-1[/math] штук, а это уравнение не может иметь более [math]k[/math] решений (поскольку полином от одной переменной степени [math]k[/math] не может иметь более [math]k[/math] корней над полем). Таким образом, [math]p-1\leqslant k[/math]. Значит,[math]k=p-1[/math], что и требовалось.
[math]\triangleleft[/math]