公約数

整数の公約数の定義を紹介します。

公約数とは複数の整数に共通する約数のことを指します。

\(n\) 個の整数 \(a_1, a_2, \ldots, a_n\) に対して, 整数 \(d\) が任意の \(1\leq i\leq n\) に対して \(d\mid a_i\) を満たすとき
\(d\) を \(a_1, a_2, \ldots, a_n\) の公約数(common divisor)であるという.

公約数の基本事項

任意の \(a_1, a_2, \ldots, a_n\) に対して \(\pm1\) はそれらの公約数である.
\(d\) を \(a_1, a_2, \ldots, a_n\) の公約数, \(d^{\prime}\) を \(d\) の約数とすると \(d^{\prime}\) は \(a_1, a_2, \ldots, a_n\) の公約数である.

証明

任意の整数 \(m\) に対して \(\pm1\mid m\) より明らか.
任意の \(1\leq i\leq n\) に対して \(d\mid a_i\) かつ \(d^{\prime}\mid d\) なので, 約数関係の推移性より, 任意の \(1\leq i\leq n\) に対して \(d^{\prime}\mid a_i\).

例

\(60\) と \(210\) の公約数は \(\pm1, \pm2, \pm3, \pm5, \pm6, \pm10, \pm15, \pm30\) である.
\(10, 55, -15\) の公約数は \(\pm1, \pm5\) である.
\(0\) と整数 \(m\) の公約数は \(m\) の約数である. 例えば \(0, 6\) の公約数は \(\pm1, \pm2,\pm3,\pm6\) である.