Linear Congruences

When can we solve 7x≡3(mod15)7x \equiv 3 \pmod{15}? How many answers are there? This simple question — solving a linear equation modulo an integer — turns out to encode the entire arithmetic structure of Z/nZ\mathbb{Z}/n\mathbb{Z}. Over the rational numbers, solving ax=bax = b is straightforward. A nonzero aa always yields the unique solution x=b/ax = b/a. Working modulo nn is different. It introduces genuinely new phenomena. An equation may have no solutions at all. It may have exactly one solution. Or it may have many solutions. The outcome depends on how aa interacts with nn. The idea matters because linear congruences are the atomic building block of modular arithmetic. Every question about solving polynomial congruences reduces to this equation. So does finding modular inverses. So does combining several congruences with different moduli, as in the Chinese Remainder Theorem. All of these reduce, at some stage, to understanding exactly this equation. Cryptographic algorithms such as RSA rest on this understanding. So do error-correcting codes and the extended Euclidean algorithm. All require a precise grasp of when ax≡b(modn)ax \equiv b \pmod n is solvable. They also require knowing what its solution set looks like. The big picture is that solvability and solution-counting are governed entirely by the greatest common divisor gcd⁡(a,n)\gcd(a,n). This single invariant determines everything. It determines whether a solution exists. If so, it determines exactly how many incongruent solutions there are modulo nn. The mechanism behind this is Bezout's Identity. It converts the divisibility condition into an explicit algorithm. That algorithm is the extended Euclidean algorithm, used for producing solutions. This article gives the complete solvability criterion for ax≡b(modn)ax \equiv b \pmod n. It describes the full solution set when solutions exist. It proves both directions rigorously. We work through two asymmetric numerical examples. We examine a counterexample showing why the gcd condition cannot be dropped. We close by connecting linear congruences to the machinery of simultaneous congruences. This machinery culminates in the Chinese Remainder Theorem.

Key takeaways
  • The congruence ax≡b(modn)ax \equiv b \pmod n is solvable in xx if and only if gcd⁡(a,n)∣b\gcd(a,n) \mid b.
  • When solvable, the solutions form exactly d=gcd⁡(a,n)d = \gcd(a,n) distinct residue classes modulo nn.
  • These dd solutions are evenly spaced: consecutive solutions differ by n/dn/d.
  • When gcd⁡(a,n)=1\gcd(a,n)=1, there is a unique solution modulo nn, given by x≡a−1b(modn)x \equiv a^{-1}b \pmod n.
  • The extended Euclidean algorithm both certifies solvability and constructs an explicit solution.
  • Key idea: solving ax≡b(modn)ax\equiv b\pmod n is really solving the linear Diophantine equation ax−ny=bax - ny = b, so gcd divisibility is the whole story.

Where this lives today

Linear congruences are the computational engine behind the extended Euclidean algorithm's most common application: computing modular inverses, which underlies the RSA cryptosystem's key generation and decryption steps. In coding theory, solving linear congruences over Z/nZ\mathbb{Z}/n\mathbb{Z} appears in constructing check digits (such as ISBN and UPC codes) and in decoding certain linear codes. In computer science, hashing schemes and pseudorandom number generators (linear congruential generators) are literally defined by iterating xk+1≡axk+c(modn)x_{k+1} \equiv ax_k + c \pmod n, and understanding their period and coverage properties requires exactly the solvability theory developed here. In pure mathematics, the step from a single linear congruence to systems of congruences with different, possibly non-coprime moduli is precisely the subject of the Chinese Remainder Theorem, which decomposes Z/nZ\mathbb{Z}/n\mathbb{Z} into a product of simpler rings and reduces simultaneous solvability to compatibility conditions built from exactly the gcd criterion proved above.

Ask the tutor: How does the solvability criterion here extend to solving systems of linear congruences with different moduli, as in the Chinese Remainder Theorem?

DefinitionLinear congruence and its solutions

Let a,b,na, b, n be integers with n≥1n \geq 1. A linear congruence is an equation of the form

ax≡b(modn),ax \equiv b \pmod{n},

where xx ranges over the integers. An integer x0x_0 is a solution if n∣(ax0−b)n \mid (ax_0 - b). Two solutions x0,x1x_0, x_1 are considered the same solution if x0≡x1(modn)x_0 \equiv x_1 \pmod n, since replacing a solution by any integer congruent to it modulo nn yields another solution (this is immediate from the definition of congruence: if x0≡x1(modn)x_0 \equiv x_1 \pmod n then ax0≡ax1(modn)a x_0 \equiv a x_1 \pmod n). Accordingly, we count solutions as residue classes modulo nn, i.e. elements of Z/nZ\mathbb{Z}/n\mathbb{Z}, rather than as individual integers. The congruence is called solvable if at least one such residue class exists.

Intuition

Think of Z/nZ\mathbb{Z}/n\mathbb{Z} as nn equally spaced points arranged around a circle, labeled 0,1,…,n−10, 1, \dots, n-1. Multiplication by aa is a map from this circle to itself: it sends each point xx to the point ax  nax \bmod n. Solving ax≡b(modn)ax \equiv b \pmod n asks: which points xx get sent to bb by this map? If gcd⁡(a,n)=1\gcd(a,n) = 1, multiplication by aa is a bijection of the circle onto itself (it merely permutes the nn points), so every target bb is hit exactly once — a unique solution. If d=gcd⁡(a,n)>1d = \gcd(a,n) > 1, the map is no longer a bijection: it is dd-to-one onto its image, and its image consists only of the multiples of dd modulo nn. So bb is hit only if d∣bd \mid b, and when it is hit, it is hit exactly dd times — giving dd solutions, evenly spaced n/dn/d apart around the circle. This "evenly spaced" structure is not a coincidence; it comes from rewriting the congruence as a genuine linear equation ax−ny=bax - ny = b over the integers and invoking Bezout's identity, which certifies that d=gcd⁡(a,n)d=\gcd(a,n) is exactly the set of integer combinations of aa and nn.

Figure
The map x↦7x mod 15x \mapsto 7x \bmod 15: a bijection since gcd⁡(7,15)=1\gcd(7,15)=1
Domain: x mod 15 Codomain: 7x mod 15 0 1 2 3 4 5 6 7 8 9 10 11 3 → x=12 0 7 14 6 13 5 12 4 11 3 10 2 x = 9 is the unique solution of 7x ≡ 3 (mod 15)
TheoremSolvability criterion and solution set for linear congruences

Let a,b,na, b, n be integers with n≥1n \geq 1, and let d=gcd⁡(a,n)d = \gcd(a,n). Then: 1. The congruence ax≡b(modn)ax \equiv b \pmod n has a solution if and only if d∣bd \mid b. 2. If d∣bd \mid b, then the congruence has exactly dd incongruent solutions modulo nn. If x0x_0 is any one solution, the complete list of incongruent solutions is

x0, x0+nd, x0+2⋅nd, …, x0+(d−1)⋅nd(modn).x_0,\ x_0 + \frac{n}{d},\ x_0 + 2\cdot\frac{n}{d},\ \dots,\ x_0 + (d-1)\cdot\frac{n}{d} \pmod n.

3. In particular, if gcd⁡(a,n)=1\gcd(a,n) = 1, the congruence has a unique solution modulo nn, namely

x≡a−1b(modn),x \equiv a^{-1} b \pmod n,

where a−1a^{-1} is a modular inverse of aa modulo nn.

Proof

We prove each part in turn. Throughout, d=gcd⁡(a,n)d = \gcd(a,n).

Part 1: solvability   ⟺  d∣b\iff d \mid b. (⇒\Rightarrow) Suppose x0x_0 is a solution, so n∣(ax0−b)n \mid (ax_0 - b). Then there is an integer kk with

ax0−b=nk,i.e.b=ax0−nk.ax_0 - b = nk, \quad\text{i.e.}\quad b = ax_0 - nk.

Since d∣ad \mid a and d∣nd \mid n, we get d∣(ax0−nk)=bd \mid (ax_0 - nk) = b. This proves the forward direction. (⇐\Leftarrow) Suppose d∣bd \mid b. By Bezout's Identity, since d=gcd⁡(a,n)d = \gcd(a,n), there exist integers u,vu, v such that

au+nv=d.au + nv = d.

Write b=dmb = d m for some integer mm (using d∣bd \mid b). Multiplying the Bezout identity by mm gives

a(um)+n(vm)=dm=b,a(um) + n(vm) = dm = b,

so setting x0=umx_0 = um we get ax0−b=−n(vm)a x_0 - b = -n(vm), i.e. n∣(ax0−b)n \mid (a x_0 - b). Hence x0=umx_0 = um is a solution. This proves solvability, completing Part 1.

Part 2: the solution set, given solvability. Assume now d∣bd \mid b, and let x0x_0 be a solution obtained as above (or any solution — the argument below applies to any single fixed solution). Step A (every listed value is a solution). We claim that for every integer jj,

x0+j⋅ndx_0 + j\cdot \frac{n}{d}

is again a solution. Indeed,

a(x0+jnd)−b=(ax0−b)+ad jn.a\left(x_0 + j\frac{n}{d}\right) - b = (ax_0 - b) + \frac{a}{d}\, jn.

Since x0x_0 is a solution, n∣(ax0−b)n \mid (ax_0-b); and the second term adjn\frac{a}{d}jn is manifestly a multiple of nn because a/da/d is an integer (as d∣ad \mid a). Hence the whole right-hand side is a multiple of nn, so x0+jn/dx_0 + j n/d is a solution for every integer jj. Step B (every solution has this form). Conversely, let x1x_1 be any solution. Then both ax0≡b(modn)ax_0 \equiv b \pmod n and ax1≡b(modn)ax_1 \equiv b\pmod n, so subtracting,

a(x1−x0)≡0(modn),i.e.n∣a(x1−x0).a(x_1 - x_0) \equiv 0 \pmod n, \quad\text{i.e.}\quad n \mid a(x_1-x_0).

Write a=da′a = d a', n=dn′n = d n' with gcd⁡(a′,n′)=1\gcd(a', n') = 1 (this is possible and gcd⁡(a′,n′)=1\gcd(a',n')=1 is a standard property of dividing through by the gcd: if a common factor e>1e>1 divided both a′a' and n′n', then dede would divide both aa and nn and exceed d=gcd⁡(a,n)d = \gcd(a,n), a contradiction). The divisibility n∣a(x1−x0)n \mid a(x_1-x_0) becomes

dn′∣da′(x1−x0)⟹n′∣a′(x1−x0)d n' \mid d a' (x_1 - x_0) \quad\Longrightarrow\quad n' \mid a'(x_1-x_0)

(cancelling the common factor dd, valid since d≠0d \neq 0). Since gcd⁡(a′,n′)=1\gcd(a',n')=1, Euclid's lemma (a direct consequence of Bezout's identity: if n′∣a′cn' \mid a'c and gcd⁡(a′,n′)=1\gcd(a',n')=1, write a′u+n′v=1a'u+n'v=1, multiply by cc to get a′uc+n′vc=ca'uc + n'vc = c, and note n′n' divides both terms on the left) gives

n′∣(x1−x0).n' \mid (x_1 - x_0).

Thus x1−x0=jn′=j⋅ndx_1 - x_0 = j n'= j\cdot \dfrac{n}{d} for some integer jj, i.e. x1≡x0+jnd(modn)x_1 \equiv x_0 + j\dfrac{n}{d}\pmod n. This proves every solution is congruent to one of the form in Step A. Step C (exactly dd incongruent classes). By Steps A and B, the full solution set modulo nn is exactly

{ x0+j⋅nd  n:j∈Z }.\left\{\, x_0 + j\cdot\frac{n}{d} \bmod n : j \in \mathbb{Z} \,\right\}.

It remains to show this set has exactly dd distinct residues modulo nn, achieved by j=0,1,…,d−1j = 0, 1, \dots, d-1. First, these dd values are pairwise incongruent modulo nn: if x0+j1n/d≡x0+j2n/d(modn)x_0 + j_1 n/d \equiv x_0 + j_2 n/d \pmod n with 0≤j1,j2≤d−10 \le j_1, j_2 \le d-1, then n∣(j1−j2)(n/d)n \mid (j_1 - j_2)(n/d), so dividing by n/dn/d (a positive integer since n/d≥1n/d \ge 1), we get d∣(j1−j2)d \mid (j_1-j_2); but ∣j1−j2∣<d|j_1 - j_2| < d, forcing j1=j2j_1 = j_2. Second, every value x0+jn/dx_0 + jn/d for arbitrary integer jj is congruent modulo nn to one with j∈{0,…,d−1}j \in \{0,\dots,d-1\}: write j=qd+rj = qd + r with 0≤r≤d−10 \le r \le d-1 (division algorithm), then

x0+jnd=x0+rnd+qn≡x0+rnd(modn).x_0 + j\frac{n}{d} = x_0 + r\frac{n}{d} + qn \equiv x_0 + r\frac{n}{d} \pmod n.

Hence the solution set modulo nn is precisely {x0,x0+n/d,…,x0+(d−1)n/d}\{x_0, x_0 + n/d, \dots, x_0+(d-1)n/d\}, a set of exactly dd distinct residues. This proves Part 2.

Part 3: the coprime case. If gcd⁡(a,n)=1\gcd(a,n) = 1, then d=1d = 1 and Part 2 gives a unique solution modulo nn. By definition of Modular Inverses, since gcd⁡(a,n)=1\gcd(a,n)=1, Bezout's identity provides u,vu,v with au+nv=1au + nv = 1, so au≡1(modn)au \equiv 1 \pmod n; thus uu is a modular inverse a−1a^{-1} of aa. Multiplying ax≡b(modn)ax \equiv b \pmod n by a−1a^{-1} gives x≡a−1(ax)≡a−1b(modn)x \equiv a^{-1}(ax) \equiv a^{-1}b \pmod n as a necessary condition on any solution, and substituting x=a−1bx = a^{-1}b back in verifies a(a−1b)=(aa−1)b≡1⋅b=b(modn)a(a^{-1}b) = (aa^{-1})b \equiv 1\cdot b = b \pmod n, confirming it is indeed a solution. Combined with uniqueness from Part 2, this establishes Part 3. ■\blacksquare

∎

Worked examples

Example 1: a coprime case forcing a genuine computation. Solve 23x≡11(mod60)23x \equiv 11 \pmod{60}. Step 1 — check solvability. Compute gcd⁡(23,60)\gcd(23,60) via the Euclidean algorithm:

60=2⋅23+14,23=1⋅14+9,14=1⋅9+5,9=1⋅5+4,5=1⋅4+1,4=4⋅1+0.60 = 2\cdot 23 + 14,\quad 23 = 1\cdot 14 + 9,\quad 14 = 1\cdot 9 + 5,\quad 9 = 1\cdot 5 + 4,\quad 5 = 1\cdot 4+1,\quad 4 = 4\cdot 1 + 0.

So gcd⁡(23,60)=1\gcd(23,60) = 1. Since 1∣111 \mid 11, the congruence is solvable, and by Part 3 of the theorem there is a unique solution modulo 6060. Step 2 — back-substitute to find the inverse of 2323 mod 6060. Reversing the Euclidean algorithm:

1=5−1⋅41 = 5 - 1\cdot 4
=5−1⋅(9−1⋅5)=2⋅5−1⋅9= 5 - 1\cdot(9 - 1\cdot 5) = 2\cdot 5 - 1\cdot 9
=2⋅(14−1⋅9)−1⋅9=2⋅14−3⋅9= 2\cdot(14 - 1\cdot 9) - 1\cdot 9 = 2\cdot 14 - 3\cdot 9
=2⋅14−3⋅(23−1⋅14)=5⋅14−3⋅23= 2\cdot 14 - 3\cdot(23 - 1\cdot 14) = 5\cdot 14 - 3\cdot 23
=5⋅(60−2⋅23)−3⋅23=5⋅60−13⋅23.= 5\cdot(60 - 2\cdot 23) - 3\cdot 23 = 5\cdot 60 - 13\cdot 23.

So −13⋅23+5⋅60=1-13 \cdot 23 + 5\cdot 60 = 1, giving 23⋅(−13)≡1(mod60)23\cdot(-13) \equiv 1 \pmod{60}. Reducing −13  60-13 \bmod 60 gives 4747; check: 23⋅47=1081=18⋅60+123\cdot 47 = 1081 = 18\cdot 60 + 1. Indeed 1081=1080+11081 = 1080+1. So 23−1≡47(mod60)23^{-1} \equiv 47 \pmod{60}. Step 3 — solve. By Part 3,

x≡47⋅11≡517(mod60).x \equiv 47 \cdot 11 \equiv 517 \pmod{60}.

Since 517=8⋅60+37517 = 8\cdot 60 + 37, we get x≡37(mod60)x \equiv 37 \pmod{60}. Verification. 23⋅37=851=14⋅60+1123 \cdot 37 = 851 = 14\cdot 60 + 11, and indeed 840+11=851840 + 11 = 851. So 23⋅37≡11(mod60)23\cdot 37 \equiv 11 \pmod{60} ✓, and this is the unique solution class modulo 6060.

Example 2: a non-coprime case with d>1d > 1, illustrating the full solution set. Solve 42x≡18(mod54)42x \equiv 18 \pmod{54}. Step 1 — check solvability. Compute d=gcd⁡(42,54)d = \gcd(42,54):

54=1⋅42+12,42=3⋅12+6,12=2⋅6+0.54 = 1\cdot 42 + 12,\quad 42 = 3\cdot 12 + 6,\quad 12 = 2\cdot 6 + 0.

So d=6d = 6. Since 6∣186 \mid 18 (indeed 18=3⋅618 = 3\cdot 6), the congruence is solvable, and by Part 2 there are exactly d=6d = 6 incongruent solutions modulo 5454. Step 2 — find one solution via Bezout. Back-substitute:

6=42−3⋅12=42−3(54−42)=4⋅42−3⋅54.6 = 42 - 3\cdot 12 = 42 - 3(54 - 42) = 4\cdot 42 - 3\cdot 54.

So 42⋅4+54⋅(−3)=642\cdot 4 + 54\cdot(-3) = 6. Since b=18=3⋅6b = 18 = 3\cdot 6, multiply through by m=3m=3:

42⋅12+54⋅(−9)=18.42\cdot 12 + 54\cdot(-9) = 18.

So x0=12x_0 = 12 satisfies 42⋅12≡18(mod54)42\cdot 12 \equiv 18 \pmod{54}. Check: 42⋅12=504=9⋅54+1842\cdot 12 = 504 = 9\cdot 54 + 18, since 486+18=504486+18=504. Confirmed. Step 3 — list all six solutions. By Part 2 the solutions are x0+j⋅(n/d)x_0 + j\cdot(n/d) for j=0,…,5j=0,\dots,5, where n/d=54/6=9n/d = 54/6 = 9:

12, 21, 30, 39, 48, 57≡3(mod54).12,\ 21,\ 30,\ 39,\ 48,\ 57\equiv 3 \pmod{54}.

So reducing mod 54, the complete solution set is

x≡3, 12, 21, 30, 39, 48(mod54).x \equiv 3,\ 12,\ 21,\ 30,\ 39,\ 48 \pmod{54}.

Verification of a couple of these: for x=3x=3: 42⋅3=126=2⋅54+1842\cdot 3 = 126 = 2\cdot 54+18 ✓ (since 108+18=126108+18=126). For x=48x = 48: 42⋅48=201642\cdot 48 = 2016, and 2016=37⋅54+182016 = 37\cdot 54 + 18, since 37⋅54=199837\cdot 54 = 1998 and 1998+18=20161998+18=2016 ✓. Both check out, and one verifies similarly for x=12,21,30,39x=12,21,30,39. Notice the six solutions are exactly the residues 3,12,21,…3, 12, 21, \dots spaced 99 apart, matching n/d=9n/d = 9 from the theorem.

CounterexampleWhy the hypothesis "d∣bd \mid b" cannot be dropped

The theorem's Part 1 requires checking d=gcd⁡(a,n)d = \gcd(a,n) divides bb; without this hypothesis the congruence can be flatly unsolvable, even though a,b,na,b,n look otherwise unremarkable. Consider 6x≡4(mod9)6x \equiv 4 \pmod{9}. Here gcd⁡(6,9)=3\gcd(6,9) = 3, and 3∤43 \nmid 4. The theorem predicts no solution. Let's confirm directly by brute force, checking all nine residues x=0,1,…,8x = 0,1,\dots,8:

6⋅0=0, 6⋅1=6, 6⋅2=12≡3, 6⋅3=18≡0, 6⋅4=24≡6,6\cdot 0=0,\ 6\cdot1=6,\ 6\cdot2=12\equiv3,\ 6\cdot3=18\equiv0,\ 6\cdot4=24\equiv6,
6⋅5=30≡3, 6⋅6=36≡0, 6⋅7=42≡6, 6⋅8=48≡3(mod9).6\cdot5=30\equiv3,\ 6\cdot6=36\equiv0,\ 6\cdot7=42\equiv6,\ 6\cdot8=48\equiv3 \pmod 9.

The only values ever achieved by 6x  96x \bmod 9 are {0,3,6}\{0,3,6\} — precisely the multiples of d=3d=3 modulo 99 — and 44 is never among them. So indeed 6x≡4(mod9)6x\equiv 4\pmod 9 has no solution. This shows exactly what goes wrong if one attempts to apply the "unique solution via inverse" shortcut (Part 3) without first verifying gcd⁡(a,n)=1\gcd(a,n)=1 or, more generally, without checking d∣bd\mid b: 66 has no inverse modulo 99 at all (since gcd⁡(6,9)=3≠1\gcd(6,9)=3\ne1), so the formula x≡a−1bx\equiv a^{-1}b is not even meaningful here, and one cannot bypass the divisibility check. The hypothesis d∣bd\mid b is therefore not a technical nicety — it is the exact dividing line between solvable and unsolvable instances.

Scope, edge cases & common traps

SituationWhat happens
gcd⁡(a,n)=1\gcd(a,n)=1Unique solution mod nn; use modular inverse
gcd⁡(a,n)=d>1\gcd(a,n)=d>1, d∣bd\mid bExactly dd solutions mod nn, spaced n/dn/d apart
gcd⁡(a,n)=d>1\gcd(a,n)=d>1, d∤bd\nmid bNo solution at all
a≡0(modn)a \equiv 0\pmod n, b≢0b\not\equiv 0Special case of above with d=nd=n: unsolvable unless n∣bn\mid b
n=1n=1Every integer is a solution (only one residue class mod 11)

The mathematician behind it

Origins · 1 minCarl Friedrich Gauss and how this was discovered
CF
Carl Friedrich Gauss
1777–1855 · Göttingen, Germany

Gauss systematized the theory of congruences in his 1801 treatise Disquisitiones Arithmeticae, introducing the notation a≡b(modn)a \equiv b \pmod n still used today. He treated linear congruences as the natural starting point of modular arithmetic, building toward quadratic reciprocity and the arithmetic of Gaussian integers. His arithmetic viewpoint — replacing equations over Z\mathbb{Z} with equivalence classes modulo nn — reframed number theory as the study of finite algebraic structures, laying groundwork later formalized as ring and group theory.

History
- 3rd century: Diophantus studies integer solutions to linear and polynomial equations, though not in congruence language.
- 5th–7th centuries: Chinese mathematicians (Sunzi, later Qin Jiushao) solve systems of simultaneous linear congruences, prefiguring the Chinese Remainder Theorem.
- 1621: Bachet de Méziriac publishes a systematic account of the Euclidean algorithm and integer solutions to ax+by=cax+by=c.
- 1801: Gauss's Disquisitiones Arithmeticae formalizes congruence notation and the modern theory of linear congruences.
- 19th–20th centuries: the theory becomes the foundation of finite fields, group theory, and eventually public-key cryptography.
What's the difference between "no solution" and "infinitely many solutions"?

Over the integers, ax≡b(modn)ax\equiv b\pmod n either has no integer solutions or has infinitely many integers satisfying it — but those infinitely many integers collapse into finitely many residue classes modulo nn. When we say "the congruence has dd solutions," we always mean dd distinct classes modulo nn, not dd literal integers. Any single class contains infinitely many representative integers (e.g., x=3,3+n,3+2n,…x=3, 3+n, 3+2n,\dots all count as "the same solution"). This convention matches how we treat the equation itself: since xx and x+nx+n satisfy identical congruences, they are not meaningfully different solutions.

Does the solvability criterion generalize to systems of several linear congruences?

Yes, and this is exactly the bridge to the Chinese Remainder Theorem. A system like x≡a1(modn1)x\equiv a_1 \pmod{n_1}, x≡a2(modn2)x\equiv a_2\pmod{n_2} is solvable precisely when gcd⁡(n1,n2)\gcd(n_1,n_2) divides a1−a2a_1-a_2, and the CRT gives an explicit construction and shows the solution is unique modulo lcm(n1,n2)\mathrm{lcm}(n_1,n_2) when the moduli are coprime. The single-congruence gcd criterion proved here is the base case that CRT-style arguments repeatedly invoke when combining more than two congruences.

How do I actually compute the modular inverse needed in Part 3?

Run the Euclidean algorithm on aa and nn to confirm gcd⁡(a,n)=1\gcd(a,n)=1, recording the quotients at each division step. Then back-substitute those steps in reverse order to express 11 as au+nvau+nv for some integers u,vu,v — this is the extended Euclidean algorithm. The coefficient uu, reduced modulo nn, is the desired inverse a−1a^{-1}. Example 1 above carries out this computation in full for a=23,n=60a=23, n=60, obtaining 23−1≡47(mod60)23^{-1}\equiv 47\pmod{60}.

What if aa and nn share no common factor other than trivially, but nn itself is prime?

If n=pn=p is prime and p∤ap\nmid a, then automatically gcd⁡(a,p)=1\gcd(a,p)=1 (since the only divisors of pp are 11 and pp), so Part 3 always applies: every nonzero residue aa modulo a prime pp has a unique inverse, and ax≡b(modp)ax\equiv b\pmod p always has exactly one solution whenever p∤ap\nmid a. This is why Z/pZ\mathbb{Z}/p\mathbb{Z} for prime pp forms a field — every nonzero element is invertible — whereas Z/nZ\mathbb{Z}/n\mathbb{Z} for composite nn is only a ring with zero divisors.

Can aa or bb be negative, or larger than nn?

Yes — the theorem places no restriction on the sign or size of aa and bb; only n≥1n\ge1 is required. Negative values or values exceeding nn can always be reduced modulo nn first without changing the solution set, since gcd⁡(a,n)=gcd⁡(a  n,n)\gcd(a,n)=\gcd(a\bmod n, n) and the divisibility condition d∣bd\mid b only depends on b  db\bmod d. Reducing first is a matter of computational convenience, not mathematical necessity.

What happens when a=0a=0?

If a=0a=0, the congruence becomes 0≡b(modn)0\equiv b\pmod n, i.e. n∣bn\mid b. This fits the general theorem with d=gcd⁡(0,n)=nd=\gcd(0,n)=n: the criterion "d∣bd\mid b" becomes "n∣bn\mid b" exactly as expected, and when it holds, every integer xx is a solution, consistent with Part 2 predicting d=nd=n solutions modulo nn (all nn residues work).

Is the solution formula x≡a−1bx\equiv a^{-1}b still valid if I only know some inverse of a, not the "canonical" one in [0,n)?

Yes. Any integer uu satisfying au≡1(modn)au\equiv 1\pmod n works identically in the formula, since the final answer is only claimed up to congruence modulo nn anyway. If u1u_1 and u2u_2 are both inverses of aa mod nn, they satisfy u1≡u2(modn)u_1\equiv u_2\pmod n automatically (by the uniqueness part of the theorem applied to b=1b=1), so u1b≡u2b(modn)u_1 b\equiv u_2 b\pmod n regardless of which representative you use.

Before this

Where this leads