HMMT November

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.