Two integers and are said to be congruent modulo a positive integer if and only if divides the difference of and (either or can be taken; divides one if and only if it divides the other). In other words, and are congruent modulo if and only if one of them can be obtained from the other by adding a multiple of . The fact that and are congruent modulo can be indicated by the notation
Congruence modulo 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 is similar to equality is that it has the following three properties.
- For every integer , is congruent to itself modulo . This is because the difference of in itself is 0 and every integer divides 0, including .
- For every pair of integers and , if is congruent to modulo , then is congruent to modulo . This is because if and only if .
- For every triple of integers , and , if is congruent to modulo and is congruent to modulo , then is also congruent to modulo . This is because if and , then .
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 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 the congruence class of modulo is the set of all integers congruent to modulo and is denoted . The three properties above can be stated in equivalent ways in terms of congruence classes.
- Every integer is a member of .
- For every pair of integers and , if is a member of , then is a member of .
- For every triple of integers , and , if is a member of and is a member of , then is a member of .
From property 1 it follows that every integer is a member of a congruence class modulo . It can also be proven that this congruence class is unique: no two distinct congruence classes modulo share a member. Suppose and are integers and an integer is a member of both and . Then is a member of , and is a member of , by property 2. Now, suppose is an integer. If is a member of , then is a member of (by property 3), which means it is a member of (by property 3 again). And if is a member of , then is a member of (by property 3), which means it is a member of (by property 3 again). So the members of and are exactly the same: that is, . And all that was required to prove this was the fact that was in both and . 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 and that is congruent to modulo if and only if . 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 and are congruent modulo . In this spirit, for every integer , can be called the residue of modulo . Also, 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 in this way, we call them integers modulo rather than congruence classes modulo . The set of all the integers modulo is denoted .
By thinking of members of in this way we can add and subtract them. Suppose and are integers modulo . To find or , we just take any pair of integers and whose residues are and respectively, and then and . Of course, we need to make sure that this process does not give different values depending on the values of and chosen. This is ensured by the following theorem.
Theorem 1 For every quadruple of integers , , and such that and are congruent modulo and and are congruent modulo , and are congruent modulo and and are congruent modulo . In other words, if and then and .
Proof: Since and are congruent modulo , . Since and are congruent modulo , . Therefore (which means and are congruent modulo ) and (which means and are congruent modulo ).
Integers modulo can be multiplied in exactly the same way: for every pair of integers and modulo , is the residue of where is any integer whose residue modulo is and is any integer whose residue modulo is . The uniqueness of this residue is ensured by the following theorem.
Theorem 2 For every quadruple of integers , , and such that and are congruent modulo and and are congruent modulo , and are congruent modulo . In other words, if and then .
Proof: Since and are congruent modulo , there is an integer such that . Since and are congruent modulo , there is an integer such that . Therefore : note that the first two terms have a common factor of , while the remaining term is , so we are done.
Every integer is congruent modulo to its remainder upon division by , because if we let and be the quotient and remainder, respectively, of in , then . Furthermore, is the only integer congruent to which is non-negative but less than , because if there were another such there would be an integer such that , so and would also be the quotient and remainder, respectively, of in . It follows that, since there are exactly possible remainders, there are exactly integers modulo : , , … and . This is one of the main reasons why the concept of integers modulo 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 , 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 integers modulo .
The fact that every integer is congruent modulo to its remainder upon division by allows us to give a simple algorithm for adding, subtracting and multiplying integers modulo , if, for each operand, we know at least one integer whose residue modulo is the operand. Let and be integers such that the first operand is and the second operand is . The algorithm goes as follows.
- Find the remainders and of in and respectively.
- Find the result of the operation on the integers and .
- Find the remainder of in . This is .
For example, (modulo 6), (modulo 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 and which are congruent modulo and every non-negative integer , and are congruent modulo . So, suppose you want to find the remainder of in . If is congruent to 0, 1 or modulo , then is congruent to , or modulo , which can all be easily computed no matter how large is. For example, let’s find the remainder of 3 in . 2 is congruent to modulo 3, and is 1 because 100 is even. So the remainder is 1. Even if is not congruent to one of these numbers, it may be possible to express as a product where and are integers and is congruent to 0, 1 or modulo . Then , which is congruent to , or modulo . For example, the remainder of 17 in is 1 because which is congruent to modulo 17.