Feladat: F.2369 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Alberti G. ,  Almássy T. ,  Böröczky K. ,  Danyi P. ,  Engländer J. ,  Erdős L. ,  Fekete Gy. ,  Hetyei G. ,  Holbok I. ,  Lenkó Cs. ,  Mikó Teréz ,  Mohay T. ,  Nagy 348 R. ,  Nyikes P. ,  Papp 193 G. ,  Peták T. ,  Pintér G. ,  Sigray I. ,  Simák Gy. ,  Szemők Á. ,  Tranta Beáta ,  Törőcsik J. ,  Török Zs. ,  Weisz F. ,  Zieger B. 
Füzet: 1983/január, 8 - 9. oldal  PDF file
Témakör(ök): Prímszámok, Feladat, Számsorozatok
Hivatkozás(ok):Feladatok: 1982/május: F.2369

A 7,37,337,3337,33337 számok mind prímek. Igaz-e, hogy ezt a sorozatot tovább folytatva mindig prímszámot kapunk ? Mi a helyzet a 31,331,3331,... sorozattal ?

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 feladat szövegében szereplő állítás nem igaz, hiszen sem 3337, sem 33337 nem prím: 3337=4771, 33337=173753. A sorozatot tovább folytatva sem kapunk mindig prímet. Mivel 333333 osztható 7-tel (prímfelbontása 337111337), azért 3333337=10333333+7 is osztható 7-tel. Általában a sorozatnak azok a tagjai, melyek alakja

3333336 db3333336 db...3333336 db7,
szintén oszthatók 7-tel, tehát nem lehetnek prímek.
Ahhoz, hogy a második sorozatban is végtelen sok összetett számot találunk, elegendő megmutatnunk, hogy valamilyen k-ra a k darab hármassal leírt szám osztható 31-gyel, hiszen ekkor a
33...3k db33...3k db...33...3k db31
szám szintén osztható 31-gyel s így (lévén nagyobb, mint 31) nem prímszám.
Tekintsük az alábbi számokat:
a1=3,a2=33,...,a32=3(32 db 3-as).
Mivel 31-gyel való osztáskor összesen 31 különböző maradék lehetséges, és nekünk 32 darab számunk van, akad közöttük kettő, ai és aj (i<j), melyek különbsége osztható 31-gyel. Ámde ha 31 osztója az
aj-ai=aj-i10j-i
számnak, akkor 31 osztója aj-i-nek is, hiszen 31 prímszám, és a szorzat második tényezője, 10j-i, nem osztható 31-gyel. Ez pedig azt jelenti, hogy a (j-i) darab hármasból álló szám osztható 31-gyel, ahogyan azt kívántuk.
 

Megjegyzés. Kellő (?) türelemmel ellenőrizhető, hogy a1, a2, ..., a14 egyike sem osztható 31-gyel, míg a15=333333333333333 igen, s így a második sorozat 16-ik tagja, 33333333333333331 biztosan nem prím. Szintén belátható, hogy a második sorozat egyik tagja sem osztható a 2,3,5,7,11 és 13 számok egyikével sem; továbbá az első 17-tel osztható tag 333333331.