Greatest Common Divisor
Summary: The greatest common divisor of two integers is found by the Euclidean algorithm — repeated division with remainder — which Euler proves correct via the invariance of the GCD under the operation .
Sources: chapter-1.3.7, additions-1
Last updated: 2026-05-10
Definition
The greatest common divisor of two positive integers and is the largest integer that divides both. Dividing both terms of a ratio by their GCD reduces it to lowest terms.
When , the numbers are coprime and the ratio cannot be simplified.
The Euclidean Algorithm
Divide the larger number by the smaller, then divide the previous divisor by the remainder, and so on:
Stop when a remainder is ; the last non-zero remainder is .
The sequence is strictly decreasing, so the algorithm always terminates.
Worked examples
| Inputs | Steps | GCD |
|---|---|---|
| ; ; | ||
| Five steps | ; reduces to | |
| Seven steps | ; already coprime | |
| ; | ; reduces to |
Proof of correctness
Lemma: if and , then for any integer , and conversely if and , then .
Consequence: .
Each step replaces the pair with where , preserving the GCD. When , the pair is with — which is therefore the GCD of the original pair.
Connection to fractions
The same algorithm applied to numerator and denominator of a fraction reduces it to lowest terms (§443 in the context of geometrical ratios, and in ch1.1.8-properties-of-fractions for ordinary fractions).
Connection to continued fractions
Lagrange observes (Add. I, Art. 4) that recording the quotients of the Euclidean algorithm — instead of the GCD — produces the continued-fraction expansion of :
So the same procedure that yields also yields the CF of — and therefore all the best rational approximations to in lower terms.