TSSFL TECHNOLOGY STACK

In mathematics, congruence modulo (referred to as well modular arithmetic) is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus, see https://en.wikipedia.org/wiki/Modular_arithmetic. The idea is simply to divide by and then take the reminder.

Examples

Definition

Let be a positive integer. Then two integers and are said to be congruent mod , written as if

Question

Let be a positive integer. Show that the relation of congruence mod is an equivalence relation.

Solution

Note that

Thus,

(i) Reflexive:

(ii) Symmetric: Suppose

(iii) Transitive: Suppose and , then and


So and hence

Quiz

Show further that there are equivalence classes of the form