Matematyka.pl

Niech n będzie liczbą całkowitą \(\displaystyle{ \ge 2}\). Udowodnić, że n nie dzieli \(\displaystyle{ 2^{n} -1}\).

prosze o wskazówki jak rozwiązać to zadanie

A więc na samym początku trzeba zauważyć że pod lupę bierzemy jedynie n nieparzyste.
(Jako że wyrażenie daje zawsze wynik w postaci liczby nieparzystej nie podzielimy jej nigdy przez liczbę parzystą).

Skoro już to wiemy możemy od razu odrzucić wszystkie liczby pierwsze korzystając z małego twierdzenia Fermata, gdyż każda liczba z n pierwszym \(\displaystyle{ 2 ^{n}}\) będzie przystawała do 2 (mod n).

Zauważ jeszcze, że \(\displaystyle{ 2 ^{n}}\) zawsze będzie przystawało do parzystej liczby (mod n).

Pingwin94 pisze:Zauważ jeszcze, że \(\displaystyle{ 2 ^{n}}\) zawsze będzie przystawało do parzystej liczby (mod n).

?

Dla \(\displaystyle{ n\ge 2}\) ma zachodzić \(\displaystyle{ n | 2^n-1}\), oczywiście \(\displaystyle{ 2 \nmid n}\). Niech teraz \(\displaystyle{ p}\) będzie najmniejszym dzielnikiem pierwszym \(\displaystyle{ n}\), oraz \(\displaystyle{ t = ord_p 2}\), musi więc zachodzić \(\displaystyle{ t | n}\), oraz z twierdzenia Eulera dostajemy \(\displaystyle{ 2^{p-1} \equiv 1 \pmod{p}}\), skąd \(\displaystyle{ t | p-1}\), czyli \(\displaystyle{ t \le p-1 < p}\) ale z założenia p jest najmniejszym dzielnikiem pierwszym n, więc \(\displaystyle{ t=1}\), czyli \(\displaystyle{ 2 \equiv 1 \pmod{p} \Leftrightarrow p=1}\) ale z założenia p jest pierwsze, czyli n nie ma dzielników pierwszych, co bezpośrednio implikuje \(\displaystyle{ n=1}\), ale z założenia \(\displaystyle{ n\ge 2}\) więc dana podzielność nie zajdzie dla żadnego n, cnd.