KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 10 March 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley