Engineering/Mathematics/Foundations of number theory

Congruences and Modular Arithmetic

Reducing modulo n replaces an infinite ring by a finite one without losing addition or multiplication. Understanding exactly what survives that collapse — and what does not, such as free cancellation and square roots — is the difference between correct modular code and code that fails only on rare inputs.

Working algebra
Number theory
Applied daily
≈17 min read
Feeds RSA, DH, hashing

ℤ_nFinite ringThe n residue classes modulo n form a commutative ring with unity under the induced operations.

gcd = 1Invertibility test[a]_n is a unit exactly when gcd(a,n) = 1. This is decided in O(ℓ²) time with no factoring.

CRTDecompositionFor coprime moduli, ℤ_n₁n₂ ≅ ℤ_n₁ × ℤ_n₂ as rings — the single most exploited isomorphism in the field.

×4RSA speed-upSigning with CRT on the two prime factors costs roughly one quarter of the direct exponentiation, a routine implementation gain.

Executive summary

A congruence a ≡ b (mod n) asserts that n ∣ (a − b). Because divisibility by n is preserved by addition and multiplication, congruence is a compatible equivalence relation: the quotient set inherits a ring structure. That quotient, ℤ_n, is where practically all computation in this library actually happens.

Three questions organise the topic. Which elements are invertible? When does a linear congruence have a solution, and how many? And how do the pieces of a composite modulus interact? The answers are, respectively, the units criterion, the solvability criterion for ax ≡ b, and the Chinese remainder theorem.

Relationa ≡ b (mod n)

n divides the difference. An equivalence relation compatible with + and ×.

Objectℤ_n

The set of residue classes, a commutative ring with unity of size n.

Subgroupℤ*_n

The units: classes with gcd(a,n)=1. Size φ(n). Abelian group under multiplication.

DecompositionCRT

Coprime factorisation of the modulus splits the ring into a direct product.

Contents

Definitions and basic properties

Definition D1

Congruence

For n > 0 and a,b ∈ ℤ, write a ≡ b (mod n) when n ∣ (a − b), equivalently when a mod n = b mod n. The relation is reflexive, symmetric and transitive, and it respects the ring operations:

a ≡ a′ and b ≡ b′ ⟹ a + b ≡ a′ + b′ and ab ≡ a′b′ (mod n)Compatibility — the reason the quotient inherits a ring structure rather than only a set structure.

Compatibility is what licenses the everyday practice of reducing intermediate results. In an expression built from +, − and ×, you may reduce modulo n at any point without changing the final class. This bounds operand size and is the reason modular arithmetic is computationally attractive in the first place.

What does not survive reduction

Division, order comparison and exponent arithmetic do not transfer. From a ≡ b (mod n) you may not conclude x^a ≡ x^b; exponents live modulo the order of x, not modulo n. Nor is there any meaningful sense in which one residue class is larger than another.

Contents

The ring ℤn and its units

The residue class of a is [a]_n = a + nℤ. Defining [a] + [b] = [a+b] and [a][b] = [ab] is well defined precisely because of compatibility, and the resulting structure ℤ_n is a commutative ring with unity [1] and exactly n elements.

Theorem T1

Units criterion

[a]_n has a multiplicative inverse if and only if gcd(a,n) = 1, and the inverse is then unique. Proof: gcd(a,n)=1 gives as + nt = 1, so [a][s] = [1]. Conversely [a][b]=[1] means ab − 1 = kn, so any common divisor of a and n divides 1.

The units form a group ℤ*_n under multiplication, of order φ(n). Two structural corollaries follow at once:

ℤ_n is a field ⟺ n is prime. For prime p every non-zero class is a unit, and the field is written ℤ_p or F_p.
For composite n there are zero divisors: if n = ab with 1 < a,b < n then [a][b] = [0] with neither factor zero. Zero divisors are exactly what breaks cancellation.
A failed inversion is informative: if gcd(a,n) = d > 1 then d is a non-trivial factor of n. Several factoring algorithms are built on provoking exactly this event.

Theorem T2

Cancellation

If gcd(a,n) = 1 and ax ≡ ay (mod n) then x ≡ y (mod n). In general ax ≡ ay (mod n) implies only x ≡ y (mod n/gcd(a,n)) — the modulus shrinks rather than the conclusion holding outright.

Contents

Solving linear congruences

The complete solvability picture, with the count of solutions.

Theorem T3

Solvability of ax ≡ b (mod n)

Let d = gcd(a,n). The congruence ax ≡ b (mod n) has a solution if and only if d ∣ b. When it does, the solution set is a single residue class modulo n/d, and therefore consists of exactly d distinct classes modulo n.

Compute d = gcd(a, n) with the extended Euclidean algorithm
The same run also produces s,t with as + nt = d. Cost is O(ℓ²) bit operations for ℓ-bit inputs.
Test divisibility d ∣ b
If it fails, there is no solution and the work stops here. This is the only obstruction.
Reduce to a coprime problem
Divide through: (a/d)x ≡ (b/d) (mod n/d), where now gcd(a/d, n/d) = 1.
Invert and multiply
x ≡ (b/d)·s (mod n/d) using the Bézout coefficient s, which inverts a/d modulo n/d.
Lift back if all solutions modulo n are wanted
Add multiples of n/d to enumerate the d classes modulo n.

Worked example

Solve 18x ≡ 30 (mod 42). Here d = gcd(18,42) = 6 and 6 ∣ 30, so solutions exist. Dividing gives 3x ≡ 5 (mod 7); since 3·5 = 15 ≡ 1 (mod 7), the inverse of 3 is 5, so x ≡ 25 ≡ 4 (mod 7). Modulo 42 the solution set is {4, 11, 18, 25, 32, 39} — six classes, as predicted.

Contents

The Chinese remainder theorem

Theorem T4

CRT, ring form

ℤ_{n₁n₂⋯n_k} ≅ ℤ_n₁ × ℤ_n₂ × ⋯ × ℤ_{n_k}valid whenever the moduli are pairwise coprime; the isomorphism sends [a] to the tuple of its reductions

Equivalently: for pairwise coprime n_i and arbitrary targets a_i, the system x ≡ a_i (mod n_i) has a solution, unique modulo n = ∏ n_i.

The proof is constructive and is the algorithm: with n_i* = n/n_i, coprimality gives inverses m_i = (n_i*)⁻¹ mod n_i, and x = ∑ a_i n_i* m_i works because each term vanishes modulo every other modulus.

What the isomorphism is used for
Application	Mechanism	Effect
RSA private operation	Exponentiate modulo p and q separately, recombine	Roughly a fourfold speed-up: two half-size exponentiations instead of one full-size
Multi-modular arithmetic	Compute modulo several word-size primes, reconstruct	Turns big-integer linear algebra into parallel small-integer work
Structure of ℤ*_n	Units decompose as ∏ ℤ*_p^e	Gives multiplicativity of φ and the square-root count modulo composites
Secret sharing and error correction	Residues act as redundant shares of an integer	Underlies residue number systems and CRT-based sharing schemes
Counting square roots	Each odd prime factor contributes two roots	n with k distinct odd prime factors has 2^k square roots of 1

Coprimality is not optional

With non-coprime moduli the system x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂) is solvable if and only if a₁ ≡ a₂ (mod gcd(n₁,n₂)), and the solution is then unique modulo lcm(n₁,n₂). Code that assumes the coprime case silently produces wrong answers rather than errors.

Contents

Orders, exponents and the first hard problem

For a unit α ∈ ℤ*_n, the multiplicative order is the least k > 0 with α^k = 1. Orders divide the group order φ(n), which is Lagrange's theorem specialised to this group.

Exponents reduce modulo the order, not modulo n: α^e = α^{e mod ord(α)}. In RSA this is why the private exponent is taken modulo φ(n) — or better, modulo λ(n), the exponent of the group.
Given α and α^x, recovering x is the discrete logarithm problem. Addition and multiplication modulo n are easy; this inverse question is not known to be.
Squaring is not injective on ℤ*_n for n with several prime factors, so “the” square root of a residue does not exist. Extracting square roots modulo a composite is computationally equivalent to factoring it.

Where the library goes next

Congruences give the arena; the interesting questions are about the multiplicative structure inside it. Counting units leads to Euler's phi function and Fermat's little theorem; finding elements of maximal order leads to generators and discrete logarithms; deciding which residues are squares leads to quadratic reciprocity.

Contents

Common mistakes

Modular arithmetic failure modes
Mistake	Symptom	Correct practice
Reducing exponents modulo n	Wrong results in exponentiation, often only for large exponents	Reduce exponents modulo the group order or λ(n)
Cancelling a non-unit	Solutions lost or spurious solutions gained	Divide the modulus by gcd(a,n) as well
Assuming a unique solution to ax ≡ b	Missing d − 1 of the d solution classes	Report all d = gcd(a,n) classes
Applying CRT to non-coprime moduli	Silent wrong answers	Check pairwise gcds; use the compatibility condition
Ignoring negative remainders in code	Rare, input-dependent defects	Normalise to [0,n) at every boundary
Timing-variable reduction in crypto code	Side-channel leakage of secret operands	Use constant-time reduction routines for secret data

Contents

Quick reference

Modular identities worth memorising
Identity	Condition
a ≡ b (mod n) ⟺ n ∣ (a−b)	always
ax ≡ ay ⇒ x ≡ y (mod n/gcd(a,n))	always
a⁻¹ mod n exists	gcd(a,n) = 1
\|ℤ*_n\| = φ(n)	always
ax ≡ b (mod n) solvable	gcd(a,n) ∣ b; then gcd(a,n) solutions
ℤ_mn ≅ ℤ_m × ℤ_n	gcd(m,n) = 1
ℤ_n is a field	n prime
ord(α) ∣ φ(n)	α ∈ ℤ*_n

Why is ℤ_n defined with residue classes rather than the symbols 0…n−1?

The two definitions are isomorphic and the concrete one is what implementations use. The class-based definition is preferred in proofs because it makes the ring homomorphism ℤ → ℤ_n and the CRT decomposition natural rather than something to be checked by hand.

How do I choose between reducing eagerly and reducing lazily?

Eager reduction after every operation keeps operands bounded and is the safe default. Lazy reduction — allowing intermediate values to grow to a few machine words before reducing — is faster in tight loops but requires a careful bound argument to guarantee no overflow.

Is ℤ*_n always cyclic?

No. It is cyclic exactly when n is 1, 2, 4, p^e or 2p^e for an odd prime p. For RSA moduli n = pq it is not cyclic, which is why the group exponent λ(n) = lcm(p−1,q−1) is smaller than φ(n).

Does CRT help if the factorization of the modulus is unknown?

No — and that asymmetry is deliberate in cryptography. The holder of the factorization gets the fourfold RSA speed-up; an attacker without it cannot use the decomposition at all.

Contents

References and further reading

V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 2 (congruences) and §4.3 (Chinese remaindering).
A. J. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996 — Chapter 2 and §14.5, including CRT-based RSA.
D. E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed., 1997 — §4.3.2 on modular arithmetic and residue number systems.
H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1993 — §1.3 on practical CRT reconstruction.

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: congruences-and-modular-arithmeticReview cycle: annual

Congruences and Modular Arithmetic

Executive summary

Definitions and basic properties

Congruence

The ring ℤn and its units

Units criterion

Cancellation

Solving linear congruences

Solvability of ax ≡ b (mod n)

Compute d = gcd(a, n) with the extended Euclidean algorithm

Test divisibility d ∣ b

Reduce to a coprime problem

Invert and multiply

Lift back if all solutions modulo n are wanted

The Chinese remainder theorem

CRT, ring form

Orders, exponents and the first hard problem

Common mistakes

Quick reference

References and further reading

Continue learning

KEVOS Intelligence

Executive summary

Definitions and basic properties

Congruence

The ring ℤn and its units

Units criterion

Cancellation

Solving linear congruences

Solvability of ax ≡ b (mod n)

Compute d = gcd(a, n) with the extended Euclidean algorithm

Test divisibility d ∣ b

Reduce to a coprime problem

Invert and multiply

Lift back if all solutions modulo n are wanted

The Chinese remainder theorem

CRT, ring form

Orders, exponents and the first hard problem

Common mistakes

Quick reference

Related pages in this library

References and further reading

Continue learning