LVIII OM - I - Zadanie 8

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

\[<br />
x_1,\;\;\; x_1x_2,\;\;\; x_1x_2x_3,\;\;\; \ldots,\;\;\; x_1x_2...x_{p-1}<br />
\]

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

\[<br />
(i-1)-i,\;\;\; 2(i-1)-i,\;\;\; 3(i-1)-1, \;\;\;\ldots,<br />
\;\;\; (p-1)(i-1)-1.<br />
\]

Ż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

\[<br />
(l(i-1)-i)-(k(i-1)-i)=(l-k)(i-1)<br />
\]

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

\[<br />
((j-1)x_i-j)-((i-1)x_i-i)=(j-i)(x_i-1)<br />
\]

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

\[<br />
x_1=1 \qoraz (i-1)x_i\equiv i\pmod{p}\dla i=2,3,\ldots,p-1.<br />
\]

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

\[<br />
ij-i\equiv i(j-1)\equiv (i-1)(j-1)x_i\equiv (i-1)(j-1)x_j\equiv (i-1)j<br />
\equiv ij-j\pmod{p},<br />
\]

co daje oczywistą sprzeczność $ i\equiv j\!\!\!\pmod{p} $. Pozostaje sprawdzić, że dla $ i=2,3,\ldots,p-1 $ mamy

$$(i-1)!\cdot x_1x_2...x_i\equiv x_2\cdot 2x_3\cdot 3x_4\cdot ... (i-1)x_i\equiv 2\cdot 3\cdot 4\cdot... i=(i-1)!\cdot i\pmod{p},$$

a więc $ x_1x_2...x_i\equiv i\!\!\!\pmod{p} $.

Komentarze

Dodaj nową odpowiedź