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?
Best Answer
${\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$