A process, based on the Division Algorithm, for finding the greatest common divisor (a, b) of two positive integers a and b. Assuming that a > b, write a = bq₁ + r₁, where 0 ≤ r₁ < b. If r₁ = 0, the gcd (a,b) is equal to b; if r₁ ≠ 0, then (a,b) = (b,r₁), so the step is repeated with b and r₁ in place of a and b. After further repetitions, the last non‐zero remainder obtained is the required gcd. For example, for a = 1274 and b = 871, write

and then (1274,871) = (871,403) = (403, 65) = (65,13) = 13.

The algorithm also enables s and t to be found such that the gcd can be expressed as sa + tb (see Bézout’s lemma). We use the previous equations in turn to express each remainder in this form. Thus,