整数の積=最大公約数×最小公倍数

本記事の内容

本記事は「最小公倍数、最大公約数とは何か？」というところから「2つ以上の整数の積はその整数の最大公約数と最小公倍数の積と等しい」ということを証明する記事です。

本記事を読むに当たり、割り算定理(剰余の定理)を知っている必要があるため、以下の記事も合わせてご覧ください。

割り算定理(剰余の定理)の証明

...

for-spring.com

2023.02.17

最大公約数と最小公倍数

「今更最大公約数と最小公倍数って言われても、知ってますよ」という方も多いと思います。
なにせ筆者の記憶が正しければ、最大公約数と最小公倍数が出現したのは中学数学だからです。

もちろん、中学数学で習った最大公約数と最小公倍数と本記事で述べる最大公約数と最小公倍数は同じものです。
ただ、中学数学で学んだ最大公約数及び最小公倍数は少々直感的な説明だったと記憶しています。
そこで、整数論的に、しっかりと定めようという話です。

公倍数と最小公倍数

予想通りたいしたことではありません。
しかしながら案外落とし穴があるのです。

公倍数とは2つ以上の整数に対する共通な倍数のことを指します。
公倍数は倍数なのですから、いくらでもあります。
正の公倍数もあれば負の公倍数もあります。
したがって、公倍数には本来最小値というものはありません。

「え？最小公倍数って公倍数の中で最小のものじゃないの？」と思われるかもしれませんが、よくよく考えてみると公倍数自体に最小値はないのです(これが落とし穴)。

しかしながら、公倍数に絶対値をつけてみてはどうでしょうか。
公倍数とはいえ整数ですから、絶対値をつけると必ず\(0\)以上の整数となります。
\(0\)は任意の整数の倍数です(実際、どんな整数に\(0\)を掛けても\(0\)だから)。
要するに、公倍数に絶対値をつけることで最小値が得られます。
先の通り、\(0\)はどんな整数の倍数ですので、それは除外し公倍数に絶対値をつけたものの中で最小の値が最小公倍数の正体なのです。

要するに

ということなのです。

公約数と最大公約数

これもたいしたことではありません。
公倍数とくらべて落とし穴もほとんど無いと言って良いでしょう。

公約数は、2つ以上の整数に共通な約数(例えば\(1\))のことを指します。
約数も整数ですので、正の約数もあれば負の約数もあります。
公倍数と異なるのは、公約数は最大値も最小値も存在するということです。

なぜなら、\(a,b\in\mathbb{Z}\)の公約数は\(\left|a\right|\)および\(\left|b\right|\)より大きくなることはなく、また\(a\)および\(b\)よりも小さくなることはないからです。
例を挙げれば、\(a=-6\)と\(b=4\)の場合を考えてみます。
\(-6\)と\(4\)の公倍数は\(-2,\ -1,\ 1,\ 2,\)です。
確かに\(\left|6\right|\)および\(\left|4\right|\)より大きい整数もなければ、\(-6\)および\(4\)より小さい整数もありません。
したがって、最大値が存在します。
この最大値を最大公約数と呼ぶ、という話なのです。

要するに、

ということです。

最小公倍数、最大公約数の性質

では、最小公倍数、最大公約数の性質を紹介します。
どれも基本的ですが、よく使う性質です。

2つ以上の整数の公倍数は最小公倍数の倍数である。

定理1.の証明

\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の最小公倍数を\(l>0\)とします。
また、\(m\)を\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の任意の公倍数とします。
このとき、割り算定理(剰余の定理)を使います。

定理0.(割り算定理、剰余の定理)の証明は【代数学の基礎シリーズ】初等整数論編 その2を御覧ください。

定理0.(割り算定理、剰余の定理)により、
$$
m=ql+r\quad 0\leq r< l
$$
という\(q,r\in\mathbb{Z}\)が一意的に存在します。
故に、
$$
r=m-ql
$$
です。
\(m\)は\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の任意の公倍数であり、\(l\)は\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の最小公倍数ですので、\(m\)も\(l\)も\(a_1\)の倍数です。
ここで、次の事実を使います。

定理2.の証明は【代数学の基礎シリーズ】初等整数論編 その2を御覧ください。

定理2.により、\(r\)は\(a_1\)の倍数となります。
少し詳しく書けば、\(m\)は\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の任意の公倍数だから、もちろん\(a_1\)の倍数です。
また、\(l\)は\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の最小公倍数ですので、これも\(a_1\)の倍数です。
故に
\begin{eqnarray}
(\exists k_1,k_2\in\mathbb{Z})\ {\rm s.t.}\ m=k_1a_1,\ l=k_2a_1
\end{eqnarray}
となります。
今、\(r=m-ql\)であるので、\(r=m-ql=k_1a_1-q\cdot k_2a_1=a_1(k_1-qk_2)\)となるため、\(r\)は\(a_1\)の倍数ということになります。

同様にして、\(r\)は\(a_2,a_3,\cdots\)の倍数となります。
すなわち、\(r\)は\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)すべての倍数のため、\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の公倍数です。

\(l\)は\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の最小公倍数であるため、\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の公倍数の中で\(0\)を除いて絶対値が最小ものです。
今、\(0\leq r<l\)なわけですので、これは\(r=0\)以外ありえない、ということになります(\(r\in\mathbb{N}\cup\left\{0\right\}\)により)。

したがって、\(r=0\)から\(m=ql\)となり、\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の任意の公倍数は\(a_1,a_2,a_3,\cdots\in\mathbb{Z}\)の最小公倍数の倍数であることが証明されました。

定理1.の証明終わり

2つ以上の整数の公約数は最大公約数の約数である。

定理3.の証明

\(m=\gcd(a_1,a_2,a_3,\cdots,a_n)\)、すなわち\(a_1,a_2,a_3,\cdots a_n\in\mathbb{Z}\)の最大公約数を\(m\)とし、\(d\)を\(a_1,a_2,a_3,\cdots a_n\in\mathbb{Z}\)の任意の公約数とします。
このとき、\(d\)が\(m\)の約数である、というは\(m={\rm lcm}(d.m)\)、すなわち\(m\)と\(d\)の最小公倍数が\(m\)であることと同値です。

実際、仮に\({\rm lcm}(m,d)=m\)だとすると、\(m\)と\(d\)の最小公倍数が\(m\)ということですので、\(m\)は\(m\)と\(d\)の公倍数です。
故に、\(m=kd\)という\(k\in\mathbb{Z}\)が存在します。
したがって、\(d\)は\(m\)の約数です。

逆に、\(m=kd\)という\(k\in\mathbb{Z}\)が存在したとすると、\(m\)は\(m\)と\(d\)の公倍数です。
今、\(m=kd\)により\(m>d\)です。
\({\rm lcm}(m,d)\)は\(m\)と\(d\)の公倍数の絶対値の中で最小のものですから、\(m\)以外ありえない、ということになります。

さて、今\(l-{\rm lcm}(m,d)\)、すなわち\(m\)と\(d\)の最小公倍数とします。
\(m\)は\(a_1,a_2,a_3,\cdots a_n\in\mathbb{Z}\)の最大公約数ですから、\(a_1\)は\(m\)の倍数です。
また、\(d\)は\(a_1,a_2,a_3,\cdots a_n\in\mathbb{Z}\)の最大公約数の公約数ですから、\(a_1\)は\(d\)の約数でもあります。
ここで、定理1.を使います。

定理1.により、\(a_1\)は\(m\)と\(d\)の公倍数となり、したがって\(l\)の倍数となります。
同様にして\(l\)は\(a_2,a_3,\cdots a_n\in\mathbb{Z}\)の公約数でもあります。
故に、\(l\leq m\)です(\(m\)は公約数の中で最大のものだから)。

\(l\)は\(m\)の倍数だから、\(l\geq m\)でもあります。
したがって、\(l=m\)となるわけです。

定理3.の証明終わり

2つの整数の積はそれらの最小公倍数と最大公約数の積と等しい。

本題です。

定理4.の証明

\(l={\rm lcm}(a,b)\)ですから、\(l\)は\(a,b\)の公倍数です。
故に、
$$
(\exists a^\prime,b^\prime\in\mathbb{Z})\ {\rm s.t.}\ l=ab^\prime\land l=a^\prime b\tag{1}
$$
です。

さて、\(ab\)はもちろん\(a\)と\(b\)の公倍数です(双方で割り切れるため)。
故に、再度定理1.を使うことで、\(ab\)は\(l\)の倍数であることがわかります。
したがって、
$$
(\exists d\in\mathbb{Z})\ {\rm s.t.}\ ab=dl\tag{2}
$$
です。
(1)を(2)に代入して
$$
a=da^\prime,\quad b=db^\prime\tag{3}
$$
を得ます。
すなわち、\(a\)も\(b\)も\(d\)の倍数であるため、\(d\)は\(a\)と\(b\)の公約数です。

故に、定理3.から、2つ以上の整数の公約数は最大公約数の約数であるため、
$$
(\exists e\in\mathbb{Z})\ {\rm s.t.}\ m=de
$$
です。
今、\(m=\gcd(a,b)\)により\(a\)と\(b\)は\(m\)で割り切れるから、(3)で\(a^\prime\)と\(b^\prime\)は\(e\)で割り切れます。
実際、\(a=mk_1\)、\(b=mk_2\)と書けることから
$$
mk_1=da^\prime,\quad mk_2=db^\prime
$$
となり、\(m=de\)により
$$
dek_1=da^\prime,\quad dek_2=db^\prime\Longleftrightarrow ek_1=a^\prime,\quad ek_2=b^\prime
$$
となるからです。

故に、
$$
(\exists a^{\prime\prime},b^{\prime\prime}\in\mathbb{Z})\ {\rm s.t.}\ a^\prime=ea^{\prime\prime},\ b^\prime=eb^{\prime\prime}
$$
です。
これを(1)に代入すると、
$$
l=ab^{\prime\prime}e=ba^{\prime\prime}e\tag{4}
$$
となります。

仮に、\(e=1\)だったとすれば、\(m=de\)により\(m=d\)となるため、(2)により\(ab=lm\)が成り立ち、証明完了です。
そこで、\(e>1\)だったとしましょう。
(4)から、
$$
\frac{l}{e}=ab^{\prime\prime}=ba^{\prime\prime}
$$
となり、\(ab^{\prime\prime},ba^{\prime\prime}\in\mathbb{Z}\)から、\(\displaystyle\frac{l}{e}\)は\(a\)と\(b\)の公倍数となります。
しかし、\(e>1\)であることから、\(\displaystyle\frac{l}{e}<l\)です。
すなわち、最小公倍数\(l\)よりも小さい公倍数が存在することになってしまい、矛盾です。
したがって、\(e=1\)でなければならないため、証明完了です。

定理4.の証明終わり

皆様のコメントを下さい！

最小公倍数、最大公約数は中学生で出現しますが、概念自体は小学生でも分かりそうなほどシンプルなものです。
しかし、ちゃんと考えてみようとすると案外落とし穴があったりするものです。
皆様の経験でなにか専門的に勉強してから「あれ？実はあれは厳密じゃなかったんだ？」となったことがありましたらぜひコメントで教えて下さい！

結

今回は「最小公倍数、最大公約数とは何か？」というところから「2つ以上の整数の積はその整数の最大公約数と最小公倍数の積と等しい」ということを証明しました。

最大公約数については、中学校で学んだことほぼそのまんまでしたが、最小公倍数については、よくよく考えてみると「落とし穴」があるのです。

案外「あれ？誤認してたかも」ということに気がつくのもまた楽しいですよね。

次回は最大公約数、について非常によく使う事実を証明します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)

初等整数論について、以下の書籍をオススメします！