Изменения
Нет описания правки
|about=1
|statement=
<tex>ord(ab)=lcmord(a)ord(b)</tex> , если <tex>gcd(ord(a), ord(b))=1</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>. Из этих двух фактови из взаимной простоты <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> — минимальное такое число.Лемма доказана
}}
{{Лемма
|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>, что и требовалось доказать.
