L MOM - Zadanie 1

Zawody matematyczne:

L MOM, 2009

Dana jest dodatnia liczba całkowita $n$ oraz parami różne liczby całkowite $a_1,\dots,a_k$ ( $k\geq2$ ), będące elementami zbioru $\{1,\dots,n\}$ . Ponadto, dla każdego $i=1,\dots,k-1$ , liczba $n$ jest dzielnikiem liczby $a_i(a_{i+1}-1)$ . Udowodnić, że $n$ nie jest dzielnikiem liczby $a_k(a_1-1)$ .

Rozwiązanie

Podane w treści zadania podzielności można zapisać w postaci kongruencji:

$ a_ia_{i+1}\equiv a_i\pmod n\quad\text{dla }i=1,2,\dots,k-1. $

Wynika z nich, że

$ (1) \qquad a_1a_2\dots a_{k-1}a_k\equiv a_1a_2\dots a_{k-1}\equiv\dots\equiv a_1\pmod n. $

Aby przeprowadzić dowód nie wprost, załóżmy, że liczba $n$ dzieli iloczyn $a_k(a_1-1)$ , czyli $a_ka_1\equiv a_k\pmod n$ . Wówczas

$ (2) \begin{split} a_1a_2\dots a_k &= a_ka_1\dots a_{k-2}a_{k-1}\equiv a_ka_1\dots a_{k-2} \\ \equiv\dots &\equiv a_ka_1\equiv a_k\pmod n. \end{split} $

Z (1) i (2) wynika, że $a_1\equiv a_k\pmod n$ . To jest jednak niemożliwe, gdyż $a_1,a_k\in\{1,\dots,n\}$ oraz $a_1\neq a_k$ . Uzyskana sprzeczność dowodzi, że liczba $n$ nie dzieli iloczynu $a_k(a_1-1)$ .