7
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.