View source for Definition:Greatest common divisor

{{Def|1=Greatest common divisor|2=
If <math>a, b [[∈]] [[ℤ]]</math>, then [[the]] [[greatest common divisor]] <math>g</math> of <math>a</math> and <math>b</math> satisfies:

# <math>g [[\mid]] a</math> [[and]] <math>g [[\mid]] b</math> (i.e. <math>g</math> is a common [[divisor]]), and
# [[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 [[\mid]] g</math> (which [[Claim:if a ❘ b then a ≤ b|implies]] that <math>c ≤ g</math>).
}}