Exercise 1655Number theory › Divisibility and gcdOlympiadAdded 3 Nov 2026

GCD of polynomial coefficients

#gcd#coefficients#polynomials

Statement

Let $P(X)=a_nX^n+\cdots+a_0\in\mathbb{Z}[X]$ . Show that if a prime $p$ divides all coefficients except possibly $a_k$ , then $P$ has a root mod $p$ only if $a_k\equiv0\pmod p$ .

Hint

Reduce $P$ mod $p$ : $P\equiv a_kX^k\pmod p$ .

Show solutionHide solution

Solution

Reduction. Mod $p$ , $P(X)\equiv a_kX^k\pmod p$ .

Root condition. If $\alpha\in\mathbb{Z}/p\mathbb{Z}$ satisfies $P(\alpha)\equiv0$ , then $a_k\alpha^k\equiv0$ .

Conclusion. If $a_k\not\equiv0$ , then $\alpha=0$ is the only possible root, and it satisfies $P(0)\equiv a_0\equiv0$ automatically. If $a_0\not\equiv0$ and $a_k\not\equiv0$ , $P$ has no root mod $p$ .

GCD of polynomial coefficients

Statement

Solution

More problems in Divisibility and gcd