For positive integers $n$, let $s(n)$ be the sum of $n$-th powers of primitive roots $\bmod 1601$. Find the number of positive integers $n < 1000$ such that $1601$ divides $s(n)$.
How do I approach this problem? $3$ is the smallest primitive root of $1601$, but I am not sure how to find $s(n)$ from the same since there are $600+$ primitive roots? It's a problem I'm trying to solve
One idea I have that I'm presently working on is considering $(p-n)^{k}$ a multiple of $1601$ (obviously) and its binomial expansion, but new ideas are welcome!