XXI OM - II -Zadanie 3

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ą.

Komentarze

Dodaj nową odpowiedź