Dowód niepodzielności

[xxDorianxx]

Witam mam problem z tym zadaniem.Wykaż,że nie ma takiego \(\displaystyle{ n>1}\) dzielącego \(\displaystyle{ 2^n-1}\).

[Premislav]

Jeżeli \(\displaystyle{ n}\) jest parzyste, to nawet \(\displaystyle{ 2\nmid 2^n-1}\), tym bardziej \(\displaystyle{ n\nmid 2^n-1}\).
Dalej przypuśćmy nie wprost, że \(\displaystyle{ n}\) jest liczbą nieparzystą taką, że \(\displaystyle{ n|2^n-1}\).
Niech \(\displaystyle{ p}\) będzie najmniejszą liczbą pierwszą dzielącą \(\displaystyle{ n}\). Wówczas w szczególności \(\displaystyle{ p|2^n-1}\). Z małego twierdzenia Fermata mamy \(\displaystyle{ 2^{p-1}\equiv 1\pmod{p}}\).
Niech teraz \(\displaystyle{ r}\) będzie rzędem \(\displaystyle{ 2}\) modulo \(\displaystyle{ p}\), tj. \(\displaystyle{ r}\) jest najmniejszą liczbą całkowitą dodatnią, która spełnia zależność \(\displaystyle{ 2^r\equiv 1\pmod{p}}\)
Udowodnijmy przez sprzeczność, że \(\displaystyle{ r|n}\) (zostawiam ten fragment jako proste ćwiczenie dla Ciebie). Ponieważ \(\displaystyle{ r\le p-1}\), to albo \(\displaystyle{ r=1}\) (łatwo sprawdzamy, że to prowadzi do sprzeczności), albo istnieje liczba pierwsza \(\displaystyle{ q\le p-1}\), która dzieli \(\displaystyle{ r}\). Wówczas z przechodniości relacji podzielności także \(\displaystyle{ q|n}\), ale \(\displaystyle{ q<p}\), sprzeczność z minimalnością \(\displaystyle{ p}\).

[xxDorianxx]

Premislav, Wielkie Dzięki