Maths Olympiad Prep

Library / /244 of 520

Number theory Difficulty 6.9 National olympiad Prove it

Let f f be a polynomial with positive integer coefficients. Prove that if n n is a positive integer, then f(n) f(n) divides f(f(n)\plus1) f(f(n)\plus{}1) if and only if n\equal1. n\equal{}1.

Solution

1. Let f f be a polynomial with positive integer coefficients, and let n n be a positive integer. We need to prove that f(n) f(n) divides f(f(n)+1) f(f(n) + 1) if and only if n=1 n = 1 .

2. First, consider the polynomial f(x) f(x) . Since f f has positive integer coefficients, f(x) f(x) is strictly increasing for x1 x \geq 1 . This means that for any x1 x \geq 1 , f(x)f(1) f(x) \geq f(1) .

3. We need to show that f(n)f(f(n)+1) f(n) \mid f(f(n) + 1) if and only if n=1 n = 1 .

4. Notice that f(n)+11=f(n) f(n) + 1 - 1 = f(n) . Therefore, we can write:
f(n)f(f(n)+1)f(1) f(n) \mid f(f(n) + 1) - f(1)
This follows from the fact that if ab a \mid b and ac a \mid c , then a(bc) a \mid (b - c) .

5. Since f(n)f(f(n)+1)f(1) f(n) \mid f(f(n) + 1) - f(1) , it implies that:
f(n)f(f(n)+1) f(n) \mid f(f(n) + 1)
if and only if:
f(n)f(1) f(n) \mid f(1)

6. Now, consider the case when n=1 n = 1 :
f(1)f(f(1)+1) f(1) \mid f(f(1) + 1)
Since f f has positive integer coefficients, f(1) f(1) is a positive integer. Therefore, f(1) f(1) divides f(f(1)+1) f(f(1) + 1) .

7. Next, consider the case when n>1 n > 1 . Since f f is strictly increasing and has positive integer coefficients, we have:
f(n)>f(1) f(n) > f(1)
Therefore, f(n) f(n) cannot divide f(1) f(1) because f(n) f(n) is greater than f(1) f(1) .

8. Hence, the only possible value for n n such that f(n)f(f(n)+1) f(n) \mid f(f(n) + 1) is n=1 n = 1 .

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.