Modular Arithmetic
By: Fabian Meraz
What is Modular Arithmetic?
Modular Arithmetic is all about remainders. Recall that the division theorem states that, “when we divide positive integers, we get a quotient and a remainder.” For a>0 and d>0, there are unique integers q and r such that
a=dq+r where 0≤r<d.
When we are doing modular arithmetic, we just care about the remainder.
Example:
For a ≡ b (mod m) , where m>0, the following are true:
a and b differ by a multiple of m
a=b+ mj for some integer j
a and b have the same remainder when divided by m
a mod m is equal to b mod m
Properties of modular arithmetic
If a≡ b (mod m) and c≡ d (mod m), then a+c ≡ b+d (mod m).
If a≡ b (mod m) and c≡ d (mod m), then ac ≡ bd (mod m).
if ax ≡ ay (mod m) and gcd (a,m)= 1, then x≡y (mod m).
Test question:
What is 125 (mod 6)?
What is 35 (mod 12)?
BONUS!
I found the following video very interesting because it shows how modular arithmetic is used for RSA encryption.