Number theoryDifficulty 6.5National OlympiadProve itHong Kong
Is there a polynomial f of degree 2007 with integer coefficients, such that f(n),f(f(n)),f(f(f(n))),… are pairwise relatively prime for every integer n? Justify your claim.
Solution
Yes. For example, we can take f(x)=x2007−x2006+1. It suffices to show that (m,fk(m))=1 for any positive integer k, since we can replace m by any fj(n). Consider any prime p dividing m. Then we have f(m)≡0(modp)≡−0+1=1(modp). Whenever fi(m)≡1(modp), we have fi+1(m)≡1−1+1≡1(modp). Thus, fk(m)≡1(modp) for any k≥1 by induction. This shows p∤fk(m), and hence (m,fk(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.