Definition:Greatest common divisor

From CS2800 wiki
If [math]a, b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math], then the greatest common divisor [math]g [/math] of [math]a [/math] and [math]b [/math] satisfies:
  1. [math]g \href{/cs2800/wiki/index.php/%5Cmid}{\mid} a [/math] and [math]g \href{/cs2800/wiki/index.php/%5Cmid}{\mid} b [/math] (i.e. [math]g [/math] is a common divisor), and
  2. for any [math]c [/math] that divides both [math]a [/math] and [math]b [/math], we have [math]c ≤ g [/math] (in other words, [math]g [/math] is greater than any other common divisor). In fact we will show that [math]c \href{/cs2800/wiki/index.php/%5Cmid}{\mid} g [/math] (which implies that [math]c ≤ g [/math]).