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 
 A: You can shrink the size of the numbers you need to deal with by noticing that
$$
n^6-1=(n^3-1)(n^3+1)=(n-1)(n+1)(n^2-n+1)(n^2+n+1) \, .
$$
So if any of those four factors are multiples of $7$, so too will be $n^6-1$.
Now,


*

*$1-1=0 \times 7$

*$2^2+2+1=1 \times 7$

*$3^2-3+1=1 \times 7$

*$4^2+4+1=3 \times 7$

*$5^2-5+1=3 \times 7$

*$6+1=1 \times 7$


so one of these factors is a multiple of $7$ for all $n \in \{1,2,3,4,5,6\}$.
A: When you are dividing by 7 and only care about remainders, the only numbers you really are caring about are 0 through 6. This is because these represent the only possibilities for remainders. 
So if you check each of those numbers specifically, you see that they all have a remainder of 1:
$$
\begin{align}
1^6 &= 1 \\
2^6 &= 64 = 9\cdot7 + 1\\
3^6 &= 729 = 107 \cdot 7 + 1 \\
4^6 &= 4096 = 585 \cdot 7 + 1 \\
5^6 &= 15625 = 2232 \cdot 7 + 1 \\
6^6 &= 46656 = 6665 \cdot 7 + 1
\end{align}
$$
A: Every integer which is not divisible by $7$ is of the form $7k\pm 1$, $7k\pm 2$, or $7k\pm 3$, where $k$ is an integer.  Imagine taking the $6$-th power of one of these numbers. The result will be a multiple of $7$, plus one of $1^6$, $2^6$, or $3^6$. It is easy to verify that in each of these cases, the result has remainder $1$ on division by $7$. For $1^6$ it is obvious. Since $2^6=64$, we have the result for $2^6$. For $3$ we note that $3^2$ has remainder $2$ on division by $7$, and $2^3$ has remainder $1$.
A: 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$$
