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:

- 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), .

*We have , so . Substituting, we obtain*

*We have , so . Substituting, we obtain*

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

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

**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.

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