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:

We will demonstrate this using an example. What is 12 divided by 7? By the division theorem we have 12=7(1)+5. Note that the remainder is 5. Now we will compute 12 (mod 7). 12 (mod 7) is congruent to 5 (mod 7).

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.

Gambling with Secrets: 8/8 (RSA Encryption)

Sources:

Discrete Math Arthur T. Benjamin


http://www.youtube.com/watch?v=vgTtHV04xRI