## Task 21/73

Determine a polynomial $P(x)$ of the smallest degree with integer coefficients that is always divisible by 8 for odd $x$. The polynomial $P(x)$ should not be divisible by 2 for every integer $x$.
First, it is clear that no linear polynomial satisfies the conditions given in the problem. If we substitute $x=1$ and $x=-1$ into the congruence $a x+b \equiv 0(\bmod 8)$, we obtain

$$
a+b \equiv 0(\bmod 8) \quad ; \quad-a+b \equiv 0(\bmod 8)
$$

which implies $a \equiv b \equiv 0(\bmod 4)$. This means, however, that the polynomial is divisible by 2 for any integer $x$.

To find a polynomial of degree 2 with the required properties, we use the following fact: It is

$$
1^{2} \equiv(-1)^{2} \equiv 3^{2} \equiv(-3)^{2} \equiv 1(\bmod 8)
$$

That is, the square of any odd number leaves a remainder of 1 when divided by 8. Therefore, for the polynomial

$$
P(x)=x^{2}-c^{2} \equiv 0(\bmod 8)
$$

if $x$ and $c$ are odd numbers. For even numbers $x$, however, $x^{2} \equiv 0(\bmod 2)$, and for odd numbers $c$, $c^{2} \equiv 1(\bmod 2)$. Consequently, the polynomial $P(x)=x^{2}-c^{2}$ with odd $c$ is not divisible by 2 for all integer $x$.