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

Thomas Andrews
  • 177,126
Lukas Arvidsson
  • 2,376

4 Answers4

14

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$.

André Nicolas
  • 507,029
12

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$$

3

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\}$.

Micah
  • 38,108
  • 15
  • 85
  • 133
2

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} $$

Paul Raff
  • 757