Editing Greatest common divisor (section)

=== Euclid's algorithm ===
{{Main|Euclidean algorithm}}
The method introduced by [[Euclid]] for computing greatest common divisors is based on the fact that, given two positive integers {{mvar|a}} and {{mvar|b}} such that {{math|''a'' > ''b''}}, the common divisors of {{mvar|a}} and {{mvar|b}} are the same as the common divisors of {{math|''a'' – ''b''}} and {{mvar|b}}.

So, Euclid's method for computing the greatest common divisor of two positive integers consists of replacing the larger number with the difference of the numbers, and repeating this until the two numbers are equal: that is their greatest common divisor.

For example, to compute {{math|gcd(48,18)}}, one proceeds as follows:
: <math>\begin{align}\gcd(48,18)\quad&\to\quad \gcd(48-18, 18)= \gcd(30,18)\\
&\to \quad \gcd(30-18, 18)= \gcd(12,18)\\
&\to \quad \gcd(12,18-12)= \gcd(12,6)\\
&\to \quad \gcd(12-6,6)= \gcd(6,6).\end{align}</math>
So {{math|1=gcd(48, 18) = 6}}.

This method can be very slow if one number is much larger than the other. So, the variant that follows is generally preferred.