# Simplest method to find $5^{20}$ modulo $61$

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

-
The simplest method is probably to use a calculator. But you are probably inquiring about elegant methods of computing this. – arjafi Jun 26 '12 at 6:55
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

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

-

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

-

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.

-

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

-

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

-

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

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

-