Congruence and Modular Arithmetic

The second unit of a rings-first abstract algebra course. Equivalence relations and the partitions they make, congruence modulo n and its classes, the integers modulo n as a number system with well-defined addition and multiplication, and which of its elements can be inverted, proved in full, with the calendar, clock arithmetic and the numbers 1729 and 1001 as running examples.

The first of January 2026 was a Thursday, so what day is the first of January 2027? Nobody counts the 365 days one at a time. Since 365 leaves remainder 1 on division by 7, the answer is one weekday later, a Friday. A clock works the same way: eight hours after 7 o'clock it is 3 o'clock, whichever day it is. In both cases, integers that differ by a multiple of a fixed number are treated as the same, and the arithmetic still works. Why is that allowed, and what kind of number system does it produce?

This unit answers both questions. Making "treated as the same" precise needs a general idea, the equivalence relation, which sorts a set into disjoint classes. Congruence modulo $n$, the relation of differing by a multiple of $n$, is the leading example. Its classes can be added and multiplied, and with those operations they form the integers modulo $n$, written $\mathbb{Z}_n$. It is the first number system in the course outside the familiar chain of integers, rationals and reals.

The route has four steps, one per article.

  1. First, equivalence relations and the partitions they make, and the rule that a definition on classes must not depend on the representative chosen.
  2. Then congruence modulo $n$: its $n$ classes, one for each remainder of the division algorithm, and the rules for adding, multiplying and canceling congruences.
  3. Next, the classes become $\mathbb{Z}_n$. The central proof of the unit shows that adding and multiplying classes through representatives is well defined.
  4. Finally, division. Bezout's identity from the previous unit shows exactly which classes have inverses. It separates prime moduli, where every nonzero class can be inverted, from composite ones, where some nonzero classes multiply to zero.

The running examples are the calendar, the clock, and the pair 1729 and 1001 from Arithmetic in the Integers. There the Euclidean algorithm found $\gcd(1729, 1001) = 91$. Here that 91 is the reason 1001 has no inverse modulo 1729. Every number comes from a script in the site's repository.

The unit covers Chapter 2 of the course text (Hungerford, 2014), with the general theory of equivalence relations as in Judson (2026, §1.2). Every later unit uses it:

  • the ring axioms are abstracted from the laws of $\mathbb{Z}_n$;
  • the RSA cryptosystem computes in $\mathbb{Z}_n$;
  • the construction of $\mathbb{Z}_n$ from classes is repeated for polynomials, for ideals and for groups.

Articles

  • Equivalence Relations and Partitions: when can different objects be treated as the same? Relations, the reflexive, symmetric and transitive properties, and relations with only two of them. Equivalence classes, the proof that they partition the set, and the matching between equivalence relations and partitions. Fractions as classes of pairs of integers, and what makes a definition on classes well defined.
  • Congruence Modulo n: which rules of arithmetic survive when multiples of $n$ are ignored? The definition and its three equivalent forms, congruence as an equivalence relation with $n$ classes, and the rules for adding and multiplying congruences. When a common factor can be canceled. Applications to weekdays, digit checks on multiplication, and polynomials with no integer roots.
  • The Integers Modulo n: can the classes themselves be added and multiplied? The set $\mathbb{Z}_n$, the proof that its operations are well defined, and operations that are not. The laws of arithmetic in $\mathbb{Z}_n$, addition and multiplication tables, a quadratic equation with eight solutions, fast powers by repeated squaring, and unsigned integers in computers.
  • Units and Zero Divisors in the Integers Modulo n: which classes can we divide by? The theorem that $[a]$ is invertible exactly when $\gcd(a, n) = 1$, and inverses by the extended Euclidean algorithm. Zero divisors, and the proof that every nonzero class is one or the other. Prime moduli, linear equations $ax = b$ and their number of solutions, the group of units, and Wilson's theorem.

The unit builds on Arithmetic in the Integers: the division algorithm supplies the remainders, and Bezout's identity supplies the inverses. The laws proved for $\mathbb{Z}_n$ become the axioms of a ring in the next unit. The distinction between prime and composite moduli becomes the distinction between fields and rings with zero divisors. Powers in $\mathbb{Z}_p$ are the subject of Fermat's little theorem, the basis of the RSA cryptosystem.

References

  • Gauss, C. F. (1801). Disquisitiones Arithmeticae, Section 1 (articles 1 to 12). Leipzig: Gerhard Fleischer. The definition of congruence and the notation $\equiv$. record · 3 pages
  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), Chapter 2. Brooks/Cole, Cengage Learning. The course text. record · 44 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §1.2.3 and §3.1.1. Free online at judsonbooks.org. record · 44 pages