Kezdőlap


Feladat:	2009. évi Nemzetközi Matematika Diákolimpia 11. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Nagy Dániel
Füzet:	2009/október, 388. oldal		PDF \| MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Számsorozatok, Oszthatóság, Maradékos osztás, kongruenciák
Hivatkozás(ok):	Feladatok: 2009/szeptember: 2009. évi Nemzetközi Matematika Diákolimpia 11. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Nagy Dániel megoldása. $n ∣ a_{i} (a_{i + 1} - 1)$ azt jelenti, hogy

\begin{matrix} a_{i} \equiv a_{i} a_{i + 1} (mod n) . \end{matrix}

(1)

Ezt felhasználva:

\begin{matrix} a_{1} a_{k} \equiv a_{1} a_{2} a_{k} \equiv a_{1} a_{2} a_{3} a_{k} \equiv ... \equiv a_{1} a_{2} ... a_{k - 1} a_{k} (mod n) . \end{matrix}

Az (1) alapján újra kapjuk, hogy

\begin{matrix} a_{1} a_{2} ... a_{k - 1} a_{k} \equiv a_{1} a_{2} ... a_{k - 1} \equiv a_{1} a_{2} ... a_{k - 2} \equiv ... \equiv a_{1} a_{2} \equiv a_{1} (mod n) . \end{matrix}

A fentiekből következik, hogy

\begin{matrix} a_{1} a_{k} \equiv a_{1} (mod n) . \end{matrix}

(2)

A bizonyítandó állítás szerint

n ∤ a_{k} (a_{1} - 1)

. Felhasználva (2)-t:

\begin{matrix} a_{k} (a_{1} - 1) = a_{1} a_{k} - a_{k} \equiv a_{1} - a_{k} (mod n) . \end{matrix}

Mivel

0 < | a_{1} - a_{k} | < n

, tehát az

n

-nel való osztási maradék 0-nál nagyobb, így

n ∤ a_{k} (a_{1} - 1)