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

2010-09-13T03:15:09Z

Andrey:

В этом разделе мы будет рассматривать элементы [[мультипликативная группа поля|мультипликативной группы]] [[Определение поля и подполя, изоморфизмы полей|поля]] <tex>\mathbb{Z}/p \mathbb{Z}</tex>, то есть вычетов по модулю <tex>p</tex>, причем <tex>p \in \mathbb{P}</tex>.
Прежде чем доказывать теорему, докажем две леммы.
{{Лемма
|id=l1
|about=1
|statement=
<tex>ord(ab)=lcm(ord(a), ord(b))</tex>, где <tex>ord(a)</tex> {{---}} [[порядок числа]] по модулю p, а <tex>lcm</tex> {{---}} [[наименьшее общее кратное]] двух чисел (least common multiple).
|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>. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.

WTF?
<tex>p = 5; a = b = 2; ord(a) = ord(b) = 4, ord(ab) = 2, lcm(ord(a), ord(b)) = 4.</tex>
}}
{{Лемма
|id=l2
|about=2
|statement=
Пусть <tex>ord(a)=xy</tex> и <tex>gcd(x,y)=1</tex>. Тогда <tex>ord(a^x)=y</tex>.
|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>, что и требовалось доказать.
}}
{{Теорема
|id=th
|about=О цикличности мультипликативной группы поля <math>\mathbb{Z}/p \mathbb{Z}</math>
|statement=Мультипликативная группа поля <math>\mathbb{Z}/p \mathbb{Z}</math> циклична.
|proof=
Итак, нам требуется доказать существование порождающего элемента для нашей группы {{---}} то есть такого элемента <tex>g</tex>, что <tex>\forall a: 1\leqslant a\leqslant p-1 ;\exists x: g^x=a \pmod p</tex>. Пусть <tex>k=lcm(ord(i))</tex> по всем <tex>i:0 < i\leqslant p-1</tex>. Пусть теперь <tex>k=p_1^{k_1}p_2^{k_2} \cdots p_m^{k_m}</tex>. Тогда из определения <tex>k</tex> и свойств <tex>lcm</tex> следует, что <tex>\exists a:{ }ord(a)\vdots p_i^{k_i}</tex>. Значит, <tex>ord(a)=x \cdot p_i^{k_i}</tex> для некоторого <tex>x</tex>, тогда по второй лемме <tex>ord(a^x)=p_i^{k_i}</tex>. Таким образом, мы можем найти такое число, что его порядок равен <tex>p_i^{k_i}</tex>. Пусть <tex>ord(a_i)=p_i^{k_i}</tex>. Тогда <tex>h= \prod^m_{i=1}a_i</tex> {{---}} искомый элемент. И правда {{---}} <tex>ord(h)=k</tex> {{---}} по первой лемме. Очевидно порядок числа не может быть больше <tex>p-1</tex>, значит <tex>k\leqslant p-1</tex>. С другой стороны условие <tex>x^k=1 \pmod p</tex> выполняется для всех ненулевых вычетов по модулю <tex>p</tex>, которых <tex>p-1</tex> штук, а это уравнение не может иметь более <tex>k</tex> решений (поскольку полином от одной переменной степени <tex>k</tex> не может иметь более <tex>k</tex> корней над [[Определение поля и подполя, изоморфизмы полей|полем]]). Таким образом, <tex>p-1\leqslant k</tex>. Значит,<tex>k=p-1</tex>, что и требовалось.
}}

[[Категория: Теория чисел]]

Викиконспекты - Вклад участника [ru]

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