Maths Olympiad Prep

Library / /13 of 24

, 2023

Algebra Difficulty 6.6 National Olympiad Prove it Canada

Problem:
Let f(x)f(x) be a non-constant polynomial with integer coefficients such that f(1)1f(1) \neq 1. For a positive integer nn, define divs(n)\operatorname{divs}(n) to be the set of positive divisors of nn.
A positive integer mm is ff-cool if there exists a positive integer nn for which
f[divs(m)]=divs(n) f[\operatorname{divs}(m)]=\operatorname{divs}(n)
Prove that for any such ff, there are finitely many ff-cool integers.
(The notation f[S]f[S] for some set SS denotes the set {f(s):sS}\{f(s): s \in S\}.)

Solution

Solution:
Assume for the sake of contradiction that there are infinitely many ff-cool integers.
If f(x)f(x) has a negative leading coefficient, then a sufficiently large ff-cool integer mm will have f(m)<0f(m)<0. But this implies mm is not ff-cool, contradiction.
Thus f(x)f(x) has a positive leading coefficient, so we can pick an NN such that for all m>Nm>N,
f(m)>max(f(1),f(2),,f(m1)) f(m)>\max (f(1), f(2), \ldots, f(m-1))
This means f(m)f(m) is the largest value in f[divs(m)]f[\operatorname{divs}(m)], so if mm is ff-cool with f[divs(m)]=divs(n)f[\operatorname{divs}(m)]=\operatorname{divs}(n), then we must have n=f(m)n=f(m), since nn is the largest value in divs(n)\operatorname{divs}(n). In other words,
f[divs(m)]=divs(f(m)) f[\operatorname{divs}(m)]=\operatorname{divs}(f(m))
for all ff-cool m>Nm>N.
For each of those mm's, 1divs(f(m))1 \in \operatorname{divs}(f(m)), so there must be a kdivs(m)k \in \operatorname{divs}(m) such that f(k)=1f(k)=1. Let k1,k2,,knk_{1}, k_{2}, \ldots, k_{n} be the solutions to f(x)=1f(x)=1. Thus every ff-cool m>Nm>N is divisible by some k{k1,k2,,kn}k \in\left\{k_{1}, k_{2}, \ldots, k_{n}\right\}. Since there are infinitely many such mm's and finitely many kk's, by the Pigeonhole Principle there is some kk which divides infinitely many ff-cool integers mm. (Note that k1k \neq 1 since f(1)1f(1) \neq 1.)
For all ff-cool m>Nm>N divisible by kk, we have
f(mk)f[divs(m)]=divs(f(m))f(mk)f(m). \left.f\left(\frac{m}{k}\right) \in f[\operatorname{divs}(m)]=\operatorname{divs}(f(m)) \Longrightarrow f\left(\frac{m}{k}\right) \right\rvert\, f(m) .
Thus, f(x)f(kx)f(x) \mid f(k x) has infinitely many positive integer solutions. Let d=deg(f)d=\operatorname{deg}(f), and write
f(kx)f(x)=kd+g(x)f(x) \frac{f(k x)}{f(x)}=k^{d}+\frac{g(x)}{f(x)}
for some g(x)Z[x]g(x) \in \mathbb{Z}[x] with deg(g)<d\operatorname{deg}(g)<d. If g(x)0g(x) \neq 0, then for sufficiently large xx we have 0<g(x)<f(x)0<|g(x)|<f(x), since deg(f)>deg(g)\operatorname{deg}(f)>\operatorname{deg}(g). But then f(kx)f(x)kd=g(x)f(x)\frac{f(k x)}{f(x)}-k^{d}=\frac{g(x)}{f(x)} cannot be an integer, which gives us the desired contradiction.
Therefore g(x)=0g(x)=0, so f(kx)=kdf(x)f(k x)=k^{d} f(x), i.e. f(x)=axdf(x)=a x^{d} for some positive integer aa. If a=1a=1 then f(1)=1f(1)=1, a contradiction. But if a>1a>1, then f(x)=1f(x)=1 has no integer solutions, another contradiction.

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.