Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

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.

Problems in Mathematics of KöMaL, December 2012