Feladat: B.3525 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bóka Gergely 
Füzet: 2002/december, 534 - 535. oldal  PDF file
Témakör(ök): Számsorozatok, Euler-Fermat-tételek, Lineáris kongruenciák, Feladat
Hivatkozás(ok):Feladatok: 2002/február: B.3525

Bizonyítsuk be, hogy az 1,31,331,3331,... sorozatban végtelen sok összetett szám van.

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.

I. megoldás. A 31 prímszám, azért a ,,kis'' Fermat-tétel szerint osztója a 1030-1 számnak. Mivel (1030)k-1k osztható (1030-1)-gyel, azért a 31 osztója az összes 1030k-1 alakú számnak is (k tetszőleges pozitív egész). Osztója tehát ezen számok harmadrészének is, vagyis minden olyan számnak, ami 30k darab 3-as számjegyből áll. Egy ilyen számot 100-zal megszorozva, majd az eredményhez 31-et hozzáadva újfent 31-gyel osztható számhoz jutunk, és minden ilyen szám a megadott sorozathoz tartozik. Ezek szerint 31-től kezdve a sorozat minden 30-adik eleme osztható 31-gyel, ezek tehát a 31 kivételével valamennyien összetettek. Ezzel beláttuk, hogy a sorozatban végtelen sok összetett szám van.

 
Megjegyzés. A ,,kis'' Fermat-tételt számos számelmélettel foglalkozó könyvben megtalálhatjuk, például Dr. Szalay Mihály: Számelmélet című tankönyvében is.
 
II. megoldás. Az 1,31,331,3331,... sorozatban végtelen sok olyan elem van, amelyben 16k+8 darab 3-as van. Tekintsük ezeket az elemeket:
333...33316k+8db1=999...99916k+8db33=999...999916k+9db-63=1016k+9-1-63=1016k+9-73.

Ha belátjuk, hogy 171016k+9-7, akkor (3;17)=1 miatt 1016k+9-73 is osztható 17-tel, azaz 17333...33316k+81 is fennáll. Ehhez igazolni kell, hogy 1016k+97mod17.
A kongruencia szabályait felhasználva:
1016k+9=109(1016)k=10003(100004)k==(5817+14)3((58817+4)4)k143(44)k==(16117+7)(1517+1)k71k=7(mod17).
Tehát 1016k+9-70(mod17), így 17333...33316k+81 minden k-ra. A sorozatnak végtelen sok eleme osztható 17-tel, ezért végtelen sok eleme összetett.
Bóka Gergely (Szolnok, Verseghy Ferenc Gimn., 11. évf.)