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