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.


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)?


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)


Discrete Math Arthur T. Benjamin