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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

We have $\varphi(7)=6$, therefore, $4^6\equiv 1\ (\mathrm{mod}\ 7)$ by Euler's theorem. Now, $ (4^6)^{166}=4^{996}\equiv 1\ (\mathrm{mod}\ 7)$. Since $4^4\equiv 4\ (\mathrm{mod}\ 7)$, it follows that $4^{1000}=4^{996}\times 4^4\equiv 4\ (\mathrm{mod}\ 7)$.