Originally Posted by

**terrorsquid** I think I am not understanding something properly as I keep having problems with modular arithmetic for some reason. For example, I am given this:

Compute: $\displaystyle 3^{20}$ mod 71

So I understand that there is a number x that is = $\displaystyle 3^{20}$ less a multiple of 71. So with my calculator I do the following:

$\displaystyle \frac{3^{20}}{71} = 49109639.4507042254$

$\displaystyle 0.4507042254\times 71 = 32$

$\displaystyle \therefore$ the original statement is congruent with 32 mod 71

Or I just find how many whole times 71 will go into $\displaystyle 3^{20}$. multiply 71 by that number and then subtract it form $\displaystyle 3^{20}$ to be left with 32.

I can't seem to understand my notes on how to do it without a calculator and now I have a problem doing the following (my calculator just shows error):

$\displaystyle 5^{4675}$ mod 89

Can someone walk me through what they are thinking/trying to do when breaking these down without a calculator? or direct me to a resource that does a better job of explaining this - I can't seem to grasp it yet.

Thanks.