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.
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"?
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