Feladat: B.3859 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Blázsik Zoltán ,  Dányi Zsolt ,  Farkas Ádám László ,  Honner Balázs ,  Károlyi Márton ,  Kornis Kristóf ,  Kovács 111 Péter ,  Kovács 129 Péter ,  Kunovszki Péter ,  Kutas Péter ,  Mészáros Gábor ,  Nagy János ,  Szabó Tamás ,  Szaller Dávid ,  Szalóki Dávid ,  Szegvári Gábor ,  Szentandrási István ,  Szilágyi Csaba ,  Szücs Gergely ,  Tomon István ,  Tóthmérész Lilla ,  Udvari Balázs ,  Varga László ,  Varga Péter ,  Véges Márton 
Füzet: 2006/szeptember, 345 - 346. oldal  PDF file
Témakör(ök): Oszthatóság, Számsorozatok, Feladat
Hivatkozás(ok):Feladatok: 2005/november: B.3859

Keressük meg az összes olyan 1-nél nagyobb n természetes számot, amelyre az 1,2,3,...,n számoknak létezik olyan a1,a2,...,an sorrendje, hogy az a1, a1a2, a1a2a3, ..., a1a2an szorzatok mind különböző maradékot adnak n-nel osztva.

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.

Megoldás. Ha létezik ilyen sorrend, akkor szükségképpen a1=1 (különben valamelyik szorzat egyenlő lenne a rákövetkezővel) és an=n, mert ellenkező esetben egynél több szorzat is osztható lenne n-nel, azaz nulla maradékot adna n-nel osztva. Először megmutatjuk, hogy n nem lehet 4-nél nagyobb összetett szám. Tételezzük fel ugyanis, hogy 4<n=ab, ahol 2ab<n. Ekkor b>2 miatt 2a=2nb<n, így ab vagy 2ab folytán a1a2an-1 is nulla maradékot ad n-nel osztva, hiszen osztható ab-vel.
Az n tehát csak 4 vagy prímszám lehet. Az n=4-re egy alkalmas sorrend 1, 3, 2, 4. Megmutatjuk, hogy akkor is létezik megfelelő sorrend, ha n értéke prím. Legyen ekkor ‐ ahogy szükséges ‐ a1=1, an=n, az a2,...,an-1 számokat pedig úgy választjuk 2,3,...,n-1 közül, hogy ai(i-1)-nek az n-nel való osztási maradéka i legyen. Ez a következőképpen lehetséges: adott 2in-1 esetén szorozzuk meg az 1,2,...,n-1 számok mindegyikét (i-1)-gyel; mivel n prím, a kapott szorzatok egyike sem osztható n-nel, és mind különböző maradékot adnak. Ellenkező esetben, ha pl. ak(i-1) és at(i-1) ugyanazt a maradékot adná, akkor a különbségük, (ak-at)(i-1) osztható lenne n-nel; ez lehetetlen, mivel sem i-1, sem ak-at nem lehet n-nel osztható.
Így viszont az n-1 különböző nemnulla maradék között minden nemnulla maradék megtalálható, ezért i is. Abban is biztosak lehetünk, hogy az eképpen kapott ai szám nem az a1=1, hiszen akkor ai(i-1)=i-1 lenne, amelynek a maradéka nem i.
Ezután igazoljuk, hogy a különböző i sorszámokra kapott ai értékek mind különbözőek. Ha ugyanis valamilyen ij-re ai=aj=c (a1=1) adódna, akkor c(i-1)=ai(i-1) osztási maradéka i, c(j-1)=aj(j-1) osztási maradéka pedig j; így c(i-j)=c((i-1)-(j-1))=c(i-1)-c(j-1) osztási maradéka i-j lenne, azaz (c-1)(i-j)=c(i-j)-(i-j) osztható n-nel, ami lehetetlen.
Végül megmutatjuk, hogy az a2,...,an-1 számok ebben a sorrendben (előttük a1=1-gyel, utánuk legvégül pedig an=n-nel) teljesítik a feladat követelményeit. Az a1 maradéka 1, a1a2 maradéka 1a2 maradéka, azaz 2, a1a2a3 maradéka 2a3 maradéka, azaz 3 stb.: ha már tudjuk, hogy a1a2ak maradéka k (ahol k<n-1), akkor a1a2akak+1 maradéka kak+1 maradéka, azaz k+1. Végül a1a2an maradéka nyilván 0.