Divisibility and the Euclidean algorithm

For integers a and b, saying that a divides b means there is an integer k with b = ak. The witness k matters: 4 divides 20 because 20 = 4 × 5, whereas 4 does not divide 22. Every nonzero integer divides zero, but zero divides only zero. In this lesson the greatest common divisor is defined for pairs not both zero and is always chosen positive.

A common divisor divides each member of a pair. If it divides a and b, it also divides every integer combination ua + vb: substitute a = dr and b = ds, then factor out d. This closure under subtraction explains the algorithm. Notice that a common divisor need not divide the quotient a/b as an integer; introducing fractions would change the problem and discard the structure we need.

When b is positive, division with remainder gives a unique pair q and r with a = qb + r and zero at most r less than b. Any divisor of a and b divides r = a − qb. Conversely, any divisor of b and r divides a = qb + r. The sets of common divisors therefore agree in both directions. This is stronger than merely noticing that one particular divisor survives.

Apply the same step to b and r until a remainder is zero. Each nonzero remainder is a smaller positive integer than its predecessor, so the procedure cannot continue forever. At the last step the positive member divides the zero member, and its greatest common divisor with zero is itself. Working backward through the invariant proves that this last nonzero remainder is the answer for the original pair.

The algorithm is useful even when factorization would be expensive. Successive remainder equations are easy to check using multiplication and subtraction, and the final nonzero remainder gives a compact certificate of the result. A single wrong quotient can corrupt every later line, so verify the range condition on every remainder. For a negative starting integer, division still works with a positive divisor and a nonnegative remainder; alternatively start with absolute values.

The word greatest refers to ordinary positive size, but the gcd also has a stronger property: every common divisor divides it. That property follows from the preserved divisor sets and the final pair. It lets the gcd organize later solvability tests for integer equations. A calculator displaying a decimal quotient has not answered this question; the important information is the integer remainder and the fact that the problem has become smaller.