4
$\begingroup$

What is the remainder when $4^{1000}$ is divided by 7? In my book the problem is solved, but I am unable to understand the approach. Please help me understand -

Solution -

To find the Cyclicity, we keep finding the remainders until any remainder repeats itself. It can be understood with the following example:

No./7 -> $4^1$ $4^2$ $4^3$ $4^4$ $4^5$ $4^6$ $4^7$ $4^8$

Remainder -> 4 2 1 4 2 1 4 2

Now $4^4$ gives us the same remainder as $4^1$, so the Cyclicity is of 3 (Because remainders start repeating themselves after $4^3$

So any power of 3 or multiple of 3 will give the remainder of 1. So, $4^{999}$ will give remainder 1.

Final remainder is 4.

Now I don't understand the last line. Please explain, how the remainder comes down to 4?

$\endgroup$
  • 1
    $\begingroup$ You have seen (by example, not really proved), that $$4^k \equiv 4^l \mod 7 \Leftrightarrow k\equiv l \mod 3$$ Chose $k=1000, l=1$ and you are done. $\endgroup$ – AlexR Apr 1 '14 at 14:22
  • $\begingroup$ If in doubt, try the very basic things. You know that $4^{999}=7r+1$ for some integer $r$. Multiply by $4$ to give $4^{1000}=28r+4$ which clearly leaves remainder $4$ on division by $7$. $\endgroup$ – Mark Bennet Apr 1 '14 at 14:26
  • $\begingroup$ I didn't understand the answers or comments with "mod", what are they? $\endgroup$ – Man_From_India Apr 1 '14 at 14:38
  • $\begingroup$ I got it. I did searched the forum, and came o know about Fermat's little theorem, which solves these kind of problems. Thanks everyone, I got it. $\endgroup$ – Man_From_India Apr 1 '14 at 14:45
  • 1
    $\begingroup$ @Man_From_India $x\equiv y \mod z$ - where mod is short for "modulo" (sometimes "modulus") is another way of saying that $z$ is a factor of $x-y$ or alternatively that $x=rz+y$ for some integer $r$. It takes a bit of getting used to, but is very useful, particularly because (with a little care) you can do arithmetic $\mod z$ and forget that there are terms like $rz$ in the background. $\endgroup$ – Mark Bennet Apr 1 '14 at 14:48
4
$\begingroup$

${\rm mod}\ 7\!:\ \color{#c00}{4^{\large 3}\equiv 1}\,\Rightarrow\, 4^{\large 1000}\equiv 4^{\large 1+999}\equiv 4 (\color{#c00}{4^{\large 3}})^{\large 333}\equiv 4\color{#c00}{(1)}^{\large 333}\equiv 4$

More generally we have that $\ 4^{\large r+3q}\equiv 4^r (\color{#c00}{4^{\large 3}})^{\large q}\equiv 4^{\large r}\color{#c00}{(1)}^{\large q}\equiv 4^{\large r}$

Written in terms of mod this is: $\ 4^{\large n}\equiv 4^{\large n\ {\rm mod}\ 3}\,$ where $\ n = 3q+r\,$ and $\,r = n\ {\rm mod}\ 3$

$\endgroup$
1
$\begingroup$

As you have said, the remainders are cyclic in the pattern 4 2 1 4 2 1. So, if $4^{999}$ has a remainder of 1, $4^{1000}$ will have the next remainder in the cycle which is 4.

$\endgroup$
0
$\begingroup$

Hint: $2^3\equiv1\mod7$, and $4=2^2$.

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