An introduction to modular arithmetic

Two integers {a} and {b} are said to be congruent modulo a positive integer {m} if and only if {m} divides the difference of {a} and {b} (either {a - b} or {b - a} can be taken; {m} divides one if and only if it divides the other). In other words, {a} and {b} are congruent modulo {m} if and only if one of them can be obtained from the other by adding a multiple of {m}. The fact that {a} and {b} are congruent modulo {m} can be indicated by the notation

\displaystyle a \equiv b \mod m.

Congruence modulo {m} is similar to equality. Of course, “similar” is kind of a vague term, and if we’re doing proper maths we have to speak precisely. What I mean when I say that congruence modulo {m} is similar to equality is that it has the following three properties.

  1. For every integer {a}, {a} is congruent to itself modulo {m}. This is because the difference of {a} in itself is 0 and every integer divides 0, including {m}.
  2. For every pair of integers {a} and {b}, if {a} is congruent to {b} modulo {m}, then {b} is congruent to {a} modulo {m}. This is because {m \mid a - b} if and only if {m \mid b - a}.
  3. For every triple of integers {a}, {b} and {c}, if {a} is congruent to {b} modulo {m} and {b} is congruent to {c} modulo {m}, then {a} is also congruent to {c} modulo {m}. This is because if {m \mid a - b} and {m \mid b - c}, then {m \mid (a - b) + (b - c) = a - c}.

You can see that all three of these properties (which have names: 1 is reflexivity, 2 is symmetry, 3 is transitivity) are also properties of equality, so having these properties does mean that congruence modulo {m} is similar to equality. By the way, any relation which is similar to equality in this way is called an equivalence relation\textemdash I’m not going to dwell on the concept here but it’s a very useful one which turns up everywhere in mathematics.

For every integer {a} the congruence class of {a} modulo {m} is the set of all integers congruent to {a} modulo {m} and is denoted {[a]}. The three properties above can be stated in equivalent ways in terms of congruence classes.

  1. Every integer {a} is a member of {[a]}.
  2. For every pair of integers {a} and {b}, if {a} is a member of {[b]}, then {b} is a member of {[a]}.
  3. For every triple of integers {a}, {b} and {c}, if {a} is a member of {[b]} and {b} is a member of {[c]}, then {a} is a member of {[c]}.

From property 1 it follows that every integer is a member of a congruence class modulo {m}. It can also be proven that this congruence class is unique: no two distinct congruence classes modulo {m} share a member. Suppose {a} and {b} are integers and an integer {c} is a member of both {[a]} and {[b]}. Then {a} is a member of {[c]}, and {b} is a member of {[c]}, by property 2. Now, suppose {d} is an integer. If {d} is a member of {[a]}, then {d} is a member of {[c]} (by property 3), which means it is a member of {[b]} (by property 3 again). And if {d} is a member of {[b]}, then {d} is a member of {[c]} (by property 3), which means it is a member of {[a]} (by property 3 again). So the members of {[a]} and {[b]} are exactly the same: that is, {[a] = [b]}. And all that was required to prove this was the fact that {c} was in both {[a]} and {[b]}. Note that all of this reasoning relied only on properties 1-3, so it is still valid for any equivalence relation, not just congruence.

The point of proving this is we can now say for every pair of integers {a} and {b} that {a} is congruent to {b} modulo {m} if and only if {[a] = [b]}. So adding the square brackets turns congruence into actual equality. The square brackets abstract away all the unimportant distinctions between integers and allow us to focus only on the distinction we care about: whether {a} and {b} are congruent modulo {m}. In this spirit, for every integer {a}, {[a]} can be called the residue of {a} modulo {m}. Also, {[a]} should not be thought of as a set, of a different kind to its members, but as an object of the same kind: a kind of number, in other words. When we are thinking about congruence classes modulo {m} in this way, we call them integers modulo {m} rather than congruence classes modulo {m}. The set of all the integers modulo {m} is denoted {\mathbb Z_m}.

By thinking of members of {\mathbb Z_m} in this way we can add and subtract them. Suppose {a} and {b} are integers modulo {m}. To find {a + b} or {a - b}, we just take any pair of integers {a'} and {b'} whose residues are {a} and {b} respectively, and then {a + b = [a' + b']} and {a - b = [a' - b']}. Of course, we need to make sure that this process does not give different values depending on the values of {a'} and {b'} chosen. This is ensured by the following theorem.

Theorem 1 For every quadruple of integers {a_1}, {a_2}, {b_1} and {b_2} such that {a_1} and {b_1} are congruent modulo {m} and {a_2} and {b_2} are congruent modulo {m}, {a_1 + a_2} and {b_1 + b_2} are congruent modulo {m} and {a_1 - a_2} and {b_1 - b_2} are congruent modulo {m}. In other words, if {[a_1] = [b_1]} and {[a_2] = [b_2]} then {[a_1 + a_2] = [b_1 + b_2]} and {[a_1 - a_2] = [b_1 - b_2]}.

Proof: Since {a_1} and {b_1} are congruent modulo {m}, {m \mid a_1 - b_1}. Since {a_2} and {b_2} are congruent modulo {m}, {m \mid a_2 - b_2}. Therefore {m \mid (a_1 - b_1) + (a_2 - b_2) = (a_1 + a_2) - (b_1 + b_2)} (which means {a_1 + a_2} and {b_1 + b_2} are congruent modulo {m}) and {m \mid (a_1 - b_1) - (a_2 - b_2) = (a_1 - a_2) - (b_1 - b_2)} (which means {a_1 - a_2} and {b_1 - b_2} are congruent modulo {m}). \Box

Integers modulo {m} can be multiplied in exactly the same way: for every pair of integers {a} and {b} modulo {m}, {a b} is the residue of {a' b'} where {a'} is any integer whose residue modulo {m} is {a} and {b'} is any integer whose residue modulo {m} is {b}. The uniqueness of this residue is ensured by the following theorem.

Theorem 2 For every quadruple of integers {a_1}, {a_2}, {b_1} and {b_2} such that {a_1} and {b_1} are congruent modulo {m} and {a_2} and {b_2} are congruent modulo {m}, {a_1 a_2} and {b_1 b_2} are congruent modulo {m}. In other words, if {[a_1] = [b_1]} and {[a_2] = [b_2]} then {[a_1 a_2] = [b_1 b_2]}.

Proof: Since {a_1} and {b_1} are congruent modulo {m}, there is an integer {q_1} such that {a_1 = q_1 m + b_1}. Since {a_2} and {b_2} are congruent modulo {m}, there is an integer {q_2} such that {a_2 = q_2 m + b_2}. Therefore {a_1 a_2 = (q_1 m + b_1) (q_2 m + b_2) = q_1 q_2 m^2 + (q_1 b_2 + q_2 b_1) m + b_1 b_2}: note that the first two terms have a common factor of {m}, while the remaining term is {b_1 b_2}, so we are done. \Box

Every integer {a} is congruent modulo {m} to its remainder upon division by {m}, because if we let {q} and {r} be the quotient and remainder, respectively, of {m} in {a}, then {a = q m + r}. Furthermore, {r} is the only integer congruent to {a} which is non-negative but less than {m}, because if there were another such {r'} there would be an integer {q'} such that {a = q' m + r'}, so {q'} and {r'} would also be the quotient and remainder, respectively, of {m} in {a}. It follows that, since there are exactly {m} possible remainders, there are exactly {m} integers modulo {m}: {[0]}, {[1]}, … and {[m - 1]}. This is one of the main reasons why the concept of integers modulo {m} is useful. There are infinitely many integers, so if you want to find out whether some property holds for all integers, you have to use some kind of clever proof; you can’t just check every integer. But if you can prove that for every pair of integers congruent modulo {m}, the property either holds for both or holds for neither, then all you need to do is check whether the property holds for each of the {m} integers modulo {m}.

The fact that every integer {a} is congruent modulo {m} to its remainder upon division by {m} allows us to give a simple algorithm for adding, subtracting and multiplying integers modulo {m}, if, for each operand, we know at least one integer whose residue modulo {m} is the operand. Let {a} and {b} be integers such that the first operand is {[a]} and the second operand is {[b]}. The algorithm goes as follows.

  1. Find the remainders {r_a} and {r_b} of {m} in {a} and {b} respectively.
  2. Find the result {x} of the operation on the integers {r_a} and {r_b}.
  3. Find the remainder {r} of {m} in {x}. This is {[a] + [b]}.

For example, {[5] - [9] = [5] - [3] = [2]} (modulo 6), {[233] + [282] = [2] + [1] = [3] = [0]} (modulo 3), {[15] [125] = [3] [1] = [3]} (modulo 4).

One cool thing about modular arithmetic is that it makes it easy to compute the remainders of arbitrarily high powers. By applying Theorem 2 it follows that for every pair of integers {a} and {b} which are congruent modulo {m} and every non-negative integer {n}, {a^n} and {b^n} are congruent modulo {m}. So, suppose you want to find the remainder of {m} in {a^n}. If {a} is congruent to 0, 1 or {-1} modulo {m}, then {a^n} is congruent to {0^n}, {1^n} or {(-1)^n} modulo {m}, which can all be easily computed no matter how large {n} is. For example, let’s find the remainder of 3 in {2^{100}}. 2 is congruent to {-1} modulo 3, and {(-1)^{100}} is 1 because 100 is even. So the remainder is 1. Even if {a} is not congruent to one of these numbers, it may be possible to express {n} as a product {k l} where {k} and {l} are integers and {a^k} is congruent to 0, 1 or {-1} modulo {m}. Then {a^n = a^{k l} = (a^k)^l}, which is congruent to {0^l}, {1^l} or {(-1)^l} modulo {m}. For example, the remainder of 17 in {2^{100}} is 1 because {2^{100} = 2^(4 \cdot 25) = 16^25} which is congruent to {1^25} modulo 17.

Advertisements

One response to “An introduction to modular arithmetic

  1. Pingback: How to compute remainders in your head, and why prime bases aren’t such a bad idea | The House Carpenter

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s