Изменения

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

<mathtex>ord(a*bab)=LCMlcm(ord(a), ord(b))</mathtex>, где <tex>ord(a)</tex> {{---}} [[порядок числа]] по модулю p, а <tex>LCMlcm</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>. Из этих двух фактов, а так же из определения порядка числа, очевидно следует требуемое.

Пусть <mathtex>ord(a)=x*yxy</mathtex>, НОДи <mathtex>gcd(x,y)=1</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>, что и требовалось доказать.