Solving linear congruences (intro) - Discrete Math

SECTION 1

Historical Context & Motivation

The study of linear congruences is among the oldest problems in number theory, arising naturally whenever one asks about divisibility patterns and remainders. Ancient civilizations recognized that certain arithmetic problems—distributing objects into equal groups, scheduling recurring events, or solving puzzles about unknown quantities—reduce to questions about residues modulo an integer. The formal language of congruences, however, took centuries to develop, and its codification transformed number theory from a collection of clever tricks into a rigorous algebraic discipline. Today, solving equations of the form ax ≡ b (mod m) is a gateway skill for understanding modular arithmetic and its profound applications in cryptography, coding theory, and computer science.

~300 CE • Sun Zi's Remainder Problem

The Chinese mathematician Sun Zi posed a problem in the Sunzi Suanjing asking for a number that leaves specific remainders when divided by 3, 5, and 7—one of the earliest known systems of simultaneous linear congruences.

628 • Brahmagupta's Kuttaka Method

The Indian mathematician Brahmagupta refined the kuttaka ('pulverizer') algorithm, an iterative procedure closely related to the Extended Euclidean Algorithm, for solving linear Diophantine equations—the integer-valued cousins of linear congruences.

1801 • Gauss's Disquisitiones Arithmeticae

Carl Friedrich Gauss published his landmark treatise, introducing the ≡ notation for congruences and systematically developing the theory of modular arithmetic, including existence and uniqueness conditions for solutions of linear congruences.

1977 • RSA Cryptosystem

Rivest, Shamir, and Adleman published the RSA algorithm, whose key generation step requires computing modular inverses—precisely the operation at the heart of solving linear congruences. This cemented modular arithmetic as essential infrastructure for digital security.

The central question that linear congruences address is deceptively simple: given integers a, b, and m, can we find an integer x such that ax leaves remainder b upon division by m? Under what conditions does a solution exist, and when it does, how many solutions are there modulo m? These questions lead directly to the concept of modular inverses and the role of the greatest common divisor as the arbiter of solvability.

SECTION 2

Core Principles & Definitions

Before solving linear congruences, we need to establish the precise definitions and foundational results that govern their behavior. A congruence a ≡ b (mod m) asserts that m divides the difference a − b, or equivalently, that a and b share the same remainder when divided by m. A linear congruence is an equation of the form ax ≡ b (mod m), where a, b, m are given integers with m > 0, and x is the unknown. The following principles form the backbone of the theory.

Congruence as Equivalence

The relation ≡ (mod m) is an equivalence relation on ℤ: it is reflexive, symmetric, and transitive. It partitions the integers into m distinct residue classes {0, 1, 2, …, m−1}.

Existence Theorem

The congruence ax ≡ b (mod m) has a solution if and only if gcd(a, m) divides b. This is the single most important criterion: if d = gcd(a, m) does not divide b, no solution exists.

Number of Solutions

When a solution exists with d = gcd(a, m), there are exactly d incongruent solutions modulo m. In the special case where gcd(a, m) = 1, the solution is unique modulo m.

Modular Inverse

When gcd(a, m) = 1, the integer a has a multiplicative inverse modulo m: an integer a⁻¹ such that a · a⁻¹ ≡ 1 (mod m). The solution to ax ≡ b (mod m) is then x ≡ a⁻¹b (mod m).

Extended Euclidean Algorithm

The Extended Euclidean Algorithm computes integers s and t such that as + mt = gcd(a, m). The coefficient s (reduced mod m) yields the modular inverse when gcd(a, m) = 1.

✦

KEY TAKEAWAY

Think of a linear congruence ax ≡ b (mod m) as trying to 'hit a target' on a circular number line with m positions. Each step of size a moves you forward around the circle. The question is: can you land exactly on position b? The gcd(a, m) determines how many positions on the circle are reachable—if d = gcd(a, m), only every d-th position is accessible. So b must be one of those accessible positions (i.e., d | b), or you can never reach it.

SECTION 3

Visual Explanation

The following diagram illustrates how the residues of multiples of a behave modulo m, depicting the 'stepping around a clock' metaphor. We visualize ℤ/mℤ as a circular arrangement of m positions and trace where successive multiples of a land, revealing the connection between gcd(a, m) and reachability.

Left: When gcd(a, m) = 3, only positions that are multiples of 3 are reachable (highlighted in cyan). Right: When gcd(a, m) = 1, every position on the circle is reachable (all highlighted in green), guaranteeing a unique solution for any right-hand side b.

The diagram above makes the existence theorem visually immediate. On the left, with a = 3 and m = 9, the multiples of 3 modulo 9 cycle through only {0, 3, 6}, covering exactly 9/gcd(3,9) = 3 distinct residues. Consequently, 3x ≡ b (mod 9) is solvable only when b ∈ {0, 3, 6}—precisely the multiples of d = 3. On the right, with a = 5 and m = 9, the gcd is 1, so stepping by 5 visits every residue class before returning to the start. This is why coprimality of a and m guarantees not merely existence but uniqueness of the solution modulo m. Understanding this geometric picture provides strong intuition for why the Extended Euclidean Algorithm works: it is essentially constructing the precise sequence of steps needed to reach any given target on the circle.

SECTION 4

Mathematical Framework

We now formalize the theory. The fundamental objects are the linear congruence equation and the conditions that govern its solution set. Throughout, we let a, b, m ∈ ℤ with m > 0.

LINEAR CONGRUENCE

ax ≡ b (mod m)

This states that m | (ax − b), or equivalently, there exists an integer k such that ax = b + km. The unknowns are x ∈ ℤ.

EXISTENCE CONDITION

ax ≡ b (mod m) has a solution ⟺ gcd(a, m) | b

Let d = gcd(a, m). The congruence is equivalent to the Diophantine equation ax − my = b, which by Bézout's identity has integer solutions if and only if d divides b.

SOLUTION COUNT

If d | b, there are exactly d incongruent solutions modulo m

If x₀ is one solution, the complete solution set is x ≡ x₀ + k(m/d) (mod m) for k = 0, 1, …, d−1. When d = 1, there is exactly one solution modulo m.

REDUCTION TO COPRIME CASE

ax ≡ b (mod m) → (a/d)x ≡ (b/d) (mod m/d) where d = gcd(a, m)

When d > 1 and d | b, divide every coefficient by d. The reduced congruence has gcd(a/d, m/d) = 1, so the modular inverse of a/d modulo m/d exists and yields the unique base solution x₀ modulo m/d.

ℹ

Connection to Bézout's Identity

The Extended Euclidean Algorithm applied to (a, m) produces integers s and t with as + mt = d. When d | b, multiply through by b/d to get a(sb/d) + m(tb/d) = b, showing that x₀ = sb/d is a particular solution. Reducing x₀ modulo m/d gives the base solution in the coprime formulation. This algorithmic connection is why the Extended Euclidean Algorithm is the standard computational tool for solving linear congruences.

SECTION 5

Solution Algorithm & Classification

With the theory established, we can organize the solution procedure into a systematic algorithm. The flowchart below captures the decision logic, while the subsequent table classifies the different scenarios one may encounter when solving a linear congruence.

The flowchart proceeds top to bottom: compute the gcd, test divisibility, reduce to the coprime case, find the modular inverse via the Extended Euclidean Algorithm, and enumerate all d incongruent solutions.

Scenario	Condition	# Solutions (mod m)	Example
No solution	gcd(a, m) ∤ b	0	4x ≡ 3 (mod 6): gcd(4,6) = 2 ∤ 3
Unique solution	gcd(a, m) = 1	1	3x ≡ 5 (mod 7): gcd(3,7) = 1
Multiple solutions	d = gcd(a,m) > 1 and d \| b	d	6x ≡ 4 (mod 8): gcd(6,8) = 2 \| 4 → 2 soln's
Trivial (a ≡ 0)	a ≡ 0 (mod m), b ≡ 0 (mod m)	m (every residue)	0x ≡ 0 (mod 5): every x works

Classification of solution scenarios for ax ≡ b (mod m)

SECTION 6

Worked Example

Let us solve the congruence 12x ≡ 18 (mod 30) step by step, demonstrating every stage of the algorithm including the Extended Euclidean computation.

Solve 12x ≡ 18 (mod 30)

1
Step 1 — Compute gcd(a, m)

Apply the Euclidean Algorithm to a = 12 and m = 30. We have 30 = 2 × 12 + 6, then 12 = 2 × 6 + 0. Therefore gcd(12, 30) = 6.

d = gcd(12, 30) = 6
2
Step 2 — Check existence condition

We need d | b, i.e., 6 | 18. Since 18 = 3 × 6, the condition is satisfied. A solution exists, and there will be exactly d = 6 incongruent solutions modulo 30.

6 | 18 ✓ — solutions exist
3
Step 3 — Reduce to coprime case

Divide every coefficient by d = 6: a/d = 12/6 = 2, b/d = 18/6 = 3, m/d = 30/6 = 5. The reduced congruence is 2x ≡ 3 (mod 5). Note that gcd(2, 5) = 1, confirming the coprime condition.

Reduced: 2x ≡ 3 (mod 5)
4
Step 4 — Find modular inverse of a/d mod m/d

We need 2⁻¹ mod 5. Apply the Extended Euclidean Algorithm: 5 = 2 × 2 + 1, so 1 = 5 − 2 × 2, giving s = −2. Reducing modulo 5: −2 ≡ 3 (mod 5). Verify: 2 × 3 = 6 ≡ 1 (mod 5). ✓

2⁻¹ ≡ 3 (mod 5)
5
Step 5 — Compute base solution

Multiply both sides of 2x ≡ 3 (mod 5) by 2⁻¹ = 3: x ≡ 3 × 3 (mod 5) = 9 ≡ 4 (mod 5). The base solution is x₀ = 4.

x₀ ≡ 4 (mod 5)
6
Step 6 — Enumerate all solutions modulo m

The d = 6 solutions modulo 30 are x ≡ x₀ + k(m/d) (mod m) = 4 + 5k (mod 30) for k = 0, 1, 2, 3, 4, 5. Computing: x ∈ {4, 9, 14, 19, 24, 29}. Each can be verified: 12 × 4 = 48 ≡ 18 (mod 30) ✓, 12 × 9 = 108 ≡ 18 (mod 30) ✓, and so on.

x ≡ 4, 9, 14, 19, 24, 29 (mod 30)

💡

Verification Tip

Always verify at least two solutions by direct substitution. For instance, 12 × 24 = 288 = 9 × 30 + 18, so 288 mod 30 = 18. ✓ This catches arithmetic errors in the Extended Euclidean computation, which is the most error-prone step.

SECTION 7

Solution Methods Compared

While the Extended Euclidean Algorithm is the general-purpose tool for solving linear congruences, several alternative approaches exist. Each has its own strengths and appropriate contexts. The following comparison helps you choose the right method for a given situation.

Method	Strengths	Limitations
Brute-force search	Trivial to implement; no theory needed; guarantees finding all solutions for small moduli	O(m) time complexity; completely impractical for large m (e.g., cryptographic sizes ~ 10³⁰⁰)
Extended Euclidean Algorithm	O(log m) time; handles all cases including d > 1; directly produces Bézout coefficients	Multi-step bookkeeping; negative intermediate values require careful sign handling
Euler's theorem ( $a^{φ(m)−1}$ )	Elegant theoretical connection; useful when φ(m) is easily computed (e.g., m prime)	Requires gcd(a,m) = 1; computing φ(m) for large composite m requires factorization
Inspection / mental arithmetic	Fastest for small moduli (m ≤ 20); builds number sense and intuition	Not systematic; error-prone; does not scale

Comparison of methods for solving ax ≡ b (mod m)

⚡

PRACTICAL ADVICE

For homework and exam problems with small moduli (m < 50), inspection or a quick Euclidean computation suffices. For programming tasks—especially in cryptography where moduli are hundreds of digits long—the Extended Euclidean Algorithm is the standard. Languages like Python provide built-in support via pow(a, -1, m) (Python 3.8+), which internally uses exactly this algorithm.

SECTION 8

Connections to Advanced Topics

Linear congruences are the simplest equations in modular arithmetic, but they serve as the launching pad for a rich landscape of more advanced results. The table below maps how each idea generalizes, illustrating that mastering the introductory case provides essential scaffolding for the rest of number theory and its applications.

Introductory Concept	Advanced Generalization	Application Domain
Single linear congruence ax ≡ b (mod m)	Systems of simultaneous congruences → Chinese Remainder Theorem	Fault-tolerant computing, secret sharing
Modular inverse a⁻¹ mod m	Multiplicative group (ℤ/mℤ)* and Euler's theorem	RSA key generation, Diffie-Hellman
Extended Euclidean Algorithm	Continued fractions, lattice basis reduction	Cryptanalysis, integer programming
Linear congruence in one variable	Polynomial congruences and Hensel's lemma	p-adic analysis, algebraic number theory
Existence via gcd condition	Solvability in rings, ideal theory	Abstract algebra, algebraic geometry

From introductory linear congruences to advanced mathematics

Perhaps the most immediate next step is the Chinese Remainder Theorem (CRT), which addresses systems of linear congruences with pairwise coprime moduli. Given the system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ aₖ (mod mₖ), the CRT guarantees a unique solution modulo m₁m₂···mₖ. Each individual congruence in the CRT construction is solved using exactly the techniques covered in this lesson. Beyond the CRT, polynomial congruences like x² ≡ a (mod p) (quadratic residues) and higher-degree congruences build on the linear case through iterative lifting procedures such as Hensel's lemma.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why the congruence 6x ≡ 5 (mod 9) has no solution, even though both 6 and 5 are less than 9. What specific criterion fails, and what is the underlying reason in terms of the residue classes that multiples of 6 can reach modulo 9?

Show answer

We compute gcd(6, 9) = 3. The existence theorem requires gcd(a, m) | b, but 3 does not divide 5. The underlying reason is that multiples of 6 modulo 9 cycle through {0, 6, 3, 0, 6, 3, …} = {0, 3, 6}, which are precisely the multiples of d = 3 within ℤ₉. Since 5 is not a multiple of 3, the residue class 5 is unreachable. No matter how many times you step by 6 around a circle of 9 positions, you only land on every third position, and 5 is not among them.

Question 2: BASIC CALCULATION

Solve the congruence 7x ≡ 3 (mod 11).

Show answer

Since gcd(7, 11) = 1, the solution is unique modulo 11. We need 7⁻¹ mod 11. Using the Extended Euclidean Algorithm: 11 = 1 × 7 + 4; 7 = 1 × 4 + 3; 4 = 1 × 3 + 1; 3 = 3 × 1. Back-substituting: 1 = 4 − 1 × 3 = 4 − 1 × (7 − 4) = 2 × 4 − 7 = 2(11 − 7) − 7 = 2 × 11 − 3 × 7. So 7⁻¹ ≡ −3 ≡ 8 (mod 11). Verify: 7 × 8 = 56 = 5 × 11 + 1 ≡ 1 ✓. Therefore x ≡ 8 × 3 = 24 ≡ 2 (mod 11). Check: 7 × 2 = 14 ≡ 3 (mod 11) ✓.

Question 3: INTERMEDIATE

Find all solutions to 15x ≡ 9 (mod 24).

Show answer

Compute d = gcd(15, 24) = 3. Since 3 | 9, solutions exist, and there are d = 3 incongruent solutions mod 24. Divide through by 3: 5x ≡ 3 (mod 8). Now gcd(5, 8) = 1. Find 5⁻¹ mod 8: try 5 × 5 = 25 ≡ 1 (mod 8), so 5⁻¹ ≡ 5 (mod 8). Thus x₀ ≡ 5 × 3 = 15 ≡ 7 (mod 8). The three solutions mod 24 are x ≡ 7 + 8k (mod 24) for k = 0, 1, 2, giving x ∈ {7, 15, 23}. Verification: 15 × 7 = 105 = 4 × 24 + 9 ≡ 9 ✓; 15 × 15 = 225 = 9 × 24 + 9 ≡ 9 ✓; 15 × 23 = 345 = 14 × 24 + 9 ≡ 9 ✓.

Question 4: APPLIED

In a simplified RSA scheme, the public key is (e, n) = (17, 60) and you need to compute the private key d such that ed ≡ 1 (mod φ(n)), where φ(60) = 16. Find d by solving 17d ≡ 1 (mod 16).

Show answer

We need 17⁻¹ mod 16. Since 17 ≡ 1 (mod 16), we have 17 × 1 ≡ 1 × 1 ≡ 1 (mod 16). Therefore d = 1. However, this is a degenerate case illustrating the importance of parameter choice in cryptography—when e ≡ 1 (mod φ(n)), the encryption and decryption exponents are effectively the same, providing no security. In practice, we would choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. With e = 7 instead, we would solve 7d ≡ 1 (mod 16): using the Extended Euclidean Algorithm, 16 = 2 × 7 + 2, 7 = 3 × 2 + 1, so 1 = 7 − 3 × 2 = 7 − 3(16 − 2 × 7) = 7 × 7 − 3 × 16, giving d ≡ 7 (mod 16). Verify: 7 × 7 = 49 = 3 × 16 + 1 ≡ 1 ✓.

Question 5: CRITICAL THINKING

Prove that if p is prime and a is not divisible by p, then ax ≡ b (mod p) always has exactly one solution modulo p. Furthermore, explain how this connects to the fact that ℤ/pℤ is a field.

Show answer

Since p is prime and p ∤ a, the only positive divisors of p are 1 and p itself, and since a is not a multiple of p, we have gcd(a, p) = 1. By the existence theorem, ax ≡ b (mod p) has a solution, and since d = 1, there is exactly d = 1 incongruent solution modulo p. This means every nonzero element of ℤ/pℤ has a multiplicative inverse, which is precisely the algebraic condition that distinguishes a field from a mere commutative ring. In ℤ/pℤ, the equation ax = b can always be solved as x = a⁻¹b, mirroring the division operation in ℚ or ℝ. When m is composite, ℤ/mℤ contains zero divisors (elements a with gcd(a, m) > 1) that lack inverses, so ℤ/mℤ is only a ring, not a field. The solvability criterion gcd(a, m) | b can thus be reinterpreted algebraically: it asks whether b lies in the ideal generated by the image of a in ℤ/mℤ.

SUMMARY

Summary & Review

Summary

A linear congruence ax ≡ b (mod m) asks for integers x whose product with a leaves remainder b upon division by m. The existence theorem states that solutions exist if and only if d = gcd(a, m) divides b, and when they do, there are exactly d incongruent solutions modulo m. The solution procedure involves dividing through by d to obtain a coprime reduced congruence, finding the modular inverse of a/d modulo m/d via the Extended Euclidean Algorithm, and then generating all solutions by adding multiples of m/d.

This technique is the entry point to a vast array of applications: from the Chinese Remainder Theorem for systems of congruences, to RSA cryptography where computing modular inverses is the central operation in key generation. Mastering the interplay between divisibility, residue classes, and modular arithmetic provides essential algebraic fluency for all subsequent work in number theory and discrete mathematics.