congruence modulo n

Two days of the week feel the same if they are a whole number of weeks apart — today and the day exactly 21 days from now are both, say, Tuesdays. Congruence modulo n captures that feeling for integers: two numbers count as congruent if they sit at the same spot once you wrap the number line around a circle of size n.

The definition: a is congruent to b modulo n, written a ≡ b (mod n), if n divides the difference a − b. Equivalently, a and b leave the same remainder when divided by n. For instance 38 ≡ 14 (mod 12) because their difference 24 is a multiple of 12, and indeed both leave remainder 2.

Congruence behaves like a well-mannered equals sign. It is reflexive, symmetric, and transitive, and it respects addition and multiplication: if a ≡ b and c ≡ d (mod n), then a + c ≡ b + d and a times c ≡ b times d (mod n). One trap: you may not freely cancel a common factor. From 6 ≡ 0 (mod 12) you cannot conclude 3 ≡ 0 (mod 12); cancellation is only safe when the factor is relatively prime to n.