Congruences and Residue Classes

Intro to Proofs · Axiom Academy

LESSON Congruences and Residue Classes A formal introduction to modular arithmetic: defining congruence, proving it is an equivalence relation, and exploring how it respects addition and multiplication. 1. The Definition of Congruence Equivalently: a and b leave the same remainder when divided by n . So every integer falls into one of n residue classes — one for each possible remainder . Two numbers are congruent exactly when they land in the same class. 2. Congruence Is an Equivalence Relation An equivalence relation must satisfy three properties: reflexivity , symmetry , and transitivity . Congruence mod n satisfies all three — which is exactly what lets it partition the integers into clean residue classes. Reflexive: a - a = 0 , and for every n . You can add congruences component-wise. Reducing first and then adding gives the same residue as adding first and then reducing — which is what makes modular arithmetic behave like ordinary arithmetic. 4. The Multiplication Property Congruences multiply too. This is the property behind fast modular exponentiation — computing huge powers by reducing at every step — which is the engine inside RSA and many other cryptosystems. You've built congruence from its definition all the way to the arithmetic that makes it a working number system. Scroll up to revisit any step.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.