<s>[INST] Why, given a natural number $n$, does $n^6$ always have the remainder of 1 when divided by 7? I am trying to prove why a natural number $n$ (which is not a multiple of $7$) when taken to the power of six ($n^6$) and divided by 7 always have the remainder of 1? I am not supposed to use "Fermats little theorem", but I am given the hint that the only numbers I have to account for are $1, 2, 3, 4, 5, 6$.
I would very much appreciate if someone could explain this to me.
Thank you 
 [/INST] Make use of the fact that if 
$$a \equiv b \pmod{k}$$ then
$$a^n \equiv b^n \pmod{k}$$
In your case, for any $n$ that is not a multiple of $7$, we have
$$n \equiv \begin{cases}1 \pmod 7\\ 2 \pmod 7 \\ 3 \pmod 7 \\ 4 \pmod 7 \\ 5 \pmod 7 \\ 6 \pmod 7 \end{cases}$$
Hence,
$$n^6 \equiv \begin{cases}1^6 \pmod 7\\ 2^6 \pmod 7 \\ 3^6 \pmod 7 \\ 4^6 \pmod 7 \\ 5^6 \pmod 7 \\ 6^6 \pmod 7 \end{cases} \equiv \begin{cases}1 & \pmod 7\\ (2^3)^2 & \pmod 7 \\ (3^3)^2 & \pmod 7 \\ (4^3)^2 & \pmod 7 \\ (5^3)^2 & \pmod 7 \\ (-1)^6 & \pmod 7 \end{cases} \equiv \begin{cases}1 & \pmod 7\\ 1^2 & \pmod 7 \\ (-1)^2 & \pmod 7 \\ 1^2 & \pmod 7 \\ (-1)^2 & \pmod 7 \\ (-1)^6 & \pmod 7 \end{cases} \equiv 1 \pmod 7$$
</s>