公約数

2つ以上の整数に共通な約数。公約数は、最大公約数の約数となる。例えば、${\displaystyle 12}$ と${\displaystyle 15}$ の公約数は${\displaystyle 12}$ と${\displaystyle 15}$ の最大公約数${\displaystyle 3}$ を求め、最大公約数${\displaystyle 3}$ の約数${\displaystyle 1,\ 3}$ となる。

一般には約数は自然数の範囲内で考えることが多いので、例えば、${\displaystyle 36}$ と${\displaystyle 48}$ と${\displaystyle 108}$ （この最小公倍数は432）の公約数は${\displaystyle \{1,\ 2,\ 3,\ 4,\ 6,\ 12\}}$ である。約数を整数の範囲内で考えるとき、約数には符号の違いを許すので、その個数は${\displaystyle 2}$ 倍となる。どういう範囲で考えているのかを常にはっきりさせておくべきである。

公約数の内最大のものを最大公約数という。公約数は、全て最大公約数の約数であるので、最大公約数を求めれば全ての公約数を求めることができる。前述の例で言えば、${\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}$ は互いに素であるという。

プロジェクト 数学

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