LX OM - I - Zadanie 2

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dana jest liczba całkowita $n \geq 2$ . Niech $r_1, r_2, r_3, \cdots, r_{n-1}$ będą odpowiednio
resztami z dzielenia liczb

$ 1, 1+2, 1+2+3, \cdots, 1+2+ \cdots +(n-1) $

przez $n$ . Znaleźć wszystkie takie wartości $n$ , że ciąg $(r_1,r_2,\cdots,r_{n-1})$ jest permutacją
ciągu $(1, 2, \cdots,n-1)$ .

Rozwiązanie

Odpowiedź: $n =2^k$ dla $k =1,2,3,\cdots$ .

Wykażemy najpierw, że potęgi dwójki spełniają warunki zadania.
W tym celu wystarczy udowodnić, że jeżeli $n =2^k$ dla pewnego całkowitego $k \geq 1$ , to reszty
$r_1, r_2, r_3, \cdots, r_n-1$ są parami różne i żadna z nich nie jest równa zeru. Gdyby któraś z
tych reszt, powiedzmy $r_m$ , była równa zeru, to liczba

$ 1+2+\cdots+m = \frac{m(m+1)}{2} $

byłaby podzielna przez $2^kk$ . Zatem dla pewnej wartości $m \in \{1,2, \cdots,2k - 1\}$ iloczyn
$m(m+1)$ byłby podzielny przez $2^{k+1}$ . Lecz jedna z liczb $m$ , $m+1$ jest
parzysta, a druga — nieparzysta. Stąd jedna z nich musiałaby być podzielna przez $2^{k+1}$ ,
wbrew temu, że obie te dodatnie liczby nie przekraczają $2^k$ . Gdyby z kolei dwie z rozważanych
reszt były równe — powiedzmy $r_l = r_m$ , gdzie $1 \leq l< m \leq n-1$ , wówczas liczba

$ (1+2+\cdots+m) - (1+2+\cdots+l) = \frac{m(m+1)}{2} - \frac{l(l+1)}{2} = \frac{(m-l)(m+l+1)}{2} $

byłaby podzielna przez $2^k$ , a więc iloczyn $(m -l)(m+l +1)$ byłby podzielny przez $2^{k+1}$ .
Suma tych czynników wynosi $2^{m+1}$ , jest więc liczbą nieparzystą. Tak jak wcześniej wynika stąd,
że jedna z liczb $m - l$ , $m + l + 1$ musi być podzielna przez $2^{k+1}$ . Jednakże liczby $l$ i $m$
są różne, dodatnie i mniejsze od $2^k$ , i podobnie jak poprzednio otrzymujemy sprzeczność.

Aby dokończyć rozwiązanie zadania, wystarczy dowieść, że gdy liczba $n$ ma nieparzysty dzielnik pierwszy $p$ ,
to ciąg $(r_1,r_2,\cdots,r_{n-1})$ nie jest permutacją ciągu $(1,2,\cdots,n - 1)$ . Zauważmy w tym celu, że
dla dowolnej liczby całkowitej dodatniej $t$ liczby

$ 1+2+...+(tp-2)+(tp-1) = \frac{tp(tp-1)}{2}, $

$ 1+2+...+(tp-1)+tp = \frac{tp(tp+1)}{2} $

są podzielne przez p, gdyż nieparzysty czynnik pierwszy p w liczniku nie skraca się z mianownikiem.
W związku z tym reszty

$ r_{p-1},r_p,r_{2p-1},r_{2p},r_{3p-1},r_{3p}, \cdots, r_{n-p-1}, r_{n-p},r_{n-1} $

są podzielne przez p. Zatem w ciągu $(r_1,r_2,\cdots,r_{n-1})$ co
najmniej $2\cdot \frac{n}{p}-1$ liczb jest podzielnych przez $p$ .
W ciągu (1,2, \cdots,n-1) występuje zaś jedynie $n-1$ liczb podzielnych
przez $p$ . Tak więc liczba $n$ nie ma żądanej własności