Modular arithmetic without a calculator

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.

Re: Modular arithmetic without a calculator

Quote:

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.

By Euler's theorem,

$\displaystyle 5^{88}\equiv 1\pmod{89}$

$\displaystyle (5^{88})^{53}\equiv 1\pmod{89}$

$\displaystyle 5^{4664}\equiv 1\pmod{89}$

$\displaystyle 5^{4675}\equiv 5^{11}\pmod{89}$

Now proceed as you did in the case of $\displaystyle 3^{20}$ mod 71.

Re: Modular arithmetic without a calculator

I don't understand why you split 4675 into 88x53 + 11.

Re: Modular arithmetic without a calculator

Quote:

Originally Posted by

**terrorsquid** I don't understand why you split 4675 into 88x53 + 11.

Because:

$\displaystyle (5^{88})^{53} \times 5^{11} = 5^{4675}$

which we do because we know that $\displaystyle 5^{88} \equiv 1 \text{ mod } 89$ so we know that $\displaystyle (5^{88})^{53} \equiv 1 \text{ mod } 89$ which leaves us with:

$\displaystyle 5^{4675} \equiv 5^{11} \text{ mod } 89$

which is relatively easy to finish off.

CB

Re: Modular arithmetic without a calculator

So, you determined that 89 was prime, therefore $\displaystyle 5^{89-1} \equiv$ 1 mod 89... then found how many times 88 went into 4675 as a whole, leaving $\displaystyle 5^{11}$ which you can calculate easily. I think I understand the method, what do I search for in google if I wanted to learn the reasoning behind all this? Just "Euler's Theorem"?

Re: Modular arithmetic without a calculator

Quote:

Originally Posted by

**terrorsquid** I think I understand the method, what do I search for in google if I wanted to learn the reasoning behind all this? Just "Euler's Theorem"?

No, try "Fermat's Little Theorem". While "Euler's Theorem" may be technically correct since he was the first to publish a proof, Euler is responsible for so many results you will be swamped with other stuff if you search for "Euler's Theorem".

CB

Re: Modular arithmetic without a calculator

the number of positive integers from 1 to n-1 (inclusive) of numbers co-prime to n, has a special name, φ(n), or "totient of n".

euler's theorem states that if (k,n) = 1, that k^φ(n) = 1 (mod n).

for example, φ(6) = 2, because only 1 and 5 are co-prime to 6.

this means that we know (without calculating at all), that 25 = 1 (mod 6) (easy enough to check in your head).

if we have a prime p, then φ(p) = p-1, so for all 1 ≤ k < p, k^(p-1) = 1 (mod p).

so, for example, 7^12 = 1 (mod 13).

as a practical matter, let's look at your original example, 3^20 (mod 71).

i promise not to use my calculator for this....

71 is prime (hopefully you can see this at once). let's see if we can't take some lesser power, first.

3^20 = (3^4)^5. 3^4 is 81, and 81 is 10 (mod 71)

so 3^20 = 10^5 (mod 71). isn't that looking better?

10^5 = (100)(100)10, and 100 = 29 (mod 71).

so 10^5 = (29)(29)(10) (mod 71).

290 = 6 (mod 71) so 10^5 = (29)(6) (mod 71). looking pretty good, now.

(29)(6) = 174 = 32 (mod 71). there! all done :)