Problem B. 4272. (May 2010)

B. 4272. The terms of sequence (a_n) are positive integers, such that a_n+1=a_n²+5a_n+1 for all n $\ge$ 1. Is it possible that the terms of the sequence are all composite numbers?

(5 pont)

Deadline expired on June 10, 2010.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Az $\displaystyle (x_n)$ sorozatot nevezzük jó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.

Statistics:

17 students sent a solution.

5 points: 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 points: Dudás 002 Zsolt, Gyarmati Máté, Szabó 928 Attila, Tossenberger Tamás.

0 point: 1 student.

Problems in Mathematics of KöMaL, May 2010

17 students sent a solution.
5 points:	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 points:	Dudás 002 Zsolt, Gyarmati Máté, Szabó 928 Attila, Tossenberger Tamás.
0 point:	1 student.

Already signed up?
New to KöMaL?