Competition problem — Number theory

Library / /20 of 29

Number theory Difficulty 6.6 National olympiad Prove it Iran

$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$
with integer coefficients *primitive* if and only if $\text{gcd}(a_n, a_{n-1}, \dots, a_1, a_0) = 1$ .
a) Let $P(x)$ be a primitive polynomial with degree less than $1398$ and $S$ be a subset of primes greater than $1398$ . Prove that there is a positive integer $n$ so that $P(n)$ is not divisible by any prime in $S$ .
b) Prove that there exists a primitive polynomial $P(x)$ with degree less than $1398$ such that for each *natural* number $n$ , $P(n)$ is divisible by every prime less than $1398$ .

Solution

a) We know that for every polynomial $P(x)$ with degree $n$ , the equation $P(x) \equiv 0 \pmod{p}$ has at most $n$ distinct roots modulo $p$ , for every prime number $p$ . Then for every $p_i \in S$ we have some $t_i \in \{1, 2, \dots, p\}$ where $p_i \nmid P(t_i)$ . Now choose $t$ by Chinese Remainder Theorem such that $t \equiv t_i \pmod{p_i}$ . Then for every $p_i \in S$ we have $p_i \nmid P(t)$ .

b) Put
$P(x) = x(x - 1) \dots (x - 1396) + 1398!$
Note that $1397$ and $1398$ are composite numbers. Then obviously for any $p \le 1398$ and $n \in \mathbb{N}$ there exists an $a_i$ such that $1 \le a_i \le 1398$ and $n \equiv a_i \pmod{p_i}$ . Therefore $p_i \mid P(n)$ and since $P(x)$ is monic it satisfies our desired conditions.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.