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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 3: Строка 3:
 
{{Лемма
 
{{Лемма
 
|id=l1
 
|id=l1
|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).
 
<math>ord(a*b)=LCM(ord(a), ord(b))</math>, где <tex>ord(a)</tex> {{---}} [[порядок числа]] по модулю p, а <tex>LCM</tex> {{---}} наименьшее общее кратное двух чисел (least common multiple).
Строка 11: Строка 11:
 
{{Лемма
 
{{Лемма
 
|id=l2
 
|id=l2
|about= Лемма 2
+
|about=2
 
|statement=
 
|statement=
 
Пусть <math>ord(a)=x*y</math>, НОД<math>(x,y)=1</math>. Тогда <math>ord(a^x)=y</math>.
 
Пусть <math>ord(a)=x*y</math>, НОД<math>(x,y)=1</math>. Тогда <math>ord(a^x)=y</math>.

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

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

Лемма (1):
[math]ord(a*b)=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(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]. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.
[math]\triangleleft[/math]
Лемма (2):
Пусть [math]ord(a)=x*y[/math], НОД[math](x,y)=1[/math]. Тогда [math]ord(a^x)=y[/math].
Доказательство:
[math]\triangleright[/math]
Очевидно, что [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], что и требовалось доказать.
[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]