What is Modular Arithmetic?
Modular arithmetic is so ubiquitous in computer science. Yet most of us never learn it in our schools. Here in this article, I plan to demystify this technique. By the end of this article you would be able to answer questions like
What is the remainder when you divide 100000000000 by 7?
Before exploring modular arithmetic, let us first try to understand what the modulo operation is. It is a simple operation which is a cousin of the popular division (÷) operation. In the division operation say n ÷ m, we are interested in finding how many times a number n can be divided by another number m. (Note: Here n can be any integer. Integers are numbers like …, -2, -1, 0, 1, 2,… and m is assumed to be a positive integer like 1, 2, …). In the modulo operation, we are interested in finding the remainder (or left over) when n is divided by m. Let us do some examples.
10 ÷ 5 = 2
Since 5 divides 10 exactly, the remainder is 0. So
10 mod 5 = 0
Here I am using the word mod to represent the modulo operation. We could have used the symbol % to represent the modulo operation as used in programming languages like C, C++, Java and C#. But mod is the symbol used by computer scientists and mathematicians and so we will stick with it.
11 ÷ 5 = 2.2
We know 5 cannot divide 11 exactly and the remainder is 1. So
11 mod 5 = 1
Unlike division, modulo operation has strange properties. To show this let us perform mod 5 operation on few numbers in the range [-5, 19].
15 mod 5 = 0; 10 mod 5 = 0; 5 mod 5 = 0; 0 mod 5 = 0; -5 mod 5 = 0;
16 mod 5 = 1; 11 mod 5 = 1; 6 mod 5 = 1; 1 mod 5 = 1; -4 mod 5 = 1;
17 mod 5 = 2; 12 mod 5 = 2; 7 mod 5 = 2; 2 mod 5 = 2; -3 mod 5 = 2;
18 mod 5 = 3; 13 mod 5 = 3; 8 mod 5 = 3; 3 mod 5 = 3; -2 mod 5 = 3;
19 mod 5 = 4; 14 mod 5 = 4; 9 mod 5 = 4; 4 mod 5 = 4; -1 mod 5 = 4;
We see above that the result of mod 5 operation repeats and there can only be 5 distinct values possible namely {0, 1, 2, 3, 4}. Also {…, 15, 10, 5, 0, -5, …} are equivalent under mod 5 as they all give the remainder 0 when divided by 5. Similarly {…, 16, 11, 6, 1, -4, …} are equivalent under mod 5 as they all give the remainder 1 when divided by 5. Such sets of numbers form an equivalence family under mod 5. The technical term for this equivalence is congruence. We could express this as
(15 ≡ 10) mod 5 (read as 15 is congruent to 10 modulo 5)
(16 ≡ 11) mod 5 (read as 16 is congruent to 11 modulo 5)
The equivalence families can be expressed as
(15 ≡ 10 ≡ 5 ≡ 0 ≡ -5) mod 5
(16 ≡ 11 ≡ 6 ≡ 1 ≡ -4) mod 5
(17 ≡ 12 ≡ 7 ≡ 2 ≡ -3) mod 5
(18 ≡ 13 ≡ 8 ≡ 3 ≡ -2) mod 5
(19 ≡ 14 ≡ 9 ≡ 4 ≡ -1) mod 5
So let us generalize our observations.
Observation 1:
Let n be an integer and m be a positive integer.
If n mod m = r, i.e. if r is the remainder when n is divided by m, then r can take m distinct values {0, 1, 2, …, m-1}. And
(r ≡ n) mod m (read as r is congruent to n modulo m).
Observation 2:
Let {p, q} be integers and m be a positive integer.
If (p ≡ q) mod m, then p mod m = q mod m.
A keen reader would have noticed that in our example and generalization, we were dividing other numbers by a fixed number and analyzing the possible remainders. This fixed number was 5 in our example and m in our generalization. It is as if we are looking at all other numbers from the point of view of this fixed number and concentrating on the remainders those other numbers make with respect to this fixed number. This fixed number is called the modulus and the technique of using the arithmetic of remainders with respect to this fixed number is called modular arithmetic. The 18ᵗʰ century mathematician Carl Friedrich Gauss is credited with formalizing the modern approach to modular arithmetic.
Now we are ready to explore modular arithmetic using three interesting theorems (properties) that have wide applications.
Theorem 1 (modular addition):
Let {a, b, c, d} be integers and m be a positive integer.
If (a ≡ b) mod m and (c ≡ d) mod m, then
(a + c ≡ b + d) mod m
Proof:
Let {a, b, c, d} be integers and m be a positive integer.
We are given (a ≡ b) mod m and (c ≡ d) mod m.
So (a mod m = b mod m) and (c mod m = d mod m).
Let r₁ be the remainder when a and b are divided by m and r₂ be the remainder when c and d are divided by m. So
a = mp + r₁ (where mp means m multiplies p)
b = mq + r₁
c = ms + r₂
d = mt + r₂
where {p, q, s, t} are integers. Adding the expressions for a and c together and the expressions for b and d together, we get
a + c = m(p+s) + r₁ + r₂
b + d = m(q+t) + r₁ + r₂
So (a + c ≡ b + d) mod m since we get the same remainder (r₁ + r₂) when we divide (a + c) by m and when we divide (b + d) by m.
Theorem 2 (modular multiplication):
Let {a, b, c, d} be integers and m be a positive integer.
If (a ≡ b) mod m and (c ≡ d) mod m, then
(a × c ≡ b × d) mod m
Proof:
Let {a, b, c, d} be integers and m be a positive integer.
We are given (a ≡ b) mod m and (c ≡ d) mod m.
So (a mod m = b mod m) and (c mod m = d mod m).
Let r₁ be the remainder when a and b are divided by m and r₂ be the remainder when c and d are divided by m. So
a = mp + r₁ (where mp means m multiplies p)
b = mq + r₁
c = ms + r₂
d = mt + r₂
where {p, q, s, t} are integers. Multiplying the expressions for a and c together and the expressions for b and d together, we get
a x c = m²ps + mpr₂ + msr₁ + r₁r₂
b x d = m²qt + mqr₂ + mtr₁ + r₁r₂
So (a x c ≡ b x d) mod m since we get the same remainder (r₁r₂) when we divide (a x c) by m and when we divide (b x d) by m.
Corollary of theorem 2 (modular exponentiation):
Let {a, b} be integers and {n, m} be a positive integers.
If (a ≡ b) mod m, then
(aⁿ ≡ bⁿ) mod m
These theorems help us answer questions like:
What is 100000000000 mod 7 (or what is the remainder when you divide 100000000000 by 7)?
Solution:
We know 10 mod 7 = 3. So
(10 ≡ 3) mod 7
Using theorem 2 and the corollary to theorem 2 repeatedly, we get
(100 ≡ 9 ≡ 2) mod 7
(10000 ≡ 4) mod 7
(100000000 ≡ 16 ≡ 2) mod 7
(10000000000 ≡ 4) mod 7
(100000000000 ≡ 12 ≡ 5) mod 7
So the answer is 5.
To know more about modular arithmetic, I recommend the following books:
Mathematics for Computer Science — Eric Lehman, F Thomson Leighton, Albert Meyer. Free e-book available here.
Essential Discrete Mathematics for Computer Science — Harry Lewis, Rachel Zax. Available at Amazon.
