最大公約数の性質

最大公約数の性質について紹介します。

最大公約数の定義はこちらを参照してください。

最大公約数の性質

\((a_1, a_2, \ldots, a_n)\in\mathbf{Z}^n\) として, \(S_n\) の \(n\) 次対称群とするとき

\(\mathrm{gcd}(a_1, a_2, \ldots, a_n)\mid a_i\)
任意の \(\sigma\in S_n\) に対して \(\mathrm{gcd}(a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)})=\mathrm{gcd}(a_1, a_2, \ldots, a_n)\).
\(\mathrm{gcd}(\mathrm{gcd}(a_1, a_2, \ldots, a_{n-1}), a_n)=\mathrm{gcd}(a_1, a_2, \ldots, a_n)\)
\(\mathrm{gcd}(|a_1|, |a_2|, \ldots, |a_n|)=\mathrm{gcd}(a_1, a_2, \ldots, a_n)\)

証明

１. 定義より明らか.

２. \(\{a_1, a_2, \ldots, a_n\}=\{a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)}\}\) より明らか.

３. \(g=\mathrm{gcd}(a_1, a_2, \ldots, a_n),\ g_0=\mathrm{gcd}(a_1, a_2, \ldots, a_{n-1}),\ g^\prime=\mathrm{gcd}(g_0, a_n), \) と置くと,
　\(1\leq i\leq n-1\) に対して \(g_0\mid a_i\) であり, \(g^\prime\mid g_0,\ g^\prime\mid a_n\) なので
　\(1\leq i\leq n\) に対して \(g^\prime\mid a_i\) より \(g^\prime\mid g\).
　また, \(1\leq i\leq n-1\) に対して \(g\mid a_i\) なので \(g\mid g_0\) であり, かつ \(g\mid a_n\) より \(g\mid g^\prime\).
　\(g,g^\prime\) は共に自然数なので \(g^\prime=g\).

４. 整数 \(a, d\) に対して \(d\mid a\ \Longleftrightarrow\ d\mid|a|\) なので良い.

最大公約数と除算

整数 \(a_1, a_2, \ldots, a_n\) に対して \(g=\mathrm{gcd}(a_1, a_2, \ldots, a_n)\) とするとき, \(g\neq 0\) ならば \[\mathrm{gcd}\left(\frac{a_1}{g}, \frac{a_2}{g}, \ldots, \frac{a_n}{g}\right)=1\] が成り立つ. つまり, \(\displaystyle\frac{a_1}{g}, \frac{a_2}{g}, \ldots, \frac{a_n}{g}\) は互いに素となる.

証明

\(b_i=a_i/g\) と置くと, 最大公約数の定義(条件１)より \(g\mid a_i\) なので \(b_i\) は整数である.
\(g^\prime=\mathrm{gcd}(b_1, b_2, \ldots, b_n)\) と置くと, \(g^\prime\mid b_i\) なので
整数 \(k_i\) を用いて \(b_i=k_ig^\prime\) と書けるが, \(b_i=a_i/g\) より, \(a_i=k_igg^\prime\) となる.
これより \(gg^\prime\mid a_i\) であるが最大公約数の定義(条件２)より \(gg^\prime\mid g\) となる.
明らかに \(g\mid gg^\prime\) であり, \(g, gg^\prime\) は自然数なので \(g=gg^\prime\).
\(g\neq0\) より \(g^\prime=1\) が従う.