Definition:Gcd

From CS2800 wiki
Definition: gcd
Euclid's GCD algorithm is the function [math]\href{/cs2800/wiki/index.php/Gcd}{gcd} : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%C3%97}{×} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] which is given as follows: [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,0) := a [/math], and for [math]b \gt 0 [/math], [math]\href{/cs2800/wiki/index.php/Gcd}{gcd}(a,b) = \href{/cs2800/wiki/index.php?title=G&action=edit&redlink=1}{g}(b,r) [/math] where [math]r = \href{/cs2800/wiki/index.php/Rem}{rem}(a,b) [/math].

This function is a good inductively defined function because by definition, [math]\href{/cs2800/wiki/index.php/Rem}{rem}(a,b) \lt b [/math], so the second argument is decreasing in the inductive definition.

The algorithm can be extended to operate on negative integers by simply taking the gcd of the absolute values of its arguments.