Corollaryは必然に。

このブログは「コロちゃんぬ」の提供でお送りします

「最大公約数と最小公倍数の分配法則」を図式で証明してみた

この記事は日曜数学 Advent Calendar 2023の9日目の記事です。前回はふくまさんの【代数的トポロジー】「n次元トーラス上のお掃除ロボットと経路計画(path planning)」【LSカテゴリー特別編】でした。師走の時期はトーラスも掃除しないといけないので助かります。

今日は次の分配法則について考えます(以降、特に断りがなければ$a$,$b$などの文字はすべて正の整数とします)。

定理
$a\land b$を$a$と$b$の最大公約数,$a\vee b$を$a$と$b$の最小公倍数とする.このとき,次の分配法則が成り立つ.
\begin{align}
a\vee (b \land c) &= (a\vee b) \land (a\vee c)\label{1} \\
a\land (b \vee c) &= (a\land b) \vee (a\land c)\label{2}
\end{align}
顔文字(・∧・)のようにしか見えない人のために日本語で書くと、\eqref{1}の式は

「$a$と($b$と$c$の最大公約数)の最小公倍数」
=「($a$と$b$の最小公倍数)と($a$と$c$の最小公倍数)の最大公約数」

を表します。つまり、「$a$との最小公倍数を計算する」という操作を$b$と$c$に分配してもよいことを意味しています。

例えば$a=8$,$b=12$,$c=15$とすると、

\begin{align*}
(\eqref{1}\text{の左辺}) &= 8\vee (12 \land 15) = 8\vee 3 = 24, \\
(\eqref{1}\text{の右辺}) &= (8\vee 12) \land (8\vee 15)\\
& = 24\land 120 = 24
\end{align*}

となるので、確かに成り立ちますね。

また、\eqref{2}の式は最大公約数と最小公倍数を入れかえた式になります。


本日はこの分配法則を証明していきます。


しかし、真面目に証明しようとすると、約数や倍数関係に関する式がたくさん出てきて読むのが大変です。

そこで、約数の関係を図式にする(矢印で結ぶ)ことで、視覚的に考察・証明をしていきたいと思います。

かなり大げさに言えば、圏論の普遍性を使った証明となります。圏論は知らなくても大丈夫ですが、少し知っている人や知らないけれど雰囲気だけ気になる人は要所要所に差し込まれた「余談」を読んでいただければと思います。



記号の導入

$a$は$b$の約数である($a$は$b$を割り切る、 $b$は$a$の倍数である、$b$は$a$で割り切れる)こと、つまり
\[
b=ka
\]をみたす正の整数$k$が存在するとき、
\[
a\overset{\times k}{\longrightarrow}b
\]と表すことにします。また、2つの整数が約数や倍数の関係にあることを整除関係と言います。

ただし、整除関係を矢印で表すのは一般的な記法ではないので注意してください($a\mid b$と書くのが一般的)。また、整除関係にだけ注目したい場合は「$\times k$」を省略することがあります。

例えば、$3$は$6$の約数($6=2\times 3$)なので
\[
3\overset{\times 2}{\longrightarrow}6
\]となります。また、$4$は$6$の約数ではないので矢印は引けません。

余談 圏というのは「対象の集まりと、対象と対象を結ぶ射(矢印)の集まりでできた数学的構造」です(とても雑な説明)。一般に対象間の射はたくさんあるのが普通ですが、対象を正の整数、射を約数関係としてできる数学的構造を圏とみたとき、対象間の射が多くても1本しかないようなガリガリにやせた圏となってます。圏と扱うには物足りない感はありますが、その分親しみやすい例にはなっているのかなぁと思います。

矢印の基本性質

この記事で使う整除関係の性質や法則をサクッと紹介します。

反射律:矢印は自分自身に引ける

おぼろげながら浮かんできたのですが、$46$は$46$の約数です。だからこそ
\[
46\overset{\times 1}{\longrightarrow}46
\]と表せます。あるいは
\begin{equation*}
\xymatrix{46 \ar@(ur,dr)[ ]^-{\times 1}}
\end{equation*}のように矢印をセクシーに(?)曲げてもよいとします。

余談 この性質は圏の定義でいうところの「恒等射の存在」に相当します。対象$A$の恒等射を$1_A$とすると、任意の射$A\overset{f}{\to}B$に対して$f\circ 1_A=1_B\circ f=f$が成り立ちます。「$\circ$」は射の合成のことで、このあとすぐ登場します。

推移律:矢印は合成できる

例えば、$3$は$6$の約数であり、$6$は$24$の約数です。このとき、$3$は$24$の約数になります。

一般に$a$は$b$の約数かつ$b$は$c$の約数ならば、$a$は$c$の約数であることが言えます。これは、整除関係の推移律と呼ばれる性質です。

この推移律を矢印で表現してみます。$a$は$b$の約数、$b$は$c$の約数のとき、
\[
a\longrightarrow b \longrightarrow c
\]のようにつながった矢印ができます。このとき、$a$は$c$の約数であるから、矢印を合成して1本の矢印
\[
a\longrightarrow c
\]と見てもよいことになります。これが推移律です。

また、反射律・推移律をみたす関係を前順序と言います。

余談 推移律は圏でいうところの「(結合法則をみたすような)射の合成」に相当します。また、前順序の構造をもつ数学的対象は(やせた)圏とみなすことができます。

反対称律:矢印が往復したらイコール

$a$は$b$の約数で、さらに$b$は$a$の約数とします。このとき、$a=b$が成り立ちます*1。証明は難しくないので割愛しますが、この法則を矢印で表すと
\begin{equation*}\xymatrix{
a \ar@<0.5ex>[r] & b \ar@<0.5ex>[l]
}\end{equation*}のように、矢印が往復したら$a=b$であることが言えるというものになります。

また、反射律・反対称律・推移律をみたす関係を順序関係と言います。つまり、整除関係は順序関係です。

余談 2つの対象$A$,$B$の間に、合成して恒等射になるような射が存在するとき、$A$と$B$は同型と言います。整除関係の圏では対象間の射が多くても1本のため、射$a\rightarrow b \rightarrow a$および射$b\rightarrow a \rightarrow b$は半ば強制的に恒等射に等しくなります。このとき、$a$と$b$は同型どころか全く同じ対象であることまで言えてしまいます。

同じ数を掛けても矢印は引ける

$3$は$6$の約数なので
\begin{equation*}\xymatrix{
3 \ar[r]^{\times2} & 6
}\end{equation*}と表せます。ここで、$3$と$6$をそれぞれ4倍してみます。
\begin{equation*}\xymatrix{
3 \ar[r]^{\times2} \ar[d]_{\times4} & 6 \ar[d]^{\times4}\\
12 & 24
}\end{equation*}このとき、$12$は$24$の約数なので
\begin{equation*}\xymatrix{
3 \ar[r]^{\times2} \ar[d]_{\times4} & 6 \ar[d]^{\times4}\\
12 \ar[r]_{\times2} & 24
}\end{equation*}となります。このように、整除関係にある2数に同じ数を掛けても、整除関係は保たれるという性質があります。

余談 縦方向の$\times4$の矢印の集まりは関手と思うことができます。あるいは「恒等関手」から「$\times4$してできる関手」への自然変換と思うこともできます。


公約数と最大公約数

次に公約数や最大公約数といった概念を矢印で表していきます。

公約数を矢印で表す

$12$と$30$の公約数の一つとして$2$があります。これは
\[
\xymatrix{
& 12\\
2\ar[ur]^{\times6}\ar[dr]_{\times15} &\\
& 30}
\]と表せますね。

つまり、公約数は「2つの数が終点になるように矢印が引ける数」と言い換えることができます。

公約数→最大公約数

$12$と$30$の公約数は$1$,$2$,$3$,$6$の4つで、最大公約数は$6$です。
このとき、$6$はすべての公約数たちとどのような関係にあるでしょうか?

もちろん、最大公約数が他の公約数よりも大きいという関係もありますが、今は整除関係に関連する性質に注目したいです。

すると、$1$,$2$,$3$,$6$はすべて$6$の約数であることに気づきます。一般に、任意の公約数は最大公約数の約数となることが知られています。

これを矢印を使って表現します。
以下のように、$12$と$30$の公約数である$2$と、最大公約数の$6$が関係する矢印を用意します。
\[
\xymatrix{
& & 12\\
2\ar[urr]^{\times6}\ar[drr]_{\times15} & 6\ar[ur]_{\times2}\ar[dr]^{\times5} &\\
& & 30}
\]


すると、$2$は$6$の約数なので、次のように矢印が“生えて”きます。
\[
\xymatrix{
& & 12\\
2\ar@{.>}[r]|{\times3}\ar[urr]^{\times6}\ar[drr]_{\times15} & 6\ar[ur]_{\times2}\ar[dr]^{\times5} &\\
& & 30}
\]ちなみに、この生えてきた矢印は
\begin{align*}
(2\overset{\times6}{\longrightarrow} 12) &= (2\overset{\times3}{\longrightarrow} 6\overset{\times2}{\longrightarrow} 12)\\
(2\overset{\times15}{\longrightarrow} 30) &= (2\overset{\times3}{\longrightarrow} 6\overset{\times5}{\longrightarrow} 30)
\end{align*}という性質も備わっています(順序関係を矢印で表した場合、この性質は半ば強制的に成り立ちます)。


楽しくなってきたので、別の公約数でもやってみましょう。


$12$と$30$の公約数である$3$と、最大公約数の$6$が関係する図式を用意します。
\[
\xymatrix{
& & 12\\
3\ar[urr]^{\times4}\ar[drr]_{\times10} & 6\ar[ur]_{\times2}\ar[dr]^{\times5} &\\
& & 30}
\]すると、$3$は$6$の約数なので、以下のように矢印が生えてきます。
\[
\xymatrix{
& & 12\\
3\ar@{.>}[r]|{\times2}\ar[urr]^{\times4}\ar[drr]_{\times10} & 6\ar[ur]_{\times2}\ar[dr]^{\times5} &\\
& & 30}
\]この生えてきた矢印についても
\begin{align*}
(3\overset{\times4}{\longrightarrow} 12) &= (3\overset{\times2}{\longrightarrow} 6\overset{\times2}{\longrightarrow} 12)\\
(3\overset{\times10}{\longrightarrow} 30) &= (3\overset{\times2}{\longrightarrow} 6\overset{\times5}{\longrightarrow} 30)
\end{align*}という性質を備えています。

今回は$12$と$30$の公約数として$2$と$3$を扱いましたが、$1$でも$6$でも同じように矢印が生えることが分かります。

ということで、「任意の公約数は最大公約数の約数」は「公約数から最大公約数へ矢印が引ける」と言い換えることができました。

最大公約数を図式で考えるの、面白いですね~

余談 最大公約数は、順序における最大下界、圏における直積という概念に相当します。なお、直積と考える場合、生えてくる射は一意である必要がありますが、整除関係の圏では射が多くても1つのため、自動的に成り立ちます。


公倍数と最小公倍数

同様に、公倍数と最小公倍数について考えていきます。

公倍数を矢印で表す

$12$と$30$の公倍数の一つとして$120$があります。これは
\[
\xymatrix{
12\ar[dr]^{\times10} & \\
&120\\
30\ar[ur]_{\times4} & }
\]と表せます。
つまり、公倍数は「2つの数が始点になるように矢印が引ける数」と言い換えることができます。

公約数と公倍数の概念が互いに逆になっているのが目に見えて分かりますね!

最小公倍数→公倍数

$12$と$30$の公倍数は$60$,$120$,$180$,$240$,$\cdots$と続き、$60$が最小公倍数です。

ここで、$12$と$30$の公倍数はすべて$60$の倍数になります。より一般に、任意の公倍数は最小公倍数の倍数となることが知られています。この性質を矢印で表します。

$12$と$30$の公倍数である$120$と最小公倍数の$60$に関係する矢印を用意すると、次のようになります:
\[
\xymatrix{
12\ar[dr]_{\times5}\ar[drr]^{\times10} & &\\
&60&120\\
30\ar[ur]^{\times2}\ar[urr]_{\times4} & &}
\]すると、$120$は$60$の倍数なので、次のように矢印が“生えます”:
\[
\xymatrix{
12\ar[dr]_{\times5}\ar[drr]^{\times10} & &\\
&60\ar@{.>}[r]|(0.4){\times2}&120\\
30\ar[ur]^{\times2}\ar[urr]_{\times4} & &}
\]この生えてきた矢印についても
\begin{align*}
(12\overset{\times10}{\longrightarrow} 120) &= (12\overset{\times5}{\longrightarrow} 60\overset{\times2}{\longrightarrow} 120)\\
(30\overset{\times4}{\longrightarrow} 120) &= (30\overset{\times2}{\longrightarrow} 60\overset{\times2}{\longrightarrow} 120)
\end{align*}という性質があります。

$120$以外の公倍数を選んでも、同じような矢印が生えることが分かります。ということで、「任意の公倍数は最小公倍数の倍数」は「最小公倍数から公倍数へ矢印が引ける」と言い換えることができました。

余談 最小公倍数は、順序における最小上界、圏における直和という概念に相当します。直積と同様に、生えてくる射は一意である必要があります。

ここまででも十分楽しかったのですが、この記事の目標は分配法則の証明です。以上のことを踏まえて、証明を考えていきましょう!

定理の証明

最大公約数と最小公倍数の分配法則を再掲します。

定理
$a\land b$を$a$と$b$の最大公約数,$a\vee b$を$a$と$b$の最小公倍数とする.このとき,次の分配法則が成り立つ.
\begin{align}
a\vee (b \land c) &= (a\vee b) \land (a\vee c)\tag{1}\\
a\land (b \vee c) &= (a\land b) \vee (a\land c)\tag{2}
\end{align}

2つの式は同値であることの証明

2つの式がありますが、実はこの2つの式は同値であることを示します。

この記事では「\eqref{1} ならば \eqref{2}」を証明します(逆は記号を反転するだけで全く同様)。つまり、最小公倍数の計算を分配できることを仮定して、 \eqref{2}を証明します。
証明
始めに、
\begin{align}
(a\land b)\vee a&=a,\label{3}\\
a \land (a\vee c)&=a\label{4}
\end{align}となることを確認する。\eqref{3}は$1a=k(a\land b)$と表せるのでよい。\eqref{4}は$a\vee c$は$a$の倍数なので$a \land (a\vee c)=a\land na =a(1\land n) = a$となる。

したがって

\begin{align*}
(\eqref{2}\text{の右辺}) & = (a\land b) \vee (a\land c) && \\
& = ( (a\land b)\vee a) \land ( (a\land b)\vee c) && (a\land b\text{を分配} ) \\
& = ( (a\land b)\vee a) \land ( (a\vee c)\land (b\vee c) ) && (c\text{を分配} ) \\
& = a \land ( (a\vee c)\land (b\vee c) ) && (\eqref{3}\text{を利用})\\
& = (a \land (a\vee c))\land (b\vee c) && (\land\text{の結合 法則}) \\
& = a \land (b\vee c) && (\eqref{4}\text{を利用})\\
& = (\eqref{2}\text{の左辺})
\end{align*}

が成り立つ。■

ここで注意ですが、途中でに関する分配法則
\[
ln\land lm =l(n\land m)
\]を用いました。これは今証明したいものとは異なるので、循環論法になっていません。

(1)の証明

2つの式が同値だと分かったため、どちらか一方を証明すれば大丈夫です。どちらも同じように示せますが、\eqref{1}の方を証明していきたいと思います。

\eqref{1}を示すためには
\begin{equation*}\xymatrix{
a\vee (b \land c) \ar@<0.5ex>[r] & (a\vee b) \land (a\vee c) \ar@<0.5ex>[l]
}\end{equation*}という2本の矢印を引くことができることを示せばよいですね。
ということで、まずは$a\vee (b \land c) \to (a\vee b) \land (a\vee c)$の矢印を引けること(これがメインの証明!)、次に逆向きの矢印が引けること(こっち側も面白い)を示していきます。

1本目の矢印

まず、\eqref{1}に出てくる数の整除関係を整理します。

\[
\xymatrix@C=20pt@R=3pt{
a\ar[dr] & & & a\vee b\\&a\vee(b\land c) & (a\vee b)\land(a\vee c)\ar[ur]\ar[dr] &\\
b\land c\ar[ur] & & &a\vee c}
\]

左の図だけ補足しておくと、$a\vee(b\land c)$は$a$と$b \land c$の(最小)公倍数なので、$a$と$b \land c$が始点になるように矢印を引きました。右も同様です。

そして、$b$と$c$の最大公約数は$b$の約数であり、$b$と$c$の最小公倍数は$b$の倍数なので、以下のように矢印を書き加えることができます:

\[
\xymatrix@C=20pt@R=3pt{
a\ar[dr] \ar@/^15pt/[rrr]+(0.5,3) & & & a\vee b\\&a\vee(b\land c) & (a\vee b)\land(a\vee c)\ar[ur]\ar[dr] &\\
b\land c\ar[ur]\ar[r] & b \ar@{}(33,-17);[uurr]+(-10,0)**\crv{[r]+(-27,0)&[ur]+(-22,0)&[uur]+(-17,0)}?>*\dir{>}&&a\vee c}
\]

このとき、左上の$a\vee b$に向かってくる2本の矢印の根っこは「$a$」と「$b \land c$」になっています。つまり、$a\vee b$は「$a$」と「$b \land c$」の公倍数になっているわけです。

ということは、$a\vee(b\land c)$の性質により、次のように矢印が生えてきます:

\[
\xymatrix@C=20pt@R=3pt{
a\ar[dr] \ar@/^15pt/[rrr]+(0.5,3) & & & a\vee b\\&a\vee(b\land c)\ar@{.>}@/^15pt/[urr] & (a\vee b)\land(a\vee c)\ar[ur]\ar[dr] &\\
b\land c\ar[ur]\ar[r]& b \ar@{}(33,-17);[uurr]+(-10,0)**\crv{[r]+(-27,0)&[ur]+(-22,0)&[uur]+(-17,0)}?>*\dir{>}&&a\vee c}
\]

今度は、以下のように矢印を書き加えます:

\[
\xymatrix@C=20pt@R=3pt{
a\ar[dr] \ar@/^15pt/[rrr]+(0.5,3) \ar@{}(5,0);[rrrdd]+(-10,0)**\crv{[rr]+(-27,0)&[rrd]+(-22,0)&[rrdd]+(-17,0)}?>*\dir{>} & & & a\vee b\\&a\vee(b\land c)\ar@{.>}@/^15pt/[urr] & (a\vee b)\land(a\vee c)\ar[ur]\ar[dr] &\\
b\land c\ar[ur]\ar[r]\ar[dr]& b \ar@{}(33,-17);[uurr]+(-10,0)**\crv{[r]+(-27,0)&[ur]+(-22,0)&[uur]+(-17,0)}?>*\dir{>}&&a\vee c\\
&c\ar@/_10pt/[rru]+(0.5,-3)&&}
\]

左下の$a\vee c$に向かってくる矢印の根っこは、やはり「$a$」と「$b \land c$」です。つまり、$a\vee c$は「$a$」と「$b \land c」$の公倍数になっているので、次のように矢印が生えます:

\[
\xymatrix@C=20pt@R=3pt{
a\ar[dr] \ar@/^15pt/[rrr]+(0.5,3) \ar@{}(5,0);[rrrdd]+(-10,0)**\crv{[rr]+(-27,0)&[rrd]+(-22,0)&[rrdd]+(-17,0)}?>*\dir{>} & & & a\vee b\\&a\vee(b\land c)\ar@{.>}@/^15pt/[urr]\ar@{.>}@/^-15pt/[drr] & (a\vee b)\land(a\vee c)\ar[ur]\ar[dr] &\\
b\land c\ar[ur]\ar[r]\ar[dr]& b \ar@{}(33,-17);[uurr]+(-10,0)**\crv{[r]+(-27,0)&[ur]+(-22,0)&[uur]+(-17,0)}?>*\dir{>}&&a\vee c\\
&c\ar@/_10pt/[rru]+(0.5,-3)&&}
\]

するとどうでしょう、$a\vee(b\land c)$は「$a\vee b$」と「$a\vee c$」に向かって矢印が引けているので、「$a\vee b$」と「$a\vee c$」の公約数ですね?

ということは、$(a\vee b)\land(a\vee c)$の性質により、次のような矢印が生えます:

\[
\xymatrix@C=20pt@R=3pt{
a\ar[dr] \ar@/^15pt/[rrr]+(0.5,3) \ar@{}(5,0);[rrrdd]+(-10,0)**\crv{[rr]+(-27,0)&[rrd]+(-22,0)&[rrdd]+(-17,0)}?>*\dir{>} & & & a\vee b\\&a\vee(b\land c)\ar@{.>}@/^15pt/[urr]\ar@{.>}@/^-15pt/[drr]\ar@{-->}@/^10pt/[r] & (a\vee b)\land(a\vee c)\ar[ur]\ar[dr] &\\
b\land c\ar[ur]\ar[r]\ar[dr]& b \ar@{}(33,-17);[uurr]+(-10,0)**\crv{[r]+(-27,0)&[ur]+(-22,0)&[uur]+(-17,0)}?>*\dir{>}&&a\vee c\\
&c\ar@/_10pt/[rru]+(0.5,-3)&&}
\]

この生やした矢印は、まさに求めていた矢印になっています!

2本目の矢印

続いて、今求めた矢印の逆向きの矢印が引けることを示していきます。
まず、
\begin{align*}
b&=b'(b\land c),\\
c&=c'(b\land c)
\end{align*}とおきます($b'$と$c'$は互いに素、つまり$b'\land c' = 1$)。

次に、公倍数の定義より、このような矢印が書けます:
\begin{equation*}\xymatrix{
a\ar[rd] &\\
b\land c \ar[r] & a\vee(b\land c)
}\end{equation*}
ここで、「$b\land c$」と「$a\vee(b\land c)」$をそれぞれ$b'$倍しても整除関係を保つので、
\begin{equation*}\xymatrix{
a\ar[rd] &\\
b\land c \ar[r] \ar[d]_{\times b'} & a\vee(b\land c) \ar[d]^{\times b'}\\
b \ar[r] & b'(a\vee(b\land c) )
}\end{equation*}となります。すると、$N:=b'(a\vee(b\land c) )$は$a$と$b$の公倍数だと分かります。

同様に、「$b\land c$」と「$a\vee(b\land c)」$をそれぞれ$c'$倍すると次のような図式が書けます:
\begin{equation*}\xymatrix{
a\ar[rd] &\\
b\land c \ar[r] \ar[d]_{\times c'} & a\vee(b\land c) \ar[d]^{\times c'}\\
c \ar[r] & c'(a\vee(b\land c) )
}\end{equation*}よって、$M:=c'(a\vee(b\land c) )$は$a$と$c$の公倍数だと分かります。

$a\vee b$および$a\vee c$の性質により、このような図式が書けることになります:
\[
\xymatrix{
& a\vee b\ar@{.>}[r] & N\\
(a\vee b)\land(a\vee c)\ar[ur]\ar[dr] & N\land M\ar[ur]\ar[dr] \\
& a\vee c\ar@{.>}[r] & M}
\]よく見ると、$(a\vee b)\land(a\vee c)$は$N$と$M $の公約数になっているので、$N\land M $の性質により
\[
\xymatrix{
& a\vee b\ar@{.>}[r] & N\\
(a\vee b)\land(a\vee c)\ar[ur]\ar[dr]\ar@{-->}[r] & N\land M\ar[ur]\ar[dr] \\
& a\vee c\ar@{.>}[r] & M}
\]となります。

ここで、積に関する分配法則により
\begin{align*}
N\land M &= (b'(a\vee(b\land c) ))\land(c'(a\vee(b\land c) ))\\
&= (a\vee(b\land c))(b'\land c')\\
&= a\vee(b\land c)
\end{align*}となるので、
\[
(a\vee b)\land(a\vee c)\longrightarrow a\vee(b\land c)
\]という矢印が引けることが証明できました。■

まとめ

最小公倍数と最大公約数に関する分配法則を図式で証明してみました。整除関係が視覚的に分かりやすかったですね!

できることなら、2本目の矢印の証明は一つの図式に矢印を加えるだけで完成させたかったですが、矢印が複雑に絡み合って「ヤバイ図式屋さん」になりそうだったのでやめました。


今日はこの辺で!
「射っ!射っ!射射射射っ!えびばーでぃ!」


thank Q for rEaDing.φ(・▽・ )

参考文献など

www.mu.c.titech.ac.jp

paperzz.com



日曜数学 Advent Calendar 2023、次回はapuさんで「ドミノで繋がる数学の話」です!

*1:整数の範囲で考えると、符号の違いが生じる可能性があります。