Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4272. feladat (2010. május)

B. 4272. Az (an) sorozat elemei pozitív egész számok és minden n\ge1 esetén an+1=an2+5an+1 teljesül. Lehet-e a sorozat összes tagja összetett szám?

(5 pont)

A beküldési határidő 2010. június 10-én LEJÁRT.


Megoldás. Az \(\displaystyle (x_n)\) sorozatot nevezzük nak, ha \(\displaystyle x_1\) nemnegatív egész szám és minden \(\displaystyle n\ge 1\) esetén \(\displaystyle x_{n+1}= x_n^2+ 5x_n+1\) teljesül, ekkor \(\displaystyle x_n\) elemei nemnegatív egész számok szigorúan növő sorozatát alkotják. Világos, hogy ha az \(\displaystyle (x_n)\) sorozat jó, akkor minden rögzített \(\displaystyle k\) nemnegatív egész esetén az \(\displaystyle x'_n=x_{n+k}\) képlet által definiált \(\displaystyle (x'_n)\) sorozat is jó. Továbbá, ha \(\displaystyle (x_n)\) és \(\displaystyle (y_n)\) is jó sorozat és \(\displaystyle x_n\equiv y_n\pmod{N}\) teljesül valamely \(\displaystyle n,N\) pozitív egészekre, akkor \(\displaystyle x_i\equiv y_i\pmod{N}\) teljesül minden \(\displaystyle i\ge n\) esetén.

Tekintsük azt a \(\displaystyle (b_n)\) jó sorozatot, amelyre \(\displaystyle b_1=0\), ekkor \(\displaystyle b_2=1\), \(\displaystyle b_3=7\), \(\displaystyle b_4=85=5\cdot 17\). A fenti észrevételek szerint, ha az az \(\displaystyle (a_n)\) jó sorozat valamelyik eleme 7-tel osztva 0 vagy 1 maradékot ad, akkor attól kedve a sorozat elemei 7-tel osztva felváltva 0, illetve 1 maradékot adnak. Hasonlóképpen, ha a sorozat valemelyik eleme 5-tel (17-tel) osztva 0, 1 vagy 2 (0, 1 vagy 7) maradékot ad, akkor attól kezdve a sorozat elemeinek 5-tel (17-tel) való osztási maradéka olyan sorozatot eredményez, amelyben a 0, 1, 2 (0, 1, 7) számok ismétlődnek periodikusan. így például az \(\displaystyle a_1\) számot úgy választva, hogy az 7-tel osztva 1 maradékot adjon, könnyen elérhetjük, hogy a sorozat páros indexű tagjai mind oszthatók legyenek 7-tel. Ha arra is ügyelünk, hogy \(\displaystyle a_1\) 5-tel osztva is 1 maradékot adjon, akkor az is igaz lesz, hogy az \(\displaystyle a_{3k}\) elemek mind oszthatók 5-tel, ha pedig azt is megköveteljük, hogy \(\displaystyle a_1\) 17-tel osztva 7 maradékot adjon, akkor az \(\displaystyle a_{3k+2}\) elemek mind oszthatók lesznek 17-tel. Ha a sorozat minden eleme nagyobb, mint 17, akkor (feltéve, hogy mindez egyszerre garantálható) elérhetjük, hogy az \(\displaystyle a_{6k+1}\) elemek kivételével a sorozat minden eleme összetett szám legyen. Ezt pedig tényleg garantálhatjuk, ha \(\displaystyle a_1\)-et olyan pozitív egésznek választjuk, amely \(\displaystyle 35\cdot 17=595\)-tel osztva \(\displaystyle 595-34=561\) maradékot ad.

Ilyen választás mellett persze az \(\displaystyle a_{6k+1}\) elemek sem 5-tel, sem 7-tel, sem pedig 17-tel nem lesznek oszthatók. Nézzük meg azonban a fenti sorozat \(\displaystyle b_7\) elemét. Ez nyilván osztható 5-tel, 7-tel és 17-tel is. Azt állítjuk, hogy ezeken felül még legalább egy további \(\displaystyle p\) prímszámmal is osztható. Mivel \(\displaystyle b_7>b_4=7651>595\), ehhez csak azt kell látnunk, hogy \(\displaystyle b_7\) nem osztható sem \(\displaystyle 5^2\)-nel, sem \(\displaystyle 7^2\)-nel, sem pedig \(\displaystyle 17^2\)-nel. Mivel \(\displaystyle b_5\equiv 1\equiv b_2\pmod{25}\), látható, hogy \(\displaystyle b_7\equiv b_4\equiv 10\pmod{25}\), tehát \(\displaystyle b_7\) valóban nem osztható 25-tel. Modulo 49 számolva \(\displaystyle b_4\) 36, \(\displaystyle b_5\) pedig 7 maradékot ad, ugyanúgy, mint \(\displaystyle b_3\), és így \(\displaystyle b_7\) is 7 maradékot kell adjon. Végül modulo 289 számolva \(\displaystyle b_5\equiv 137\), \(\displaystyle b_6\equiv 92\), \(\displaystyle b_7\equiv 255\not\equiv 0\). Létezik tehát egy olyan \(\displaystyle p\ne 5,7,17\) prímszám, amely osztja a \(\displaystyle b_7\) számot. Ha tehát az \(\displaystyle a_1\) szám megválasztásánál ügyelünk arra, hogy az \(\displaystyle p\)-vel osztható legyen, akkor a sorozat összes \(\displaystyle a_{6k+1}\) alakú eleme osztható lesz \(\displaystyle p\)-vel.

Összefoglalva, ha az \(\displaystyle a_1>p\) szám a \(\displaystyle p\) prímnek olyan többszöröse, amely 595-tel osztva 561 maradékot ad, akkor az \(\displaystyle (a_n)\) jó sorozat valamennyi eleme összetett szám lesz. Minthogy azonban \(\displaystyle p\) relatív prím az 595-höz, a \(\displaystyle 2p, 3p,\ldots, 596p\) számok 595-tel osztva mind különböző maradékot adnak, melyek között elő kell forduljon az 561 is. Létezik tehát olyan jó sorozat, amelynek minden tagja összetett szám.


Statisztika:

17 dolgozat érkezett.
5 pontot kapott:Damásdi Gábor, Éles András, Janzer Olivér, Karkus Zsuzsa, Medek Ákos, Mester Márton, Mészáros András, Nagy Róbert, Perjési Gábor, Somogyi Ákos, Weisz Ágoston, Weisz Gellért.
4 pontot kapott:Dudás 002 Zsolt, Gyarmati Máté, Szabó 928 Attila, Tossenberger Tamás.
0 pontot kapott:1 versenyző.

A KöMaL 2010. májusi matematika feladatai