Engineering / Mathematics — Integer Foundations
Congruences and Modular Arithmetic
Congruence as an equivalence relation compatible with arithmetic, and the basic manipulation rules including where cancellation fails.
Executive summary
Congruence modulo n is the statement that two integers differ by a multiple of n. What makes it valuable is not the definition but its compatibility with addition and multiplication: congruences can be added and multiplied like equations.
Cancellation is the operation that does not transfer, and misapplying it is the most common error in elementary modular arithmetic.
Learning objectives
- Define congruence and verify it is an equivalence relation.
- Apply the arithmetic compatibility rules correctly.
- State the exact condition under which cancellation is valid.
01Definition and basic properties
Congruence
For a positive integer n, integers a and b are congruent modulo n, written a ≡ b (mod n), if n | (a − b).
Congruence modulo n is an equivalence relation — reflexive, symmetric and transitive — each following directly from the corresponding property of divisibility. It therefore partitions the integers into equivalence classes, and by division with remainder there are exactly n of them, represented by 0, 1, ..., n−1.
Arithmetic compatibility
If a ≡ b (mod n) and c ≡ d (mod n), then
a + c ≡ b + d, a − c ≡ b − d, ac ≡ bd (all mod n).
The multiplicative case is the one worth checking: ac − bd = ac − bc + bc − bd = c(a−b) + b(c−d), and n divides both terms. Iterating gives a^k ≡ b^k, which is the basis of modular exponentiation.
02Where cancellation fails
Cancellation law
If ac ≡ bc (mod n) and gcd(c, n) = 1, then a ≡ b (mod n).
More generally, if d = gcd(c, n) then ac ≡ bc (mod n) implies a ≡ b (mod n/d).
The failure is structural rather than incidental. When gcd(c, n) > 1, the element c is a zero divisor modulo n, and zero divisors are exactly the obstruction to cancellation in any ring.
This is the first point at which the choice of modulus matters qualitatively. For prime n, every non-zero residue is coprime to n, so cancellation always works and the residues form a field. For composite n they do not.
03Working with congruences in practice
- Reduce early
a mod nKeep operands small; reduce after every operation, not at the end - Powers
a^k mod nNever compute a^k first; use repeated squaring with reduction at each step - Division
a · c⁻¹ mod nRequires gcd(c, n) = 1; the inverse comes from extended Euclid - Sign
((a mod n) + n) mod nNormalise after operations that may produce negatives
04Frequently asked questions
Why is congruence written with a modulus in parentheses rather than as an operator?
Because it is a relation between two integers, parameterised by n, not a function applied to one. The notation a mod n for the least non-negative residue is a related but distinct object — a specific integer rather than a statement.
Can the modulus be negative or zero?
Congruence modulo n and modulo −n are the same relation, so negative moduli add nothing. Modulo 0 the relation degenerates to equality, and modulo 1 every pair of integers is congruent; both are technically valid and practically useless.
Why does cancellation work for prime moduli?
Because every non-zero residue modulo a prime is coprime to the prime, so the gcd condition is automatic. This is the same fact as Z_p being a field, and it is why prime moduli are used wherever division is needed.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 13-15.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.