19. [11] Find the smallest positive integer $n$ such that the polynomial $(x+1)^{n}-1$ is "divisible by $x^{2}+1$ modulo 3 ", or more precisely, either of the following equivalent conditions holds:
- there exist polynomials $P, Q$ with integer coefficients such that $(x+1)^{n}-1=\left(x^{2}+1\right) P(x)+3 Q(x)$;
- or more conceptually, the remainder when (the polynomial) $(x+1)^{n}-1$ is divided by (the polynomial) $x^{2}+1$ is a polynomial with (integer) coefficients all divisible by 3 .
$(x+1)^{8} \equiv(-1)^{2}=1$. So the order $n$ divides 8 , as $x+1$ and $x^{2}+1$ are relatively prime polynomials modulo 3 (or more conceptually, in $\mathbb{F}_{3}[x]$ ), but cannot be smaller by our computations of the 2 nd and 4 th powers.
Remark. This problem illustrates the analogy between integers and polynomials (specifically here, polynomials over the finite field of integers modulo 3$)$, with $x^{2}+1(\bmod 3)$ taking the role of a prime number. Indeed, we can prove analogously to Fermat's little theorem that $f(x)^{3^{\operatorname{deg}\left(x^{2}+1\right)}} \equiv f(x)$ (mod $\left.x^{2}+1,3\right)$ for any polynomial $f(x)$ : try to work out the proof yourself! (This kind of problem, with 3 replaced by any prime $p$ and $x^{2}+1$ by any irreducible polynomial modulo $p$, is closely related to the theory of (extensions of) finite fields.)
Solution 2. Here's a solution avoiding the terminology of groups and fields. Let $R(x)=(x+1)^{n}-1-$ $P(x)\left(x^{2}+1\right)=3 Q(x)$ be the remainder (here $P$ is the quotient), whose coefficients (upon expansion) must all be divisible by 3 . Now consider $R(i)$. The coefficients of the even and odd powers of $x$ are divisible by 3 , so $R(i)$ must have real and imaginary parts divisible by 3 . Notice that $(1+i)^{2}=2 i$, $(1+i)^{4}=-4,(1+i)^{6}=-8 i,(1+i)^{8}=16$, and that $(1+i)^{8}-1=15$, which has real and imaginary parts divisible by 3 . Since any even power of $(1+i)$ (for $n \leq 6$ ) yields a purely real or purely imaginary number with a coefficient not divisible by 3 , multiplying it by $1+i$ will yield an imaginary part not divisible by 3 . To see that $n=8$ works, notice that, when taken modulo 3 ,
$$
\begin{aligned}
(x+1)^{8}-1 & =x^{8}+8 x^{7}+28 x^{6}+56 x^{5}+70 x^{4}+56 x^{3}+28 x^{2}+8 x \\
& \equiv x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x \\
& =\left(x^{2}+1\right)\left(x^{6}-x^{5}+x^{2}-x\right) \quad(\bmod 3),
\end{aligned}
$$
as desired.