XXI OM - II -Zadanie 3

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Udowodnić twierdzenie: Nie istnieje taka liczba naturalna $n > 1$ , że liczba $2^n - 1$ dzieli się przez $n$ .

Rozwiązanie

\spos{1} Załóżmy, że $n$ jest najmniejszą liczbą naturalną większą od jedności taką, że $n \mid 2^n - 1$ , zaś $k$ - najmniejszą liczbą naturalną taką, że $n \mid 2^k - 1$ . Na mocy twierdzenia danego do dowodu w zadaniu 9 na zawodach stopnia I mamy $k < n$ .

Niech $n = km + r$ , gdzie $0 \leq r < k$ . Ponieważ $n \mid 2^n - 1$ i $n \mid 2^{km} - 1$ , więc $n \mid 2^n - 2^{km} = 2^{km} (2^r - 1)$ i wobec nieparzystości $n$ otrzymujemy, że $n \mid 2^r - 1$ . Stąd wobec określenia liczby $k$ i nierówności $r < k$ , wynika, że $r = 0$ . Zatem $k \mid n$ , $k \mid 2^k - 1$ i wobec określenia liczby $n$ i nierówności $k < n$ mamy $k = 1$ . Stąd $n \mid 2^1 - 1$ , $n = 1$ i otrzymujemy sprzeczność.

%Sposób 2. Niech w będzie najmniejszą liczbą naturalną większą od jedności taką, że n | 2^n - 1, zaś k- dowolną liczbą naturalną taką, że n | 2k - 1 i k < n. Niech d będzie największym wspólnym dzielnikiem liczb n i k. Na mocy twierdzenia danego do dowodu w za-
%daniu przygotowawczym B serii II istnieją takie liczby naturalne a i b, że ąn - bk = d. Ponieważ n | 2an - 1 i n | 2ik - 1, więc n | 2an - - 2bk = 2M(2 %Zatem n j 21 - 1 i n = 1. Otrzymujemy sprzeczność.
%Sposób 3. Niech n > 1 będzie dowolną liczbą naturalną taką, że n | 2^n - 1, zaś p - jej najmniejszym dzielnikiem pierwszym. Na mocy twierdzenia danego do dowodu w zadaniu 9 na zawodach stopnia I lub na mocy małego twierdzenia Fermata mamy p | 2k - 1, gdzie k jest pewną liczbą naturalną mniejszą od p. Z określenia liczby p wynika, że liczby k i n są względnie pierwsze. Zatem na mocy twierdzenia danego do dowodu w zadaniu przygotowawczym B serii II istnieją takie liczby naturalne a i b, że an - bk - 1. Ponieważ p | 2an - 1 i p|2bk -|, więc p | 2™ - 2hk = 2bh, czyli p = 2. Otrzymaliśmy sprzeczność, ponieważ n jest liczbą nieparzystą.