Maths Olympiad Prep

Library / /61 of 94

Number theory Difficulty 6.5 National Olympiad Prove it Hong Kong

Is there a polynomial ff of degree 20072007 with integer coefficients, such that f(n),f(f(n)),f(f(f(n))),f(n), f(f(n)), f(f(f(n))), \dots are pairwise relatively prime for every integer nn? Justify your claim.

Solution

Yes. For example, we can take f(x)=x2007x2006+1f(x) = x^{2007} - x^{2006} + 1.
It suffices to show that (m,fk(m))=1(m, f^k(m)) = 1 for any positive integer kk, since we can replace mm by any fj(n)f^j(n). Consider any prime pp dividing mm. Then we have f(m)0(modp)0+1=1(modp)f(m) \equiv 0 \pmod{p} \equiv -0 + 1 = 1 \pmod{p}. Whenever fi(m)1(modp)f^i(m) \equiv 1 \pmod{p}, we have
fi+1(m)11+11(modp). f^{i+1}(m) \equiv 1 - 1 + 1 \equiv 1 \pmod{p}.
Thus, fk(m)1(modp)f^k(m) \equiv 1 \pmod{p} for any k1k \ge 1 by induction. This shows pfk(m)p \nmid f^k(m), and hence (m,fk(m))=1(m, f^k(m)) = 1. This completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.