The Greatest Common Divisor

The gcd is the load-bearing gear of elementary number theory: it is the precise tool that reduces fractions to lowest terms ($\tfrac{a}{b} = \tfrac{a/d}{b/d}$ with $d=\gcd(a,b)$), and it is the exact solvability criterion for the linear Diophantine equation $ax+by=c$ (solvable in integers iff $\gcd(a,b) \mid c$, a direct consequence of Bezout's identity above). In modular arithmetic, $\gcd(a,n)=1$ is precisely the condition for $a$ to be invertible modulo $n$, which is the backbone of the RSA cryptosystem: key generation requires choosing an encryption exponent $e$ coprime to $\varphi(n)$, and decryption relies on computing its modular inverse via the extended Euclidean algorithm. In computer science, the gcd computation is a textbook example of an algorithm with provably efficient (logarithmic) running time, underlying implementations in every major arithmetic library. In algebra, the notion generalizes to principal ideal domains, where gcd is defined via ideal containment exactly mirroring the universal property given here; this generalization is essential in ring theory and algebraic number theory. In combinatorics and dynamical systems, $\gcd$ of periods governs the structure of orbits and lattice points, e.g. determining when a line through the origin with rational slope $p/q$ (in lowest terms) first returns to a lattice point.

Ask the tutor: How does the Euclidean Algorithm turn the reduction property $\gcd(a,b)=\gcd(a,b-qa)$ into a concrete finite procedure, and how do we extract the Bezout coefficients $x_0,y_0$ from it?

Think of divisibility as an ordering on the positive integers: $m \preceq n$ means $m \mid n$. Under this order, not every pair of numbers is comparable — $4$ and $6$ neither divide each other — but every pair still has a well-defined meet, a greatest lower bound in the divisibility order. That meet is exactly $\gcd(4,6) = 2$. The gcd is the divisibility-lattice analogue of "the larger of two numbers" under the usual order $\leq$. A second, equally important picture: fix $a$ and $b$, and look at the set of all integer combinations

This set is closed under addition and under multiplication by any integer, and it contains both $a$ and $b$ (take $(x,y) = (1,0)$ or $(0,1)$). It turns out $I$ consists precisely of all multiples of a single positive integer — and that integer is $\gcd(a,b)$. This is the seed of Bezout's Identity, which asserts $\gcd(a,b) = ax_0 + by_0$ for suitable integers $x_0, y_0$; we prove the existence half of this fact below as part of establishing gcd's universal property.

(This is exactly $d = ax_0+by_0$ established in Step 2–4 of the proof above; the full computational machinery for finding $x_0,y_0$ is the subject of <a class="wiki-link" href="/wiki/math-numthy-bezout-identity" data-track="wiki_article.body.wiki_link">Bezout&#39;s Identity</a> proper, via the extended <span class="wiki-link-missing">Euclidean Algorithm</span>.)

Example 1: Computing $\gcd(1035, 621)$ via the reduction lemma, and verifying the universal property directly. We use Lemma property (3) repeatedly (this is precisely the mechanism behind the Euclidean Algorithm, though we verify it by hand here rather than invoking that theorem):

So $\gcd(1035,621) = 207$. Direct check via the definition. Factor: $1035 = 3^2\cdot5\cdot23$, and $621 = 3^3\cdot 23$. Common divisors must be products of shared prime powers: $\min(2,3)=2$ copies of $3$ and $\min(1,1)=1$ copy of $23$ (the prime $5$ does not divide $621$). So the largest common divisor is $3^2 \cdot 23 = 9 \cdot 23 = 207$, matching the reduction computation. We can also verify the universal property directly: divisors of $207 = 9\cdot 23$ are $1,3,9,23,69,207$; one checks each of these does divide both $1035$ and $621$ (e.g. $69 \mid 1035$ since $1035/69=15$, and $69\mid 621$ since $621/69=9$), while any other common divisor of $1035,621$ — say from the factorizations above, the only common divisors are exactly $\{1,3,9,23,69,207\}$ since these are the only products $3^i23^j$ with $i\le2,j\le1$ — so indeed the maximum $207$ is divisible by all smaller common divisors, consistent with the Theorem.

Example 2: Finding an explicit Bezout pair for $\gcd(101, 78)$ and applying coprime cancellation. First compute the gcd:

So $\gcd(101,78)=1$: they are coprime. Back-substituting (this is the extended algorithm, previewed here):

Check: $17\cdot101 = 1717$, $22\cdot78=1716$, and $1717-1716=1$. So

confirming $\gcd(101,78)=1$ via Lemma property (5), with explicit $x_0=17, y_0=-22$. Now apply the coprime cancellation property (6): suppose we are told $101 \mid 78c$ for some integer $c$. Since $\gcd(101,78)=1$, property (6) with $a=101, b=78$ gives $101 \mid c$. Concretely, take $c = 101k$ for any integer $k$; then $78c = 78\cdot101k$, and indeed $101 \mid 78c$ while also $101\mid c$, consistent with (and not contradicting) the claim — the content of (6) is that no other $c$ can satisfy $101\mid 78c$, which one can also verify from the Bezout identity directly: multiplying $17\cdot101 - 22\cdot78 = 1$ by $c$ gives $17\cdot101c - 22\cdot 78c = c$, and since $101$ divides both terms on the left (the first obviously, the second because $101\mid 78c$ by hypothesis), $101 \mid c$.