Feladat: 1978. évi Nemzetközi Matematika Diákolimpia 11. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1978/október, 49. oldal  PDF  |  MathML 
Témakör(ök): Maradékos osztás, Oszthatósági feladatok, Tizes alapú számrendszer, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 1978/szeptember: 1978. é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.

A feltétel akkor és csak akkor teljesül, ha

1978n-1978m=1978m(1978n-m-1)(*)
osztható 1000-rel, azaz ha osztható külön-külön 8-cal és 125-tel is. Az n>m feltétel miatt (*) jobb oldalán a második tényező páratlan, és így 8-cal akkor és csak akkor osztható, ha m≥3.
A 125-tel való oszthatósághoz vizsgáljuk először 1978a utolsó jegyét a=1,2,... értékekre. Ezek rendre 8,4,2,6,8,4,2,6,... azaz négyes periódust alkotnak. Így 1978a-1 akkor és csak akkor osztható 5-tel, ha a osztható 4-gyel. Az 19784b=...256b utolsó két számjegye ötös periódust alkot: 56,36,16,96,76,56,36,... tehát 19784b-1 pontosan akkor osztható 25-tel, ha b többszöröse 5-nek. Végül 197820c=...2565c=...776c utolsó három jegyét vizsgálva először c=5 esetén kapunk 125-tel osztható végződést.
Ez azt jelenti, hogy ha 1978n-m-1 osztható 125-tel, akkor n-m értékének legalább 100-nak kell lennie. Ezt az előző m≥3 feltétellel összevetve azonnal látható, hogy a keresett értékek m=3 és n=103.
 

Megjegyzés. A feladat megoldásához felhasználhatjuk az ún. Euler-tételt: ha a és k relatív prímek, és φ(k)-val jelöljük a k-nál kisebb, k-hoz relatív prím egészek számát, akkor aφ(k)-1 osztható k-val. (Lásd például Molnár Emil: Matematikai versenyfeladatok, 488. oldal.) Mivel φ(125)=100 és 1978 és 125 relatív prímek, azért 1978100-1 osztható 125-tel. Ez azonban nem jelenti azt, hogy 100 a legkisebb ilyen kitevő, noha a feladat éppen a legkisebbet kérdezte.