最小公倍数

整数の最小公倍数の定義を紹介します。

最小公倍数とは普通、複数の整数の公倍数のうち最小の自然数ことを指しますが、
ここではより広い定義で紹介します。

最小公倍数の性質はこちらを参照してください。

最小公倍数

\(n\in\mathbf{N}\) として, 写像 \(\mathrm{lcm}\ :\ \mathbf{Z}^n\rightarrow\mathbf{N}\) を以下のように定める:

\((a_1, a_2, \ldots, a_n)\in\mathbf{Z}^n\) に対して

  1. 任意の \(1\leq i\leq n\) に対して \(a_i\mid l\).
  2. 整数 \(m\) が, 任意の \(1\leq i\leq n\) に対して \(a_i\mid m\) ならば \(l\mid m\).

を満たす自然数 \(l\) がただ1つ存在する. そこで \(\mathrm{lcm}(a_1, a_2, \ldots, a_n)=l\) とする.

この \(\mathrm{lcm}(a_1, a_2, \ldots, a_n)\) を \(a_1, a_2, \ldots, a_n\) の最小公倍数(least common divisor) という.

証明

任意の \((a_1, a_2, \ldots, a_n)\in\mathbf{Z}^n\) に対して, 上記の条件1,2 を満たす自然数 \(l\) がただ1つ存在すること
(存在と一意性)を示す.
条件1,2 は

  1. 任意の \(a\in \{a_1,\ldots,a_n\}\) に対して \(a\mid l\).
  2. 整数 \(m\) が 任意の \(a\in \{a_1,\ldots,a_n\}\) に対して \(a\mid m\) ならば \(l\mid m\).

と同値である.

[\(n=0\) のとき]
\(\mathrm{lcm}\ :\ \{\emptyset\}\rightarrow\mathbf{N}\) を考える事となり, 条件 1,2 は

  1. 任意の \(a\in\emptyset\) に対して \(a\mid l\).
  2. 整数 \(m\) が 任意の \(a\in\emptyset\) に対して \(a\mid m\) ならば \(l\mid m\).

となるが, 条件1は常に真である.
また, 条件2の「任意の \(a\in\emptyset\) に対して \(a\mid m\)」の部分が常に真なので, 任意の整数 \(m\) に対して条件2は真でなければならない.
つまり, 自然数 \(l\) は任意の整数 \(m\) に対して \(l\mid m\) を満たす. そのような \(l\) は \(l=1\) のみ. (存在と一意性)
ゆえに \(n=0\) のとき \(\mathrm{lcm}()=1\).

[\(n\geq 1\) のとき]
\(a_1, a_2, \ldots, a_n\) に対して \(a_i=0\) となる \(i\) が存在するとき,
条件1 を満たす自然数 \(l\) は \(0\mid l\) を満たさなければならず, これは \(l=0\) のみである.
全ての \(i\) に対して \(a_i\mid 0\) であるから \(l=0\) は条件1 を満たす.
また, 条件2 を満たす整数 \(m\) は \(0\mid m\) を満たさなければならず,
\(m=0\) となり, \(0\mid 0\) であるから \(l=0\) は条件2 も満たす.
ゆえに \(\mathrm{lcm}(a_1, a_2, \ldots, a_n)=0\). (存在と一意性)

\(a_1, a_2, \ldots, a_n\) が全て \(0\) でないとき,
整数 \(a\) に対して \(M(a)\) を整数 \(a\) の正の倍数の集合として, \(M=\displaystyle\bigcap_{i=1}^nM(a_i)\) と置く.
今, \(N=|a_1a_2\cdots a_n|\) (\(|\cdot|\) は絶対値)と置くと,
任意の \(i\) に対して \(N\in M(a_i)\) であるから \(M\neq\emptyset\) である.
\(l=\min M\) とおくと, \(l\) は明らかに条件1 を満たす.
また, 任意の \(a\in \{a_1,\ldots,a_n\}\) に対して \(a\mid m\) となる整数 \(m\) を取ると,
\(m\mid |m|\) であるから \(|m|\in M\). よって \(|m|\geq l\).
このとき \(0\leq lk-|m|< l\) となる自然数 \(k\) が存在する.
\(lk-|m|>0\) のとき, 任意の \(a\in \{a_1,\ldots,a_n\}\) に対して \(a\mid (lk-|m|)\) であるから
\(lk-|m|\in M\) であるが, これは \(l\) の最小性に矛盾する.
\(lk-|m|=0\) つまり \(lk=|m|\) のとき, \(l\mid m\).
ゆえに \(l\) は条件2 を満たす. (存在)
ここで, 自然数 \(l^\prime\) が条件1,2 を満たすとすると,
\(l\) に対する条件1 と \(l^\prime\) に対する条件2 より \(l^\prime\mid l\).
\(l^\prime\) に対する条件1 と \(l\) に対する条件2 より \(l\mid l^\prime\).
\(l, l^\prime\) は共に自然数なので \(l=l^\prime\). (一意性)

以上より, 任意の \((a_1, a_2, \ldots, a_n)\in\mathbf{Z}^n\) に対して示された.

  • \(14\) と \(21\) の最小公倍数は \(42\) である. \(\mathrm{lcm}(14, 21)=42\)
  • \(3, -5, 4\) の最小公倍数は \(60\) である. \(\mathrm{lcm}(3, -5, 4)=60\)
  • \(0\) と整数 \(m\) の最小公倍数は \(0\) である. \(\mathrm{lcm}(0, m)=0\)

コメント

タイトルとURLをコピーしました