Question 74
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.
- 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.