Task 3/90 It is to be investigated whether there are polynomials of degree $m$

$$
P(n)=\sum_{i=0}^{m} a_{i} n^{i}
$$

with integer coefficients $a_{i}$, for which for every natural number $n$ (including 0) the congruence holds:

$$
\left|3^{n}-P(0)\right| \equiv 0 \quad(\bmod 8)
$$
It is $P(0)=a_{0}$. Since $3^{n} \equiv(2 \pm 1)(\bmod 8)$ (depending on whether $n$ is even or odd), the congruence

$$
\left|3^{n}-P(0)\right| \equiv\left|(2 \pm 1)-a_{0}\right| \equiv 0 \quad(\bmod 8)
$$

cannot be satisfied for any $n \in N$ and any $P(n)$. However, if the left side of the congruence were $\left|3^{n}-P(n)\right|$, then

$$
3^{n}=(2+1)^{n}=\sum_{k=0}^{n}\binom{n}{k} 2^{n-k}=\sum_{k=0}^{n-3}\binom{n}{k} 2^{n-k}+2 n^{2}+1
$$

and for $n \geq 3$ we have

$$
\sum_{k=0}^{n-3}\binom{n}{k} 2^{n-k}=8 \sum_{k=0}^{n-3}\binom{n}{k} 2^{n-k-3} \equiv 0 \quad(\bmod 8)
$$

Therefore, $P^{*}(n)=2 n^{2}+1$ is certainly a polynomial that satisfies the conditions of the problem (this is also true for $n=0 ; 1 ; 2$, as can be easily verified by calculation). If we add to $P^{*}(n)$ the 8-fold of a polynomial $P^{* *}(n)=\sum_{i=0}^{l} b_{i} n^{i}$ of degree $i$ with integer coefficients $b_{i}$, the congruence will not be altered:

$$
P(n)=2 n^{2}+1+8 \sum_{i=0}^{l} b_{i} n^{i}
$$

($b_{i}$ integers). For every natural number $n$, the congruence holds:

$$
\left|3^{n}-P(n)\right|=\left|8 \sum_{k=0}^{n-3}\binom{n}{k} 2^{n-k-3}-8 \sum_{i=0}^{l} b_{i} n^{i}\right| \equiv 0 \quad(\bmod 3)
$$