Olympiad Maths Prep

Track / Stage 7 / 125 of 300 #1525 of 2000

Problem 1525

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.2 Prove it

For a non-negative integer nn, call a one-variable polynomial FF with integer coefficients nn-[i]good [/i] if:
(a) F(0)=1F(0) = 1
(b) For every positive integer cc, F(c)>0F(c) > 0, and
(c) There exist exactly nn values of cc such that F(c)F(c) is prime.
Show that there exist infinitely many non-constant polynomials that are not nn-good for any nn.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

To show that there exist infinitely many non-constant polynomials that are not nn-good for any nn, we need to construct a family of polynomials that fail to meet the criteria for being nn-good for any non-negative integer nn.

1. **Consider the polynomial F(x)=Ax+1F(x) = Ax + 1 where AA is a non-zero integer:**
- This polynomial is non-constant since A0A \neq 0.
- F(0)=1F(0) = 1, satisfying condition (a).
- For any positive integer cc, F(c)=Ac+1F(c) = Ac + 1. Since AA and cc are positive, Ac+1>0Ac + 1 > 0, satisfying condition (b).

2. **Analyze the number of primes generated by F(x)=Ax+1F(x) = Ax + 1:**
- By Dirichlet's theorem on arithmetic progressions, there are infinitely many primes in the sequence Ac+1Ac + 1 where cc is a positive integer.
- This implies that for any nn, there are infinitely many values of cc such that F(c)F(c) is prime. Therefore, it is impossible for F(x)=Ax+1F(x) = Ax + 1 to have exactly nn values of cc such that F(c)F(c) is prime.

3. **Construct a family of polynomials that are not nn-good:**
- Consider the family of polynomials F(x)=Ax+1F(x) = Ax + 1 for any non-zero integer AA.
- As shown, these polynomials cannot be nn-good for any nn because they generate infinitely many primes, violating condition (c).

4. Conclusion:
- Since AA can be any non-zero integer, there are infinitely many such polynomials F(x)=Ax+1F(x) = Ax + 1.
- Therefore, there exist infinitely many non-constant polynomials that are not nn-good for any nn.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.