Feladat: F.2622 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Balogh Á. ,  Bánkövi Johanna ,  Beke T. ,  Benczúr A. ,  Bereczky Á. ,  Binder Zsuzsanna ,  Bukszár J. ,  Cynolter G. ,  Eckert B. ,  Fabó Gy. ,  Gács A. ,  Gyuris V. ,  Hadnagy É. ,  Hajdú Gabriella ,  Hajnal Zs. ,  Hutai Zs. ,  Jalsovszky P. ,  Károlyi 231 Enikő ,  Károlyi Gy. ,  Klug R. ,  Kovács 123 L. ,  Kovács 969 T. ,  László A. ,  Lipták 182 L. ,  Lipták Á. ,  Lozsi I. ,  Madas P. ,  Magyar Zs. ,  Mátrai K. ,  Nagy 124 G. ,  Paál B. ,  Pál G. ,  Pongor G. ,  Rimányi R. ,  Szabó 486 P. ,  Szalay Gy. ,  Szederkényi Judit ,  Szegedi Nóra ,  Szokoly Gy. ,  Talata I. ,  Tasnádi T. ,  Tóth 178 G. ,  Wiandt T. ,  Zaránd G. ,  Zsigmond L. 
Füzet: 1987/október, 299. oldal  PDF file
Témakör(ök): Euler-Fermat-tételek, Oszthatósági feladatok, Szorzat, hatvány számjegyei, Feladat
Hivatkozás(ok):Feladatok: 1987/február: F.2622

Melyek azok a természetes számok, amelyeknek bármilyen a számjegy esetén van olyan egész számú többszörösük, amelynek minden jegye a?

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.

Elegendő megkeresnünk azokat a természetes számokat, amelyeknek van olyan többszöröse, amelynek minden jegye 1. Ekkor és csak ekkor lesz ugyanis bármilyen a számjegy esetén is olyan többes, amelynek minden jegye a.
A páros, illetve az 5-tel osztható számoknak nyilván nincs csupa egyesből álló többszöröse, hiszen a páros számok utolsó jegye páros, az 5-tel oszthatók többszörösei pedig 0-ra vagy 5-re végződnek. Állítjuk, hogy e két esettel minden kivételt megtaláltunk, azaz ha egy N természetes szám relatív prím a 10-hez, akkor van olyan többszöröse, amelynek minden jegye 1-es.
Ha Um jelöli az m jegyű, csupa 1-esből álló számot, akkor tekintsük az U1,U2,... számoknak az N-nel való osztáskor fellépő maradékait. Mivel a lehetséges maradékok száma N, van olyan Um és Un (m<n), amelyek ugyanazt a maradékot adják N-nel osztva. Ez azt jelenti, hogy N|Un-Um=Un-m10m. Mivel pedig (N,10)=1, ezért a talált oszthatóságban a 10m tényező ,,leválasztható'', N|Un-m, tehát az n-m darab 1-esből álló szám az N-nek többszöröse. Ezzel a megoldást befejeztük.

 

Megjegyzés. Több megoldó észrevette, hogy a fenti megoldásban megfogalmazott állítás következik Euler (kongruencia-) tételéből, illetve az úgynevezett Kis-Fermat-tételből.
Hasonlóan mutatható meg, hogy az n alapú számrendszerben minden n-hez relatív prím N számnak van olyan többszöröse, amelynek minden jegye 1.