Page "Greatest common divisor" Paragraph 30

A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference.

To compute gcd ( 48, 18 ), divide 48 by 18 to get a quotient of 2 and a remainder of 12.

Then divide 18 by 12 to get a quotient of 1 and a remainder of 6.

Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd.

Note that we ignored the quotient in each step except to notice when the remainder reached 0, signalling that we had arrived at the answer.

Formally the algorithm can be described as: