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

 

Problem B. 4500. (December 2012)

B. 4500. Is there an at least second-degree polynomial of integer coefficients, such that the numbers n,f(n),f(f(n)),... are pairwise relative primes for all positive integers n?

(6 pont)

Deadline expired on January 10, 2013.


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

Útmutatás: Igen. Bizonyítsuk be, hogy f(0)=\pm1 és f(f(0))=\pm1.

Megoldás: Igen. Legyen f(x)=x2-x+1, és definiáljuk az fi sorozatot az f0(x)=x, fi+1(x)=f(fi(x)) rekurzióval. Azt kell belátni, hogy bármely n pozitív egész szám esetén az f_0(n),f_1(n),f_2(n)\ldots számok páronként relatív prímek. Ez ekvivalens azzal, hogy tetszőleges n pozitív egész szám, p prímszám és 0\lei<j egész számok esetén p\mid f_i(n) maga után vonja azt, hogy p\nmid f_j(n). Minthogy pedig fj(n)=fj-i(fi(n)), elegendő a következő állítást igazolni: Ha a p prímszám osztja a k egész számot, akkor bármely i\ge1 esetén f_i(k)\equiv 1\pmod{p}.

Ez az állítás i szerinti indukcióval könnyen igazolható. Az i=1 eset nyilvánvaló, hiszen p\mid k^2-k. Ha pedig valamely i-re már igazolást nyert, akkor (i+1)-re is igaz lesz:

f_{i+1}(k)=f_i(k)^2-f_i(k)+1\equiv 1^2-1+1=1\pmod{p}.


Statistics:

48 students sent a solution.
6 points:Balogh Tamás, Baran Zsuzsanna, Barna István, Csernák Tamás, Di Giovanni Márk, Fehér Zsombor, Fonyó Viktória, Forrás Bence, Havasi 0 Márton, Herczeg József, Homonnay Bálint, Janzer Barnabás, Janzer Olivér, Kabos Eszter, Kocsis Laura, Kúsz Ágnes, Leitereg András, Leitereg Miklós, Maga Balázs, Nagy Róbert, Nagy-György Pál, Sagmeister Ádám, Schultz Vera Magdolna, Schwarcz Tamás, Simon 047 Péter, Szabó 262 Lóránt, Szabó 789 Barnabás, Tardos Jakab, Tossenberger Tamás, Venczel Tünde, Williams Kada, Zilahi Tamás.
5 points:Ágoston Péter, Juhász Balázs, Mócsy Miklós, Nagy Bence Kristóf, Nagy Gergely, Zarándy Álmos.
4 points:1 student.
3 points:3 students.
1 point:2 students.
0 point:4 students.

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