XXI OM - I -Zadanie 9

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

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.