63
правки
Изменения
м
Нет описания правки
|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>. WTF?<br><tex>p (a\cdot b)^{ord(a)\cdot ord(b)}= 5; a = ^{ord(a)\cdot ord(b)}\cdot b = 2; ^{ord(a) \cdot ord(b)}= 1^{ord(b)}\cdot 1^{ord(a)}(mod~p) = 4, 1</tex>. Значит <tex>(a\cdot b)^{ord(a)\cdot ord(abb) }= 21(mod~p)</tex>, lcm(и <tex>ord(a), \cdot ord(b)) = 4.</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>, что и требовалось доказать.
