## Properties of

If the equivalence relation is congruence modulo , , then equivalence classes are more often called residue classes. The element of a residue class mod with is called the remainder of mod . Moreover, a residue class is sometimes denoted by a bar rather than by square brackets:

(Of course, depends implicitly on .) In this case, the total possible number of distinct residue classes is finite (in fact, there are exactly such classes), .

Example 1.7.2   Let and , . Note that , . Also, and .

Lemma 1.7.3   Fix an integral modulus and let be integers.
• If and then

• If then .
• If and then . (cancellation mod m'')

proof: All of these are left as an exercise, except for the last one.

Assume and . Then . By Proposition 1.2.16(3), .

Example 1.7.4   Which values of satisfy ? Solution: Since , we can use cancellation mod 5 to reduce the congruence to . So the solutions are , for any integer .

Example 1.7.5   Which values of satisfy ? Solution: Since , we can use cancellation mod 17 to reduce the congruence to . Until we learn how to compute the inverse of mod (see below), we cannot divide by . However, the following strategy works just as easily: add multiples of to until we can divide by again. For example, . As above, by the cancellation law, . So the solutions are , for any integer .

Example 1.7.6   We shall now verify the divisibilty criteria for the cases and that were stated in §1.3.1, and leave the others as exercises.

We have , so . Substituting, we obtain

from which the divisibilty result for follows.

We have , so . Substituting, we obtain

from which the divisibilty result for follows.

The following result, which will be used later, is a consequence of the Euclidean algorithm.

Lemma 1.7.7   Let and be integers. is relatively prime to if and only if there is an integer such that .

The integer in the above lemma is called the inverse of modulo .

Example 1.7.8   is the inverse of itself modulo since .

proof: (only if) Assume . There are integers such that , by the Euclidean algorithm (more precisely, by Corollary 1.4.11). Thus .

(if) Assume . There is an integer such that . By Corollary 1.4.11 again, we must have .

More generally, we have the following result.

Proposition 1.7.9   Let and be integers. if and only if there is an integer such that .

The result above tells us exactly when we can solve the modulo analogs'' of the equation studied in elementary school. The proof (which requires the previous lemma and Proposition 1.2.16) is left as a good exercise.

David Joyner 2007-09-03