63
правки
Изменения
Новая страница: «В этом разделе мы будет рассматривать элементы мультипликативной группы поля <math>\mathbb{Z}/p \m…»
В этом разделе мы будет рассматривать элементы мультипликативной группы поля <math>\mathbb{Z}/p \mathbb{Z}</math>, то есть вычетов по модулю <math>p</math>, причем <math>p \in \mathbb{P}</math>.
Прежде чем доказывать теорему, докажем две леммы.
{{Теорема
|id=l1
|about=Лемма 1
|statement=
<math>ord(a*b)=LCM(ord(a), ord(b))</math>, где <tex>ord(a)</tex> - [[порядок числа]] по модулю p, а <tex>LCM</tex> - наименьшее общее кратное двух чисел (least common multiple).
|proof=
Рассмотрим <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>. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.
}}
{{Теорема
|id=l2
|about= Лемма 2
|statement=
Пусть <math>ord(a)=x*y</math>, НОД<math>(x,y)=1</math>. Тогда <math>ord(a^x)=y</math>.
|proof=
Очевидно, что <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>, что и требовалось доказать.
}}
{{Теорема
|id=th
|about= О цикличности мультипликативной группы поля <math>\mathbb{Z}/p \mathbb{Z}</math>.
|statement=Мультипликативная группа поля <math>\mathbb{Z}/p \mathbb{Z}</math> циклична.
|proof=
Итак, нам требуется доказать существование порождающего элемента для нашей группы - то есть такого элемента <tex>g</tex>, что <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> - следует из определения <tex>k</tex>. Значит <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>. Тогда <tex>h= \prod^m_{i=1}a_i</tex> - искомый элемент. И правда - <math>ord(h)=k</math> - по первой лемме. Очевидно порядок числа не может быть больше <tex>p-1</tex>, значит <math>k\leqslant p-1</math>. С другой стороны <math> x^k=1(p)</math> - выполняется для всех ненулевых вычетов по модулю <tex>p</tex>, которых <tex>p-1</tex> штук, а количество решений этого сравнения - <tex>k</tex>. Таким образом <math>p-1\leqslant k</math>. Значит <tex>k=p-1</tex>, что и требовалось.
}}
Прежде чем доказывать теорему, докажем две леммы.
{{Теорема
|id=l1
|about=Лемма 1
|statement=
<math>ord(a*b)=LCM(ord(a), ord(b))</math>, где <tex>ord(a)</tex> - [[порядок числа]] по модулю p, а <tex>LCM</tex> - наименьшее общее кратное двух чисел (least common multiple).
|proof=
Рассмотрим <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>. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.
}}
{{Теорема
|id=l2
|about= Лемма 2
|statement=
Пусть <math>ord(a)=x*y</math>, НОД<math>(x,y)=1</math>. Тогда <math>ord(a^x)=y</math>.
|proof=
Очевидно, что <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>, что и требовалось доказать.
}}
{{Теорема
|id=th
|about= О цикличности мультипликативной группы поля <math>\mathbb{Z}/p \mathbb{Z}</math>.
|statement=Мультипликативная группа поля <math>\mathbb{Z}/p \mathbb{Z}</math> циклична.
|proof=
Итак, нам требуется доказать существование порождающего элемента для нашей группы - то есть такого элемента <tex>g</tex>, что <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> - следует из определения <tex>k</tex>. Значит <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>. Тогда <tex>h= \prod^m_{i=1}a_i</tex> - искомый элемент. И правда - <math>ord(h)=k</math> - по первой лемме. Очевидно порядок числа не может быть больше <tex>p-1</tex>, значит <math>k\leqslant p-1</math>. С другой стороны <math> x^k=1(p)</math> - выполняется для всех ненулевых вычетов по модулю <tex>p</tex>, которых <tex>p-1</tex> штук, а количество решений этого сравнения - <tex>k</tex>. Таким образом <math>p-1\leqslant k</math>. Значит <tex>k=p-1</tex>, что и требовалось.
}}
