Feladat: N.182 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csirmaz Előd ,  Dancsó Zsuzsanna ,  Dezső Balázs ,  Gerbicz Róbert ,  Gyenes Zoltán ,  Harangi Viktor ,  Horváth Gábor ,  Iván Szabolcs ,  Juhász András ,  Keszegh Balázs ,  Kiss Gergely ,  Kunszenti-Kovács Dávid ,  Lukács László ,  Mansur Boase ,  Máthé András ,  Mecz Balázs ,  Naszódi Gergely ,  Pálvölgyi Dömötör ,  Pataki Péter ,  Szakács László ,  Székelyhidi Gábor ,  Terpai Tamás ,  Tran Thanh Long ,  Végh A. László ,  Zábrádi Gergely 
Füzet: 1999/március, 164 - 166. oldal  PDF file
Témakör(ök): Rekurzív sorozatok, Természetes számok, Oszthatósági feladatok, Nehéz feladat
Hivatkozás(ok):Feladatok: 1998/szeptember: N.182

Határozzuk meg az összes olyan a, b pozitív egész számokból álló párt, amelyre a osztója (b2+b+1)-nek és b osztója (a2+a+1)-nek.

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.

Az a és b egymáshoz relatív prímek, hiszen pl. az a osztója a b-hez relatív prím (b2+b+1)-nek. Így az egyetlen olyan megoldás, amelyre a=b, az a=b=1. Tegyük fel ezután, hogy a<b, és ab+=b2+b+1, ba-=a2+a+1.
Ekkor bb+>ab+=b2+b+1>b(b+1) miatt b+>b, hasonlóan (a+1)a-ba-=a2+a+1<(a+1)(a+1) szerint a-a, és így ‐ mivel a- osztója az a-hoz relatív prím (a2+a+1)-nek ‐ a-<a vagy a-=a=1.
Megmutatjuk, hogy a, b-hez hasonlóan az a-, a és a b, b+ párok is eleget tesznek a feladat feltételeinek. Nyilván a-ba-=a2+a+1 és b+ab+=b2+b+1. Mivel a és b egymáshoz relatív prímek, elég igazolni, hogy

ab2(a-)2+a-+1)ésba2((b+)2+b++1).
Az első oszthatóság igazolásához használjuk ba-=a2+a+1-et:
b2((a-)2+a-+1)=(a2+a+1)2+b(a2+a+1)+b2=ax+(1+b+b2),
és ez valóban osztható a-val; hasonlóan láthatjuk be a második oszthatóság teljesülését is.
Tehát az a<b megoldásból ,,lefelé'' és ,,felfelé'' is tovább lépve megkaphatjuk az a-a<b<b+ sorozatot, amelynek bármely két szomszédos eleme megoldás, és ezt ugyanígy folytathatjuk tovább, mindkét irányban. Észrevehetjük, hogy a sorozatot bármelyik két szomszédos eleme már meghatározza, hiszen b+=b2+b+1a-hoz hasonlóan például b=a2+a+1b-.
Vizsgáljuk meg, hová jutunk, ha a<b-ből indulva a sorozatot ,,lefelé'' folytatjuk, ameddig csak lehetséges. Legyen a-1=a-=a2+a+ab, a-2=a-12+a-1+1a s.í.t. A sorozat ebben az irányban akkor ér véget, amikor a-(n+1)=a-n, azaz a-(n+1)=a-n=1. Ekkor a-(n-1)=a-n2+a-n1+1a-(n+1)=3, a-(n-2)=a-(n-1)2+a-(n-1)+1a-n=13 stb.; az a, b pár tehát két szomszédos eleme annak az x1<x2<... sorozatnak, amelyet az x1=1, x2=3, xi+1=xi2+xi+1xi-1 rekurzió definiál. Ennek a sorozatnak bármely két szomszédos eleme valóban megoldást ad, hiszen az (1,3) pár megoldás.
 
Megjegyzések. 1. A megoldás ötlete a következő gondolatból származik.
Ha az (a,b) számpár megoldás, akkor az a2+a+(b2+b+1)=(a2+a+1)+b2+b szám osztható a-val és b-val. Mivel a és b relatív prímek, ab-vel is osztható, vagyis egy megfelelő K pozitív egésszel
a2+b2+a+b+1=Kab.(1)
Ennek a megfordítása is igaz, ha az a, b, K pozitív egészekre (1) teljesül, akkor a2+a+1 osztható b-vel és b2+b+1 osztható a-val.
Tekintsük most a
t2-(Kb-1)t+(b2+b+1)=0
másodfokú egyenletet. Ennek egyik gyöke t1=a. A másik gyöke a ViŠta-formulák alapján
t2=(Kb-1)-a=b2+b+1a.
Az első felírásból látszik, hogy t2 egész szám, a másodikból pedig, hogy pozitív.
2. Az előbbi lépés többszöri megismétlésével az (1) egyenlet tetszőleges (a,b,K) megoldásából további megoldásokat állíthatunk elő. Könnyű meggondolni, hogy kellő számú lépést megtéve eljuthatunk az (1,1,K) megoldáshoz. Ebből következik, hogy csak K=5 lehetséges, és az (xn) sorozatot az
x0=x1=1,xn+1=5xn-xn-1-1(2)
rekurzióval is definiálhatjuk.
3. A (2) a rekurzióból xn explicit alakban is felírható:
xn=13+7-2121(5+212)n+7+2121(5-212)n.