# What is the remainder when 4 to the power 1000 is divided by 7

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?

• 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. – AlexR Apr 1 '14 at 14:22
• 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$. – Mark Bennet Apr 1 '14 at 14:26
• I didn't understand the answers or comments with "mod", what are they? – Man_From_India Apr 1 '14 at 14:38
• 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. – Man_From_India Apr 1 '14 at 14:45
• @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. – Mark Bennet Apr 1 '14 at 14:48

${\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$
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.
Hint: $2^3\equiv1\mod7$, and $4=2^2$.