公約数

$a, b \in \Z$の数 a, bを考える。このとき、

• $a = cn$
• $b = dm$

の式を考える。このとき、cをaの約数, dをbの約数を呼ぶが、$c = d$が成立する場合、その数を公約数と呼ぶ。

約数は有限であるので(約数の項目を見よ)、公約数も有限である。このとき、最大の公約数を取ることが可能である。これを最大公約数と呼ぶ。