<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">

Last update:

<div class="arithmatex">$$\gcd(a, b) = \max \{k &gt; 0 : (k \mid a) \text{ and } (k \mid b) \}$$</div>

<p>(here the symbol "<span class="arithmatex">$\mid$</span>" denotes divisibility, i.e. "<span class="arithmatex">$k \mid a$</span>" means "<span class="arithmatex">$k$</span> divides <span class="arithmatex">$a$</span>")</p>

<p>When one of the numbers is zero, while the other is non-zero, their greatest common divisor, by definition, is the second number. When both numbers are zero, their greatest common divisor is undefined (it can be any arbitrarily large number), but it is convenient to define it as zero as well to preserve the associativity of <span class="arithmatex">$\gcd$</span>. Which gives us a simple rule: if one of the numbers is zero, the greatest common divisor is the other number.</p>

<p>The algorithm was first described in Euclid's "Elements" (circa 300 BC), but it is possible that the algorithm has even earlier origins.</p>

<h2 id="algorithm">Algorithm<a class="headerlink" href="#algorithm" title="Permanent link">&para;</a></h2>

<p>Originally, the Euclidean algorithm was formulated as follows: subtract the smaller number from the larger one until one of the numbers is zero. Indeed, if <span class="arithmatex">$g$</span> divides <span class="arithmatex">$a$</span> and <span class="arithmatex">$b$</span>, it also divides <span class="arithmatex">$a-b$</span>. On the other hand, if <span class="arithmatex">$g$</span> divides <span class="arithmatex">$a-b$</span> and <span class="arithmatex">$b$</span>, then it also divides <span class="arithmatex">$a = b + (a-b)$</span>, which means that the sets of the common divisors of <span class="arithmatex">$\{a, b\}$</span> and <span class="arithmatex">$\{b,a-b\}$</span> coincide.</p>

<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">

<span class="contributors-text">Contributors:</span>

</article>