Feladat: N.118 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Braun Gábor ,  Frenkel Péter ,  Gerbicz Róbert ,  Gyenes Zoltán ,  Horváth Gábor ,  Juhász András ,  Kun Gábor ,  Lippner Gábor ,  Lukács László ,  Mátrai Tamás ,  Pap Gyula ,  Papp Dávid ,  Szabó Jácint ,  Terpai Tamás 
Füzet: 1997/április, 229 - 230. oldal  PDF  |  MathML 
Témakör(ök): Oszthatósági feladatok, Számjegyekkel kapcsolatos feladatok, Legnagyobb közös osztó, Nehéz feladat
Hivatkozás(ok):Feladatok: 1996/november: N.118

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.

Megmutatjuk, hogy megfelelő, csak 1-es és 2-es számjegyekből álló szám pontosan akkor létezik, ha d nem osztható 5-tel. Ha d osztható 5-tel, akkor d bármely többszöröse 0-ra vagy 5-re végződik, ezért nem állhat csupa 1-es és 2-es számjegyből.
Legyen d21996=2np, ahol p páratlan, 5-tel nem osztható egész. Az F. 3084. feladat megoldásában (KöMaL 1996/2. szám, 97. oldal) bebizonyítottuk, hogy tetszőleges n pozitív egészhez létezik olyan pontosan n-jegyű, csupa 1-es és 2-es számjegyből álló szám, amely osztható 2n-nel. Legyen ez a szám A.
Megmutatjuk, hogy létezik olyan k pozitív egész, amelyre 1+10n+102n+...+10kn osztható p-vel. Tekintsük az 1, 1+10n, 1+10n+102n, ... számokat. Ezek között vannak olyanok, amelyek p-vel osztva azonos maradékot adnak, legyen két ilyen szám

1+10n+...+10k1nés1+10n+...+10k2n,
ahol k1<k2. Ekkor a két szám különbsége,
10(k1+1)n(1+10n+...+10(k2-k1-1)n)
osztható p-vel. Viszont p és 10(k1+1)n relatív prímek, ezért a második tényező osztható p-vel.
Tekintsük most az (1+10n+102n+...+10kn)A számot. Ez úgy keletkezik, hogy az A számot (k+1)-szer egymás után írjuk, tehát csupa 1-es és 2-es számjegyből áll; másrészt egy p-vel osztható és egy 2n-nel osztható szám szorzata, tehát osztható 2np-vel.