L MOM - Zadanie 1

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:

\[<br /> a_ia_{i+1}\equiv a_i\pmod n\quad\text{dla }i=1,2,\dots,k-1.<br /> \]

Wynika z nich, że

\[<br /> (1) \qquad<br /> a_1a_2\dots a_{k-1}a_k\equiv a_1a_2\dots a_{k-1}\equiv\dots\equiv a_1\pmod n.<br /> \]

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

\[<br /> (2)<br /> \begin{split}<br /> a_1a_2\dots a_k &= a_ka_1\dots a_{k-2}a_{k-1}\equiv a_ka_1\dots a_{k-2} \\<br /> \equiv\dots &\equiv a_ka_1\equiv a_k\pmod n.<br /> \end{split}<br /> \]

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) $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź