Изменения

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

<mathtex>ord(ab)=ord(a*)ord(b)=LCM</tex> , если <tex>gcd(ord(a), ord(b))=1</mathtex>, где <tex>ord(a)</tex> {{---}} [[порядок числа]] по модулю p, а <tex>LCM</tex> {{---}} наименьшее общее кратное двух чисел (least common multiple).

Рассмотрим <mathtex>(ab)^k \equiv 1(\pmod p)</mathtex>. Так как группа абелева {{---}} можем записать <mathtex>a^{k}*b^{k} \equiv 1(\pmod p)</mathtex>. Очевидно <mathtex>a^{k*\cdot ord(a)}*b^{k*\cdot ord(a)}\equiv 1(\pmod p)</mathtex>, однако из определения порядка числа следует <mathtex>a^{ord(a)}\equiv 1(\pmod p)</mathtex>, а значит <mathtex>a^{k*\cdot ord(a)}\equiv 1(\pmod p)</mathtex>. Отсюда делаем вывод, что <mathtex>b^{k*\cdot ord(a)}\equiv 1(\pmod p)</mathtex>. Значит <mathtex>k*\cdot ord(a)\vdots ord(b)</mathtex>. Аналогичным образом доказывается <mathtex>k*\cdot ord(b)\vdots ord(a)</mathtex>. Из этих двух фактови из взаимной простоты <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> — минимальное такое число.Лемма доказана

Пусть <mathtex>ord(a)=x*y</math>, НОД<math>(x,y)=1xy</mathtex>. Тогда <mathtex>ord(a^x)=y</mathtex>.

Очевидно, что <mathtex>(a^x)^y=1(\pmod p)</mathtex>. Требуется доказать только тот факт, что <mathtex>y</mathtex> {{--- }} минимальное такое число. Предположим, что <mathtex>ord(a^x)=f</mathtex>. Значит <mathtex>a^{x*fxf}=1(\pmod p)</mathtex>. Однако, по условию теоремы леммы имеем <mathtex>a^{x*yxy}=1(p)</mathtex>, причем <mathtex>x*yxy</mathtex> {{--- }} минимальное такое число. Получаем <mathtex>x*yxy\leqslant x*fxf</mathtex>, значит <mathtex>y\leqslant f</mathtex>, что и требовалось доказать.

|about= О цикличности мультипликативной группы поля <math>\mathbb{Z}/p \mathbb{Z}</math>.

Итак, нам требуется доказать существование порождающего элемента для нашей группы {{- --}} то есть такого элемента <tex>g</tex>, что <mathtex>\forall a: 1\leqslant a\leqslant p-1 ;\exists x: g^x=a(\pmod p)</mathtex>. Пусть <mathtex>k=LCMlcm(ord(i))</mathtex> по всем <mathtex>i:0\leqslant < i\leqslant p-1</mathtex>. Пусть теперь <mathtex>k=p_1^{k_1}+p_2^{k_2}+...+\cdots p_m^{k_m}</mathtex>. Тогда из определения <tex>k<math/tex> и свойств <tex>lcm</tex> следует, что <tex>\exists a:{ }ord(a)\vdots p_i^{k_i}</math> - следует из определения <tex>k</tex>. Значит , <mathtex>ord(a)=x*\cdot p_i^{k_i}</mathtex> для некоторого <tex>x</tex>, тогда по второй лемме <mathtex>ord(a^x)=p_i^{k_i}</mathtex>. Таким образом , мы можем найти такое число, что его порядок равен <mathtex>p_i^{k_i}</mathtex>. Пусть <mathtex>ord(a_i)=p_i^{k_i}</mathtex>. Тогда <tex>h= \prod^m_{i=1}a_i</tex> {{--- }} искомый элемент. И правда {{--- }} <mathtex>ord(h)=k</mathtex> {{--- }} по первой лемме. Очевидно порядок числа не может быть больше <tex>p-1</tex>, значит <mathtex>k\leqslant p-1</mathtex>. С другой стороны условие <mathtex> x^k=1(\pmod p)</mathtex> - выполняется для всех ненулевых вычетов по модулю <tex>p</tex>, которых <tex>p-1</tex> штук, а количество это уравнение не может иметь более <tex>k</tex> решений этого сравнения - (поскольку полином от одной переменной степени <tex>k</tex> не может иметь более <tex>k</tex>корней над [[Определение поля и подполя, изоморфизмы полей|полем]]). Таким образом , <mathtex>p-1\leqslant k</mathtex>. Значит ,<tex>k=p-1</tex>, что и требовалось.