Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Hint: If $n-m$ is divisible by $7$ then so is $n^6-m^6$. –  Thomas Andrews Feb 6 '13 at 21:32
    
If $n$ is not multiple of $7$ then $n\equiv \{1,2,3,4,5,6\} \bmod 7$ (these all the possibilities). What happens to each one when you take the powers? –  Sigur Feb 6 '13 at 21:32
    
Which part are you having trouble with? Accounting for $1,2,3,4,5,6$, or why that's all you have to account for? –  Hurkyl Feb 6 '13 at 22:13
    
I would call them $1,2,3,-3,-2,-1$. –  Berci Feb 6 '13 at 22:25
add comment

4 Answers

up vote 11 down vote accepted

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

share|improve this answer
    
Thank you for an easy and excellent answer! –  Lukas Arvidsson Feb 7 '13 at 22:04
    
You are welcome. –  André Nicolas Feb 7 '13 at 22:32
add comment

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

share|improve this answer
    
Thank you for your great answer Marvis! –  Lukas Arvidsson Feb 7 '13 at 22:09
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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