Editing Greatest common divisor (section)

=== Euclidean algorithm ===
{{Main|Euclidean algorithm}}
[[File:The Great Common Divisor of 62 and 36 is 2.ogv|thumb|Animation showing an application of the Euclidean algorithm to find the greatest common divisor of 62 and 36, which is 2.]]

A more efficient method is the ''Euclidean algorithm'', a variant in which the difference of the two numbers {{mvar|a}} and {{mvar|b}} is replaced by the ''remainder'' of the [[Euclidean division]] (also called ''division with remainder'') of {{mvar|a}} by {{mvar|b}}.

Denoting this remainder as {{math|''a'' mod ''b''}}, the algorithm replaces {{math|(''a'', ''b'')}} with {{math|(''b'', ''a'' mod ''b'')}} repeatedly until the pair is {{math|(''d'', 0)}}, where {{mvar|d}} is the greatest common divisor.

For example, to compute gcd(48,18), the computation is as follows:
: <math>\begin{align}\gcd(48,18)\quad&\to\quad \gcd(18, 48\bmod 18)= \gcd(18, 12)\\
&\to \quad \gcd(12, 18\bmod 12)= \gcd(12,6)\\
&\to \quad \gcd(6,12\bmod 6)= \gcd(6,0).\end{align}</math>
This again gives {{math|1=gcd(48, 18) = 6}}.