XXI OM - I -Zadanie 9

Udowodnić, że dla każdej liczby nieparzystej $ n > 1 $ istnieje taka liczba naturalna $ d < n $, że liczba $ 2^d - 1 $ jest podzielna przez $ n $.

Rozwiązanie

Żadna z liczb $ 2, 2^2, \ldots, 2^n $ nie daje reszty $ 0 $ z dzielenia przez $ n $, ponieważ $ n > 1 $ i $ n $ jest liczbą nieparzystą.

Ponieważ liczb tych jest $ n $, a możliwych reszt różnych od zera jest $ n - 1 $, więc dwie liczby $ 2^r $ i $ 2^s $, gdzie $ 1 \leq r < s \leq n $, dają tę samą resztę z dzielenia przez $ n $. Zatem $ 2^s - 2^r $ dzieli się przez $ n $ i wobec tego liczba $ 2^r (2^{s-r} - 1) $ dzieli się przez $ n $. Ponieważ liczba $ n $ jest nieparzysta, więc wynika stąd, że liczba $ 2^{s-r} - 1 $ dzieli się przez $ n $. Wobec tego liczba $ d = s - r $ spełnia warunki zadania.

Komentarze

Dodaj nową odpowiedź