整数同士の関係を考える上で基本となる互いに素という概念を紹介します。
最大公約数や最小公倍数をなどと関連が深いです。
互いに素
整数 \(a_1, a_2, \ldots, a_n\) が互いに素(coprime)であるとは, 最大公約数が \(1\) である, つまり
\[\mathrm{gcd}(a_1, a_2, \ldots, a_n)=1\] が成り立っていることをいう.
例
- \(2, 3\) は互いに素である. \(\mathrm{gcd}(2, 3)=1\)
- \(12, 15, 10\) は互いに素である. \(\mathrm{gcd}(12, 15, 10)=1\)
- \(33, 0, 85\) は互いに素である. \(\mathrm{gcd}(33, 0, 85)=1\)
- \(33, 121, -22\) は互いに素ではない. \(\mathrm{gcd}(33, 121, -22)=11\)
最大公約数と互いに素な整数
整数 \(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}\) は互いに素である.
証明
\(g^\prime=\mathrm{gcd}\left(\frac{a_1}{g}, \frac{a_2}{g}, \ldots, \frac{a_n}{g}\right)\) とおくと,
全ての \(i\) に対して \(\displaystyle g^\prime\mid \frac{a_i}{g}\) であるから, 整数 \(k_i\) を用いて \(\displaystyle\frac{a_i}{g}=k_ig^\prime\) と書けるが,
\(a_i=k_igg^\prime\) なので \(gg^\prime\mid a_i\) である.
最大公約数 \(g\) の定義より \(gg^\prime\mid g\) となるので \(gg^\prime=g\).
ゆえに \(g^\prime=1\).
系
整数 \(a_1, a_2, \ldots, a_n\) に対して, \(g=\mathrm{gcd}(a_1, a_2, \ldots, a_n)\) とおくとき,
\(g\neq 0\) ならば, 互いに素な \(a_1^\prime, a_2^\prime, \ldots, a_n^\prime\) を用いて \[a_1=ga_1^\prime,\ a_2=ga_2^\prime,\ \ldots\ ,\ a_n=ga_n^\prime\] と書ける.
証明
\(a_i^\prime=a_i/g\) とすればよい.
約数関係と互いに素
整数 \(a, b, n\) に対して, \(a,b\) が互いに素で \(a\mid bn\) ならば \(a\mid n\) である.
証明
整数 \(q, r\) を用いて \(n=aq+r\ (0\leq r<|a|)\) と書ける.
\(bn=aqn+rn\) であるが, \(a\mid bn\) なので, \(a\mid rn\).
\(0\leq r<|a|\) より \(r=0\) なので \(n=qa\) となり \(a\mid n\) が従う.
コメント