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

В этом разделе мы будет рассматривать элементы мультипликативной группы поля [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]