9. [55] Let $N$ be the smallest positive integer for which
$$
x^{2}+x+1 \quad \text { divides } \quad 166-\sum_{d \mid N, d>0} x^{d} \text {. }
$$

Find the remainder when $N$ is divided by 1000 .
Answer:
672
Solution: Let $\omega=e^{2 \pi i / 3}$. The condition is equivalent to
$$
166=\sum_{d \mid N, d>0} \omega^{d}
$$

Let's write $N=3^{d} n$ where $n$ is not divisible by 3 . If all primes dividing $n$ are $1 \bmod 3$, then $N$ has a positive number of factors that are $1 \bmod 3$ and none that are $2 \bmod 3$, so $\sum_{d \mid N, d>0} \omega^{d}$ has nonzero imaginary part. Therefore $n$ is divisible by some prime that is $2 \bmod 3$. In this case, the divisors of $n$ are equally likely to be 1 or $2 \bmod 3$, so the sum is
$$
-\frac{1}{2} \tau(n)+d \tau(n)=\frac{2 d-1}{2} \tau(n) .
$$

Now, $2 \cdot 166=2^{2} \cdot 83$ and 83 is prime, so we must either have $d=42$, which forces $\tau(n)=4$, or $d=1$, which forces $\tau(n)=332$. The first cases yields a lower value of $N$, namely $3^{42} 2^{3}$.
Now let's try to compute this mod 1000 . This is clearly divisible by 8 . Modulo $125,3^{5}=243 \equiv-7$, so $3^{20} \equiv 2401 \equiv 26$ and $3^{40} \equiv 676 \equiv 51$. Therefore $3^{42} 2^{3} \equiv 72 \cdot 51=3672 \bmod 125$. Since 672 is divisible by 8 , this is our answer.