公約数

公約数の内最大のものを最大公約数という。公約数は、全て最大公約数の約数であるので、最大公約数を求めれば全ての公約数を求めることができる。前述の例で言えば、${\displaystyle 36}$と${\displaystyle 48}$と${\displaystyle 108}$との最大公約数は${\displaystyle 12}$であるので、${\displaystyle 12}$の約数をすべて求めればそれが3つの数の全ての公約数になる。${\displaystyle 1}$は全ての自然数の公約数である。

また、2つ以上の多項式について、それぞれを因数分解したときに共通に現れる因数（因子、factor）も公約数（あるいは公約元、共通因子、common factor など）と呼ぶ。例えば、${\displaystyle (x+1)^{2}}$と${\displaystyle x^{2}-1}$について、${\displaystyle x+1}$は公約数である。

最大公約数が${\displaystyle 1}$であるような2つの整数の組は、互いに素であるという。

単項イデアル整域${\displaystyle R}$（例えば整数の全体${\displaystyle \mathbb {Z} }$や実数係数多項式の全体${\displaystyle R[x]}$はそうである）において、その2つの元${\displaystyle a,\ b}$に対し、集合

${\displaystyle aR+bR=\{ax+by|x,\ y\in R\}}$

に含まれるイデアルの生成元を${\displaystyle a}$と${\displaystyle b}$の公約元という。特に

${\displaystyle aR+bR=cR}$

を満たす${\displaystyle c\in R}$を${\displaystyle a}$と${\displaystyle b}$の最大公約元という。更に、この${\displaystyle c}$が${\displaystyle R}$の単元であるとき、${\displaystyle a}$と${\displaystyle b}$は互いに素であるという。つまり、

${\displaystyle a}$と${\displaystyle b}$が互いに素${\displaystyle \Leftrightarrow ax+by=1}$となる${\displaystyle x,\ y\in R}$が存在する。

互いに素という概念は、更に一般の環でイデアルの間の関係として一般化される。環${\displaystyle S}$の2つのイデアル${\displaystyle I,\ J}$が

${\displaystyle I+J=S}$

を満たすとき、${\displaystyle I}$と${\displaystyle J}$は互いに素であるという。

プロジェクト 数学

• 公倍数
• 最大公約数
• ユークリッドの互除法