Problem A. 691. (February 2017)
A. 691. Let \(\displaystyle c\ge3\) be an integer, and define the sequence \(\displaystyle a_1,a_2,\dots\) by the recurrence \(\displaystyle a_1=c^2-1\), \(\displaystyle a_{n+1}=a_n^3-3a_n^2+3\) \(\displaystyle (n=1,2,\ldots)\). Show that for every integer \(\displaystyle n\ge2\), the number \(\displaystyle a_n\) has a prime divisor that does not divide any of \(\displaystyle a_1,\ldots,a_{n-1}\).
(5 pont)
Deadline expired on March 10, 2017.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Először a sorozat következő tulajdonságait bizonyítjuk:
(1) \(\displaystyle a_n\ge4\) minden pozitív egész \(\displaystyle n\)-re;
(2) \(\displaystyle a_n\) nem osztható \(\displaystyle 9\)-cel, ha \(\displaystyle n\ge 2\);
(3) \(\displaystyle a_n\equiv 3\pmod{a_k}\) bármilyen \(\displaystyle n>k\) pozitív egész pár esetén.
Az (1) bizonyítása triviális \(\displaystyle n\) szerinti indukcióval: \(\displaystyle n=1\)-re \(\displaystyle a_n=a_1=c^2-1\ge 3^2-1>4\). Ha pedig valamely \(\displaystyle n\)-re \(\displaystyle a_n\ge4\), akkor
\(\displaystyle a_{n+1} = a_n^3-3a_n^2+3 = a_n^2(a_n-3)+3 > 1+3 = 4. \)
A (2) bizonyításához írjuk fel a rekurzót \(\displaystyle (n-1)\)-re:
\(\displaystyle a_n = a_{n-1}^2(a_{n-1}-3)+3. \)
Ha \(\displaystyle a_{n-1}\) nem osztható \(\displaystyle 3\)-nal, akkor az \(\displaystyle a_{n-1}^2(a_{n-1}-3)\) szorzat sem osztható \(\displaystyle 3\)-mal, így \(\displaystyle a_n\) sem osztható sem \(\displaystyle 3\)-mal, sem \(\displaystyle 9\)-cel. Ha pedig \(\displaystyle a_{n-1}\) osztható \(\displaystyle 3\)-nal, akkor az első tag, \(\displaystyle a_{n-1}^2(a_{n-1}-3)\) osztható \(\displaystyle 9\)-cel, így \(\displaystyle a_n\equiv3\pmod{9}\).
A (3) állítást is \(\displaystyle n\) szerinti indukcióval igazoljuk. A legkisebb \(\displaystyle n\), ami szóba jöhet, az \(\displaystyle n=k+1\); erre
\(\displaystyle a_{k+1} = a_k^3-3a_k^2+3 \equiv 3 \pmod{a_k}. \)
Ha (3) igaz valamely \(\displaystyle n>k\)-re, azaz \(\displaystyle a_n\equiv 3\pmod{a_k}\), akkor a következő, \(\displaystyle n+1\) értékre is igaz:
\(\displaystyle a_{n+1} = a_n^3-3a_n^2+3 \equiv 3^3-3\cdot 3^2+3 = 3 \pmod{a_k}. \)
Ezután rátérhetünk a feladat megoldására. Tekintsünk egy tetszőleges \(\displaystyle n\ge2\) indexet; azt kell igazolnunk, hogy \(\displaystyle a_n\)-nek van olyan prímosztója, ami nem osztja \(\displaystyle a_1,\ldots,a_{n-1}\) egyikét sem.
Az (1) szerint \(\displaystyle a_n>3\), a (2) szerint \(\displaystyle a_n\) nem osztható \(\displaystyle 9\)-cel, ezért az \(\displaystyle a_n\)-nek biztosan van egy \(\displaystyle 3\)-től különböző prímosztója; legyen \(\displaystyle p\) egy ilyen prím.
A (3) állítás szerint bármely \(\displaystyle k<n\) esetén \(\displaystyle a_n-Ka_k=3\) valamilyen \(\displaystyle K\) egész számmal. Ha \(\displaystyle p\) közös osztója lenne \(\displaystyle a_n\)-nek és \(\displaystyle a_k\)-nak, akkor \(\displaystyle a_n-Ka_k=3\) is osztható lenne \(\displaystyle p\)-vel, márpedig \(\displaystyle p\ne3\). Így \(\displaystyle p\) nem lehet osztója \(\displaystyle a_k\)-nak semmilyen \(\displaystyle k<n\) esetén sem.
Statistics:
17 students sent a solution. 5 points: Baran Zsuzsanna, Bukva Balázs, Gáspár Attila, Imolay András, Keresztes László, Kővári Péter Viktor, Matolcsi Dávid, Németh 123 Balázs, Schrettner Jakab, Williams Kada. 4 points: Borbényi Márton, Kerekes Anna, Keresztfalvi Bálint, Lajkó Kálmán, Tóth Viktor, Váli Benedek. 3 points: 1 student.
Problems in Mathematics of KöMaL, February 2017