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

В этом разделе мы будет рассматривать элементы мультипликативной группы поля [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]. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое. WTF? [math]p = 5; a = b = 2; ord(a) = ord(b) = 4, ord(ab) = 2, lcm(ord(a), ord(b)) = 4.[/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 \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]