What is the simplest method to go about finding the remainder of $5^{20}$ divided by $61$?
Simplest method to find $5^{20}$ modulo $61$
-
1How 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$. – 2012-06-26
7 Answers
$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.
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}$.
$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}$.
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}.$
-
0UGH! 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) – 2012-06-26
$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$