Greatest Common Divisor: What It Is and How to Find It with Euclid's Algorithm

The Common Divisor, and the Greatest of Them All

A nonzero integer divides another number when it fits into it an exact number of times, with no remainder left over. When two numbers share one of these divisors, it’s called a common divisor. The greatest common divisor — the GCD — is the largest among these common divisors: the one natural number that divides both starting numbers and is, at the same time, the largest to do so.

Taken on its own, the idea stays abstract. Tried out on two actual numbers, it clicks: 234 and 42 share the divisors 1, 2, 3 and 6, and the largest of these, 6, is their greatest common divisor. The GCD lives inside the natural numbers, the same domain described in number sets: there’s no point looking for it among numbers with a decimal point.

Finding it by listing out divisors is manageable with small numbers, but the list gets unwieldy once the numbers grow large. That’s why a faster method exists, first described more than two thousand years ago — one of the oldest chapters of arithmetic.

Euclid’s Algorithm, Step by Step

Euclid’s algorithm finds the GCD without listing anything: it works through divisions with remainder, repeated on whatever pair of numbers the previous division produces. Run on 234 and 42, it goes like this:

The last nonzero remainder is 6: that’s the greatest common divisor of 234 and 42, the same number found a moment ago by listing divisors by hand.

Worked example: for the GCD of 48 and 18, the same pattern repeats. 48 = 18×2+12, then 18 = 12×1+6, then 12 = 6×2+0. The remainder right before the zero is 6, so the GCD of 48 and 18 is 6.

Why the Procedure Works

The principle holding the whole algorithm together is this: the greatest common divisor of two numbers stays identical to the one formed by the second number and the remainder of dividing the two. The GCD of 234 and 42 equals the GCD of 42 and 24, because 234 can be written as 42×5+24: any number that divides both 234 and 42 also divides 24, and any number that divides 42 and 24 also divides 234, so the two sets of common divisors always coincide.

Repeating the step, the pair of numbers shrinks every round, and the remainder keeps getting smaller. A sequence of natural numbers that keeps decreasing cannot go on forever: it has to reach zero after a finite number of steps. When it does, the last nonzero remainder is the greatest common divisor being sought.

Older Than the School That Teaches It

Euclid describes this procedure in Book VII of the Elements, written around 300 BCE. The book opens with a definition of the unit as the basis of the idea of number, and defines a number itself as a quantity made up of units: a smaller number “measures” a larger one when it is contained in it a whole number of times — another way of saying it divides it exactly.

In Proposition 1 of Book VII, Euclid describes a test for whether two numbers share no common factor other than 1: the smaller is repeatedly subtracted from the larger, until only a unit is left. In Proposition 2, he tackles what we’d now call finding the greatest common divisor, using the same kind of repeated subtraction, down to a remainder that divides the one before it exactly — that remainder is the GCD being sought. The method taught today, with division, is a faster form of the same principle Euclid described through repeated subtraction: a division, after all, is nothing more than a subtraction repeated several times in a single step.

Where It’s Used, Beyond Math Homework

According to the Wikipedia entry “Euclidean algorithm,” the greatest common divisor of two numbers can always be expressed as a sum of the two starting numbers, each multiplied by a suitable integer, possibly negative: this is Bézout’s identity, and the two coefficients are found by retracing the algorithm’s steps backward, in a separate procedure from the one described above. Still according to Wikipedia, a variant of the same algorithm computes the modular inverse, a step used in the RSA encryption that protects online transactions. The algorithm is also efficient: Gabriel Lamé proved in 1844 that it takes at most five steps for every digit the smaller number has.

Anyone studying algebra and Euclidean geometry runs into the same name, Euclid, through two different doors: the geometry of the Elements, and this arithmetic procedure — both born in the same treatise.