# Thread: Modular arithmetic without a calculator

1. ## 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: $3^{20}$ mod 71

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

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

$0.4507042254\times 71 = 32$

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

Or I just find how many whole times 71 will go into $3^{20}$. multiply 71 by that number and then subtract it form $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):

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

2. ## Re: Modular arithmetic without a calculator

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: $3^{20}$ mod 71

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

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

$0.4507042254\times 71 = 32$

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

Or I just find how many whole times 71 will go into $3^{20}$. multiply 71 by that number and then subtract it form $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):

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

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

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

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

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

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

3. ## Re: Modular arithmetic without a calculator

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

4. ## Re: Modular arithmetic without a calculator

Originally Posted by terrorsquid
I don't understand why you split 4675 into 88x53 + 11.
Because:

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

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

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

which is relatively easy to finish off.

CB

5. ## Re: Modular arithmetic without a calculator

So, you determined that 89 was prime, therefore $5^{89-1} \equiv$ 1 mod 89... then found how many times 88 went into 4675 as a whole, leaving $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"?

6. ## Re: Modular arithmetic without a calculator

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

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

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# how to find modulus widout calculator

Click on a term to search for related topics.