Teoria grup

[cis123]

Udowodnij, że jeśli \(\displaystyle{ m,n > 1}\) i \(\displaystyle{ m | 2^{n} - 1}\), to \(\displaystyle{ l(m) > l(n)}\), gdzie \(\displaystyle{ l(x)}\) oznacza najmniejszy dzielnik pierwszy liczby \(\displaystyle{ x}\).
Wskazówka: rozważ rząd elementu 2 w \(\displaystyle{ \ZZ^{*}_{l(m)}}\)

Wiemy, że m jest nieparzyste, więc l(m) również jest nieparzyste.
Wiemy, że \(\displaystyle{ 2 \in \ZZ^{*}_{l(m)}}\).
Oznaczmy, przez \(\displaystyle{ k}\) rząd elementu \(\displaystyle{ 2}\), czyli najmniejsze \(\displaystyle{ k \in \NN}\), że \(\displaystyle{ 2^{k} = 1 (mod \ l(m))}\)

Z tw. Lagrange'a wynika, że \(\displaystyle{ k | l(m)-1}\), więc \(\displaystyle{ k < l(m)}\)
Skoro \(\displaystyle{ m | 2^{n} - 1}\), to także \(\displaystyle{ l(m) | 2^{n} - 1}\).

Teraz wypadałoby pokazać, że \(\displaystyle{ k \ge l(n)}\), ale nie mam pojęcia jak to zrobić. Jakieś pomysły?

[Premislav]

Z tw. Lagrange'a wynika, że \(\displaystyle{ k | l(m)-1}\),

A to dlaczego? Przecież \(\displaystyle{ l(m)}\) nie musi być liczbą pierwszą, więc rząd \(\displaystyle{ \ZZ_{l(m)}^{*}}\) nie musi wynosić \(\displaystyle{ l(m)-1}\). Może czegoś tu nie widzę, ale moim zdaniem ten wniosek jest nieuprawniony. Na przykład popatrzmy na
\(\displaystyle{ \ZZ_{8}^{*}}\). Mamy \(\displaystyle{ |\ZZ_{8}^{*}|=4}\) i oczywiście z Lagrange'a w szczególności rząd każdego elementu dzieli liczbę \(\displaystyle{ 4}\), ale np. rząd elementu \(\displaystyle{ 5}\) w \(\displaystyle{ \ZZ^{*}_8}\) jest równy \(\displaystyle{ 2}\), co ewidentnie nie dzieli liczby \(\displaystyle{ 7=8-1}\).
A nawet jakbyś się bronił, że \(\displaystyle{ l(m)}\) jest tutaj nieparzyste, to i tak nic nie pomoże, bo w nieparzystych też istnieje kontrprzykład (a tak naprawdę dzikie mnóstwo kontrprzykładów):
chociażby w \(\displaystyle{ \ZZ_9^{*}=\left\{1,2,4,5,7,8\right\}}\)
rząd elementu \(\displaystyle{ 2}\) wynosi \(\displaystyle{ 6}\) (tyle co rząd całej grupy), a to nie jest liczba podzielna przez \(\displaystyle{ 8=9-1}\).

Natomiast to zbyt wiele nie psuje, ponieważ możemy wywnioskować, że z tw. Lagrange'a \(\displaystyle{ k}\) dzieli rząd \(\displaystyle{ \ZZ_{l(m)}^{*}}\), który to nie przekracza \(\displaystyle{ l(m)-1}\), więc tak czy inaczej \(\displaystyle{ k<l(m)}\).

Teraz wypadałoby pokazać, że \(\displaystyle{ k \ge l(n)}\), ale nie mam pojęcia jak to zrobić.

Przypuśćmy nie wprost, że \(\displaystyle{ k<l(n)}\)
Użyjemy dzielenia z resztą: zapiszmy
\(\displaystyle{ n=k\cdot q+r}\), gdzie \(\displaystyle{ q \in \ZZ^+, \ r \in \left\{ 0, 1, \ldots k-1\right\}}\)
Ponieważ \(\displaystyle{ k<l(n)}\), więc \(\displaystyle{ k}\) nie jest dzielnikiem \(\displaystyle{ n}\) (bo oczywiście \(\displaystyle{ k>1}\)), zatem \(\displaystyle{ r\neq 0}\).
Skoro z definicji \(\displaystyle{ k}\) wiemy, że
\(\displaystyle{ 2^k\equiv 1\pmod{l(m)}}\) i \(\displaystyle{ k}\) jest najmniejszą liczbą całkowitą dodatnią o tej własności, to
\(\displaystyle{ 2^{n}=2^{k\cdot q+r}=\left( 2^k\right)^q 2^r\equiv 2^r\pmod{l(m)}}\)
ale \(\displaystyle{ 2^r\neq 1\pmod{l(m)}}\) z minimalności \(\displaystyle{ k}\), zatem
\(\displaystyle{ l(m)}\) nie dzieli \(\displaystyle{ 2^n-1}\), czyli tym bardziej \(\displaystyle{ m}\) nie dzieli \(\displaystyle{ 2^n-1}\), sprzeczność.