percentage of integers such that $n^4 \pmod{16} \equiv 1$? How do I find the percentage of numbers $n$ in the list $1^4, 2^4, ... 1000^4$ such that $n \pmod{16} \equiv 1$? I know that for any $x$, if $x \pmod{16} \equiv 1$, then $x^n \pmod{16} \equiv 1$, so I know for sure that there are at least around $\lfloor \frac{1000}{16} \rfloor = 62$ values of $n$ such that $n  \pmod{16} \equiv 1$, because any multiple of $16$ plus $1$ will equal $1 \pmod {16}$. However, I am stuck on how to find the rest? My answer sheet tells me that between $20$ to $50$ percent of the numbers are $1 \pmod {16}$.

We have
$$
\begin{align}
(2n)^4
&=16n^4\\
&\equiv0&\pmod{16}
\end{align}
$$
and
$$
\begin{align}
(2n+1)^4
&=16n^4+32n^3+24n^2+8n+1\\
&\equiv16\frac{n(n+1)}2+1&\pmod{16}\\
&\equiv1&\pmod{16}
\end{align}
$$
Therefore, $8$ out of $16$ equivalence classes mod $16$ satisfy $n^4\equiv1\pmod{16}$. So, I'd say $50\%$ of the equivalence classes mod $16$.
Since there are $500$ odd numbers from $1$ to $1000$ and $500$ even numbers, exactly $50\%$ of the numbers from $1$ to $1000$ have $n^4\equiv1\pmod{16}$.
