LVIII OM - I - Zadanie 8

Zawody matematyczne:

LVIII OM, 2006-2007

Etap:

Niech $p$ będzie liczbą pierwszą. Dowieść, że istnieje taka permutacja $(x_1,x_2,\ldots,x_{p-1})$ zbioru $\{1,2,\ldots,p{-}1\}$ , że liczby

$ x_1,\;\;\; x_1x_2,\;\;\; x_1x_2x_3,\;\;\; \ldots,\;\;\; x_1x_2...x_{p-1} $

dają różne reszty przy dzieleniu przez $p$ .

Rozwiązanie

Przyjmijmy $x_1=1$ oraz dla $i=2,3,\ldots,p{-}1$ niech $x_i$ będzie taką liczbą ze zbioru $\{1,2,\ldots,p{-}1\}$ , że liczba $(i-1)x_i-i$ jest podzielna przez $p$ .

Oczywiście musimy najpierw wykazać, że podane określenie liczby $x_i$ jest poprawne, czyli że taka liczba $x_i$ istnieje. W tym celu dla ustalonej wartości $i\in\{2,3,\ldots,p-1\}$ rozpatrzmy liczby

$ (i-1)-i,\;\;\; 2(i-1)-i,\;\;\; 3(i-1)-1, \;\;\;\ldots, \;\;\; (p-1)(i-1)-1. $

Żadna z tych liczb nie daje reszty $p-i$ przy dzieleniu przez $p$ ; gdyby bowiem dla pewnego $k\in\{1,2,\ldots,p{-}1\}$ liczba $k(i-1)-i$ dawała resztę $p-i$ , to liczba $k(i-1)$ byłaby podzielna przez $p$ , co jest niemożliwe wobec nierówności ${0<k<p}$ , $0<i-1<p-1$ oraz faktu, iż $p$ jest liczbą pierwszą. Analogicznie dowodzimy, że jeśli $k$ , $l$ są liczbami całkowitymi spełniającymi nierówności $1\le k<l\le p-1$ , to liczba

$ (l(i-1)-i)-(k(i-1)-i)=(l-k)(i-1) $

nie jest podzielna przez $p$ . To oznacza, że wśród wypisanych $p-1$ liczb żadne dwie nie dają tej samej reszty z dzielenia przez $p$ oraz żadna nie daje reszty $p-i\ne 0$ . Wynika stąd, że dokładnie jedna z tych liczb daje resztę $0$ , czyli dzieli się przez $p$ .

Udowodnimy teraz, że otrzymane w ten sposób liczby $x_1$ , $x_2$ , $\ldots$ , $x_{p-1}$ są parami różne. Żadna z liczb $x_2$ , $x_3$ , $\ldots$ , $x_{p-1}$ nie jest równa $x_1=1$ , gdyż liczba $(i-1)\cdot 1-i=-1$ nie jest podzielna przez $p$ . Przypuśćmy z kolei, że dla pewnych wskaźników $2\le i<j\le p-1$ zachodzi równość $x_i=x_j$ . Wtedy liczby $(j-1)x_i-j$ oraz $(i-1)x_i-i$ są podzielne przez $p$ , a więc różnica

$ ((j-1)x_i-j)-((i-1)x_i-i)=(j-i)(x_i-1) $

dzieli się przez liczbę pierwszą $p$ , co jest niemożliwe, gdyż $0<j-i<p-1$ , jak również $0<x_i-1<p-1$ .

Pozostaje wykazać, że skonstruowane liczby spełniają warunki zadania. W tym celu wykażemy indukcyjnie, że dla $i=1,2,\ldots,p-1$ liczba $x_1x_2...x_i$ daje resztę $i$ z dzielenia przez $p$ . Dla $i=1$ jest to prawda. Załóżmy teraz prawdziwość tej własności dla $i-1$ . Liczba $x_1x_2...x_{i-1}-(i-1)$ jest zatem podzielna przez $p$ , a więc i liczba $x_1x_2...x_{i-1}x_i-(i-1)x_i$ dzieli się przez $p$ . Ale z określenia liczby $x_i$ wynika, że liczba $(i-1)x_i$ daje resztę $i$ przy dzieleniu przez $p$ . Wobec tego liczba $x_1x_2...x_i$ daje resztę $i$ z dzielenia przez $p$ , co kończy dowód indukcyjny i rozwiązanie zadania.

Uwaga: Znajomość podstawowych własności arytmetyki liczb modulo $p$ pozwala znacznie uprościć zapis powyższego rozumowania. Mianowicie przyjmujemy

$ x_1=1 \qoraz (i-1)x_i\equiv i\pmod{p}\dla i=2,3,\ldots,p-1. $

Ponieważ $p$ jest liczbą pierwszą, więc określenie liczby $x_i$ jest poprawne. Jest jasne, że liczby $x_2$ , $x_3$ , $\ldots$ , $x_{p-1}$ są różne od $x_1=1$ ; ponadto równość $x_i=x_j$ dla pewnych $2\le i<j\le p-1$ prowadziłaby do zależności

$ ij-i\equiv i(j-1)\equiv (i-1)(j-1)x_i\equiv (i-1)(j-1)x_j\equiv (i-1)j \equiv ij-j\pmod{p}, $