Divisibility Condition Count
Find the number of positive integers $ n, $ $ 1 \le n \le 100, $ for which $ x^{2n} + 1 + (x + 1)^{2n} $ is divisible by $ x^2 + x + 1 $.
- 1
- 2
- 3
- +
- 4
- 5
- 6
- -
- 7
- 8
- 9
- $\frac{a}{b}$
- .
- 0
- =
- %
- $a^n$
- $a^{\circ}$
- $a_n$
- $\sqrt{}$
- $\sqrt[n]{}$
- $\pi$
- $\ln{}$
- $\log$
- $\theta$
- $\sin{}$
- $\cos{}$
- $\tan{}$
- $($
- $)$
- $[$
- $]$
- $\cap$
- $\cup$
- $,$
- $\infty$
Solution
Let $ \omega $ be a root of $ x^2 + x + 1 = 0, $ so $ \omega^2 + \omega + 1 = 0 $. Then by the factor theorem, $ x^{2n} + 1 + (x + 1)^{2n} $ is divisible by $ x^2 + x + 1 $ if and only if $ \omega^{2n} + 1 + (\omega + 1)^{2n} = 0 $.
Since $ \omega + 1 = -\omega^2, $
\[\omega^{2n} + 1 + (\omega + 1)^{2n} = \omega^{2n} + 1 + (-\omega^2)^{2n} = \omega^{4n} + \omega^{2n} + 1.\]From the equation $ \omega^2 + \omega + 1 = 0, $ $ (\omega - 1)(\omega^2 + \omega + 1) = \omega^3 - 1, $ so $ \omega^3 = 1 $.
We divide into the cases where $ n $ is of the form $ 3k, $ $ 3k + 1, $ and $ 3k + 2 $.
If $ n = 3k, $ then
\begin{align*}
\omega^{4n} + \omega^{2n} + 1 &= \omega^{12k} + \omega^{6k} + 1 \\
&= (\omega^3)^{4k} + (\omega^3)^{2k} + 1 \\
&= 1 + 1 + 1 = 3.\end{align*}If $ n = 3k + 1, $ then
\begin{align*}
\omega^{4n} + \omega^{2n} + 1 &= \omega^{12k + 4} + \omega^{6k + 2} + 1 \\
&= (\omega^3)^{4k + 1} \omega + (\omega^3)^{2k} \omega^2 + 1 \\
&= \omega + \omega^2 + 1 = 0.\end{align*}If $ n = 3k + 2, $ then
\begin{align*}
\omega^{4n} + \omega^{2n} + 1 &= \omega^{12k + 8} + \omega^{6k + 4} + 1 \\
&= (\omega^3)^{4k + 2} \omega^2 + (\omega^3)^{2k + 1} \omega + 1 \\
&= \omega^2 + \omega + 1 = 0.\end{align*}Hence, $ x^{2n} + 1 + (x + 1)^{2n} $ is divisible by $ x^2 + x + 1 $ if and only if $ n $ is of the form $ 3k + 1 $ or $ 3k + 2, $ i.e. is not divisible by 3. In the interval $ 1 \le n \le 100, $ there are $ 100 - 33 = \boxed{67} $ such numbers.