Texas A&M University (TAMU) MATH 367 Structure of Mathematics III Test 1 Practice

Congruence modulo 3 on the integers is defined by a ~ b if and only if 3 divides a − b. This relation is an equivalence relation because it satisfies three properties.

First, reflexive: for any integer a, a − a = 0, and 0 is a multiple of 3, so a ~ a.

Second, symmetric: if a ~ b, then 3 divides a − b. Since a − b and b − a differ only by a sign, 3 also divides b − a, so b ~ a.

Third, transitive: if a ~ b and b ~ c, then 3 divides a − b and 3 divides b − c. Adding these gives 3 divides (a − b) + (b − c) = a − c, hence a ~ c.

Because all three properties hold, congruence modulo 3 is an equivalence relation. This also leads to partitioning the integers into the three residue classes modulo 3: numbers congruent to 0, 1, or 2 modulo 3.