Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the simplest method to go about finding the remainder of $5^{20}$ divided by $61$?

share|improve this question
1  
The simplest method is probably to use a calculator. But you are probably inquiring about elegant methods of computing this. –  Arthur Fischer Jun 26 '12 at 6:55
1  
How about (trying to keep the numbers small enough to do in my head): $5^3 \equiv 3$ (as most of the answers below start), so $5^6 \equiv 3^2 = 9$, so $5^{12} \equiv 9^2 = 81 \equiv 20$, so $5^{18} = 5^{12}5^6 \equiv (20)(9) = 180 \equiv -3$, so $5^{20} = 5^{18}5^2 \equiv (-3)(25) = -75 \equiv -14 \equiv 47$. –  ShreevatsaR Jun 26 '12 at 6:56

7 Answers 7

up vote 7 down vote accepted

$5^3 = 125 \equiv 3 \mod 61$, so $5^5 \equiv 25 \times 3 = 75 \equiv 14 \mod 61$, $5^{10} \equiv 14^2 = 196 \equiv 13 \mod 61$, $5^{20} \equiv 13^2 = 169 \equiv 47 \mod 61$.

share|improve this answer

Calculate. We have $5^3=125\equiv 3$, and therefore $5^5\equiv 75\equiv 14$. Thus $5^{10}\equiv 196\equiv 13$ and $5^{20}\equiv 169\equiv 47$.

share|improve this answer

Note that $5^3 = 125 = 2(61)+3$. So $5^{20} = (5^3)^6\times 5^2\equiv 3^6\times 5^2 \pmod{61}$.

Now, $3^3\equiv 27$, $3^3\times 5 = 135 \equiv 13\pmod{61}$. So

$$5^{20}\equiv (5^3)^6\times 5^2\equiv 3^6\times 5^2 =(3^3\times 5)^2 \equiv 13^2 \equiv 169\pmod{61}$$ and since $169 = 2(61) + 47$, we finally have that $5^{20}\equiv 47\pmod{61}$.

If you want to be systematic, then repeated squaring works well: $20 = 16 + 4$. So first compute $5^2=25$. Then square that and reduce modulo $61$ to get $5^4$; then square that and reduce to get $5^8$; square again to get $5^{16}$. Then multiply the results of $5^4$ and $5^{16}$ to get $5^{20}$. This amounts five products and reductions.

share|improve this answer

$5^3=125=2\cdot61+3$, so $5^3\equiv 3\pmod{61}$. $3^5=243=4\cdot61-1$, so $5^{15}\equiv 3^5\equiv-1\pmod{61}$. Finally, $5^{20}=5^{15}\cdot5^3\cdot5^2\equiv-1\cdot3\cdot25\equiv-75\equiv-14\equiv47\pmod{61}$.

share|improve this answer

Note that $5^3=125 = 3\pmod{61}$, so $5^{20}=5^{18}.25=(5^3)^6.25=3^6.25\pmod {61}$.Now $3^5=243\pmod {61}=-1\pmod {61}$ $\implies$ $3^6.25\pmod {61}= -3.25\pmod{61}=-75\pmod{61}=47\pmod {61}$.

share|improve this answer

If the exponent were larger (or the prime smaller), you could first reduce using Fermat's Little Theorem, which says $a^{p} \equiv a \pmod{p}$. This lets you take the exponent modulo $p-1$. However, that's not much help here.

What works in general (and as I've written quick-and-dirty code to do many a time) is the following technique.

First repeatedly square the base (5), keeping mod 61 as you go:

  • $5 \equiv 5 \pmod{61}$
  • $5^2 \equiv 25 \pmod{61}$
  • $5^4 = 25^2 = 625 \equiv 15 \pmod{61}$
  • $5^8 \equiv 15^2 = 225 \equiv 42 \pmod{61}$
  • $5^{16} \equiv 42^2 \equiv (-19)^2 = 361 \equiv -5 \pmod{61}.$

Each step, I've just squared my answer from the previous step. (Often it might be preferable to replace, say, 60 by -1, like I've done above a couple of times. Keep the numbers small and manageable when you can.)

Now write the binary representation for the exponent, 20. We have $20 = 16 + 4$. So we take our table above and multiply those two answers together:

$$5^{20} = 5^{16}5^4 \equiv (-5)(15) = -75 \equiv -14 \equiv 47 \pmod{61}.$$

share|improve this answer
    
A not fun and not simplest method might be noting that $(5^{20})^3 $(mod 61) $\equiv 5^{60} $mod(61) $\equiv 1 $ (mod 61), and then "noticing" that 47 cubes to 1! Thomas' way probably works a bit better though... –  MGN Jun 26 '12 at 6:38
    
and then eliminating other cube root possibilities... so not really at all even. –  MGN Jun 26 '12 at 6:40
    
@MGNewman : Don't use $\cong$ for congruences... use $\equiv$! The symbol $\cong$ is usually for approximations or isomorphisms, not for congruences. =) –  Patrick Da Silva Jun 26 '12 at 6:40
    
UGH! You are of course right. I can generally catch my latex mistakes in the instant compiling answer bar thingy, but alas, my inadequacy has been revealed! (edited it, thanks) –  MGN Jun 26 '12 at 6:42

$5^{20} =25^{10} =625^{5} =(61\times 10 +15)^5$

now the problem is simplied to $15^5 =(15^4)\times15 =(225^2)\times15 =(61\times3 +42)^2 \times15$

now the problem is simplied to $42^2 \times15 = 1764 \times15 =(61\times28 +56)\times15$

now the problem is simplied to $56\times15 =840 = 61\times13 +47$

answer $47$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.