Feladat: B.4272 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Nagy Róbert 
Füzet: 2011/február, 89 - 90. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Rekurzív sorozatok, Oszthatóság, Maradékos osztás, kongruenciák, Konstruktív megoldási módszer
Hivatkozás(ok):Feladatok: 2010/május: B.4272

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.

Megoldás. Nézzünk néhány elemet a sorozat elejéről, ha a kezdő elem 0:

a'1=0,a'2=1,a'3=7,a'4=85=5⋅17,a'5=7651=7⋅1093,a'6=58537801+38255+1=58576057,a'7=3431154453667249+292880285+1=3431154746547535==5766646632853⋅5⋅7⋅17.
Az utolsó számnál az 5 766 646 632 853 nem osztható az 5, 7, 17, 1093 egyikével sem, így van még ezeken kívül legalább egy prímosztója.
Mivel ‐ a rekurzió miatt ‐ a sorozat bármely elemének egy adott számmal való osztási maradéka kizárólag az őt közvetlenül megelőző elem osztási maradékától függ láthatjuk, hogy ha egy ilyen sorozat k-adik eleme, ak osztható 7-tel, akkor a k+2t-edik elemek mindegyike osztható 7-tel, hiszen ekkor az ak szám 7-es maradéka megegyezik a fenti a'1=0 kezdőelem 7-es maradékával, így az ak+2 7-es maradéka megegyezik a fenti a'3=7 maradékával stb. Hasonló állítás érvényes 7 helyett bármilyen számra, például az 5-nél és a 17-nél minden harmadik tag adja ugyanazt a maradékot, az M=5766646632853 pedig minden hatodik lépésben jelenik meg.
Az eddigi észrevételek alapján olyan sorozatot készítünk, amelynek mindegyik eleme (valódi módon) osztható az 5, 7, 17, M számok valamelyikével. Megfigyeléseink szerint elegendő, ha ez a sorozat első hat tagjára teljesül (a valódi oszthatóságot az biztosítja a továbbiakban is, hogy a sorozat szigorúan monoton nő). Ehhez a kezdőtagot kell alkalmasan megválasztani. Tekintsük a következő táblázatot:
 
5 és 7    17  M   1    7  0  7  5⋅17     15⋅17   7⋅1093     7  7⋅1093     58 576 057  5⋅1758 576 057  5⋅7⋅17⋅M   7⋅1093   5⋅7⋅17⋅M   ...     58 576 057...   ...   5⋅7⋅17⋅M

 

Táblázatunk szerint, ha a sorozat kezdőtagja 5-tel és 7-tel osztva 1-et, 17-tel osztva 7-et ad maradékul és osztható M-mel, akkor az 1., 2., 3., 4., 5., 6. tag rendre osztható lesz M-mel, 7⋅17-tel, 5-tel, 7-tel, 17-tel, 5⋅7-tel.
Tehát elegendő, ha a sorozat első eleme olyan A pozitív egész, amely 5-tel és 7-tel osztva 1-et, 17-tel osztva 7-et ad maradékul és osztható 2M-mel. Az 5, 7, 17 és 2M számok páronként relatív prímek, ezért a kínai maradéktétel szerint létezik ilyen A. Nyilván (2M∣A miatt) az A összetett szám, a sorozat többi eleme pedig azért összetett, mert osztható az említett számokkal, és nagyobb A-nál.
 
Megjegyzés. A kínai maradéktétel a következőt állítja: ha az m1, m2, ..., mk egészek páronként relatív prímek, és c1, c2, ..., ck tetszőleges egész számok, akkor létezik olyan (pozitív) egész szám, amelynek mi-vel való osztási maradéka megegyezik a ci osztási maradékával (minden 1≤i≤k-ra).