5
$\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$
5
  • 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, 2014 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, 2014 at 14:26
  • $\begingroup$ I didn't understand the answers or comments with "mod", what are they? $\endgroup$
    – Man_From_India
    Apr 1, 2014 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, 2014 at 14:45
  • 2
    $\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, 2014 at 14:48

4 Answers 4

Reset to default
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$

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

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

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

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to the site, and thank you for the answer. The OP commented about learning about Fermat's Little Theorem, and there are other answers that are along the same lines. Since none of the other answers mentioned Fermat's Little Theorem, if you mentioned that and added a link to it, your answer would have a bit more value. $\endgroup$
    – robjohn ♦
    Jan 23, 2021 at 0:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .