Thread: 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: mod 71

So I understand that there is a number x that is = less a multiple of 71. So with my calculator I do the following:





the original statement is congruent with 32 mod 71

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

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.

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: mod 71

So I understand that there is a number x that is = less a multiple of 71. So with my calculator I do the following:





the original statement is congruent with 32 mod 71

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

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,









Now proceed as you did in the case of mod 71.

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

Originally Posted by terrorsquid

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

Because:



which we do because we know that so we know that which leaves us with:



which is relatively easy to finish off.

CB

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

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

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