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}$.
 A: For an integer $n$, the possible values of $n \mod{16}$ are $0,1,\cdots,15$. Try seeing what happens to these values when they are raised to the fourth power modulo $16$...
Spoiler:

 The map $x \mapsto x^4 \mod{16}$ sends the set $\{0,1,\cdots,15\}$ to the set... $\{0,1\}$. Furthermore, exactly half of the elements of $\{0,1,\cdots,15\}$ map to $0$ (the even members), and the other half map to $1$ (the odd members). This means that, for any integer $n$, we have either $n^4 \equiv 0 \pmod{16}$, or $n^4 \equiv 1 \pmod{16}$. Therefore in any list of consecutive fourth powers, ~50% of them will be congruent to $1$ modulo $16$ (I write "~50%", because if the list is of odd length then obviously the split can't be exactly 50/50).

A: 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}$.
