3
$\begingroup$

I am trying to find the remainder of $4^{220}$ when divided by $7$.

$$4^{220}=2^{440}$$

Now had the question been what is the remainder of $2^{220}$ when divided by $10$, you would simply look at cycles in the last digit.

Last.Digit($2^1$)=$2$

Last.Digit($2^2$)=$4$

Last.Digit($2^3$)=$8$

Last.Digit($2^4$)=$6$

...

So the repeating cycle is $2$,$4$,$6$,$8$. Even if the question had asked the remainder if divided by $5$, one could use the last digits of $2^n$ to find the solution. Is there a way to find the remainder using this cycle when divided by $7$? Or do I literally have to compute the remainder of each power divided by $7$, as such

Remainder of ($2^1$,$7$)=$2$

Remainder of ($2^2$,$7$)=$4$

Remainder of ($2^3$,$7$)=$1$
...

A repeating cycle of $3k$. So $440=3(146)+2$, Hence the remainder is $4$.

$\endgroup$
5
  • 1
    $\begingroup$ Yes, separately. You are doing it well.. $\endgroup$
    – Berci
    Sep 29, 2013 at 20:09
  • 1
    $\begingroup$ Do you know modular arithmetic and congruence relations modulo $n$? $\endgroup$
    – user66733
    Sep 29, 2013 at 20:09
  • $\begingroup$ That way is good. Perhaps more directly, use $4$; the remainder when $4^3$ is divided by $7$ is $1$, and $19$ is a multiple of $3$. $\endgroup$
    – André Nicolas
    Sep 29, 2013 at 20:13
  • $\begingroup$ You might want to investigate Fermat's little theorem and generalisations like Euler's theorem en.wikipedia.org/wiki/Fermat's_little_theorem $\endgroup$
    – Mark Bennet
    Sep 29, 2013 at 20:15
  • $\begingroup$ I guess my question was more general. Could you use the remainders when divided by 10 to find the remainders when divided by 7? $\endgroup$
    – jessica
    Sep 29, 2013 at 20:24

2 Answers 2

Reset to default
1
$\begingroup$

In general, if $n$ is prime and $a$ is not divisible by $n$, then $a^{n-1} = 1$ is the remainder when you divide by $n$. Hence if you already know remainders of $a^1,a^2,\ldots,a^{n-2}$ when you divide by $n$, then you can get the remainder for $a^M$ for any $M \geq n$ by exploiting the cycle like you did. In your case, you have $2^3 = 1$ is the remainder when you divide by $7$, which is even better than knowing $2^6 = 1$ is the remainder when you divide by $7$, so you only need to know the remainders of $2$ and $4$ when you divide by $7$ in order to establish the cycle and do your computation. In general this can always happen; you may very well have $a^k = 1$ as the remainder when you divide by $n$, where $k$ is a smaller divisor of $n-1$. Or it may require the full $k=n-1$ to get remainder of $1$ when you divide by $n$, in order to get the cycle. But the point is you'll always get a cycle of some length $\leq n$, so you can do your computations like you did. In general, knowing the cycle for some $n$ will not help you figure out the cycle for a different coprime choice of $n$, to answer the other part of your question you alluded to.

$\endgroup$
1
  • $\begingroup$ Oh, i see. So When I found the remainder cycle for 10. I could have used this cycle to find the remainders when divided by 5 because (10,5) are not coprime. But I cann't use the remainder cycle for 10 to find 7 because they have no common factor. Do I understand you correctly? $\endgroup$
    – jessica
    Sep 29, 2013 at 20:31
1
$\begingroup$

All you need is just a little modular arithmetics. Not that the modulo is a prime number and the base and the modulo ar coprime numbers, so the Fermat's Little Theorem is your friend here. We know then that the follwing statement holds:

$$a^{n \mod p-1} \equiv a^{p-1} \equiv 1 \pmod p$$

Now just plug the values and you'll be able to obtain a solution quite easily.

$\endgroup$

You must log in to answer this question.

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