3つ以上の整数の最小公倍数はどう求める？

本記事の内容

本記事は「3つ以上の整数の最小公倍数はどう求めるのか？」について解説する記事です。

本記事を読むに当たり、最小公倍数について知っている必要があるため、以下の記事も合わせて御覧ください。

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

...

for-spring.com

2023.02.22

いきなりですが、問題です。

難易度としては、大したことではありません。
解く事自体は問題ないでしょう。

解答は、$795441$です。
つまり、${\rm lcm}(123,223,29)=795441$です。

筆者は最初愚直に解いてみましたが、断念して計算サイトを使いました。

愚直に計算する場合、大きい数の最大公約数は約数を見つけていくことが大変ですが、大きい数の最小公倍数は桁がどんどん大きくなるため、単純な計算でも骨が折れるのです。

高々3桁の3つの整数の最小公倍数だというのに、結果は「エライコッチャ」という感じです。
大きい数の最大公約数はユークリッドの互除法で求めるのでした(勿論愚直に計算してもOKです)。
では、最小公倍数は？というのが今回の内容になります。

結論：${\rm lcm}(a,b,c)={\rm lcm}\left({\rm lcm}(a,b),c \right)$を使う。

結論としては、${\rm lcm}(a,b,c)={\rm lcm}\left({\rm lcm}(a,b),c \right)$を使います(後で証明します)。

これはどういうことかというと、3つの整数の最小公倍数を求めるとき、それらの整数の一部分をその最小公倍数で置き換えてOKということです。

例えば、$a,b,c$の最小公倍数は、$a,b$の最小公倍数$m$と$c$との最小公倍数と等しいのです。

これは一般の個数でも成り立ちます。

定理1.の証明

$l={\rm lcm}(a_1,a_2,a_3,\cdots,a_n)$、すなわち$a_1,a_2,a_3,\cdots,a_n$の最小公倍数を$l$とします。
また、$m={\rm lcm}(a_1,a_2)$とし、$l^\prime={\rm lcm}\left(m,a_3,\cdots,a_n\right)$とします。
まとめると、
$$\begin{eqnarray} l&=&{\rm lcm}(a_1,a_2,a_3,\cdots,a_n)\\ m&=&{\rm lcm}(a_1,a_2)\\ l^\prime&=&{\rm lcm}\left(m,a_3,\cdots,a_n\right)\\ &=&{\rm lcm}\left({\rm lcm}(a_1,a_2),a_3,\cdots,a_n\right) \end{eqnarray}$$
とします。
このとき、示したいのは$l=l^\prime$です。

さて、$l$は$a_1$と$a_2$の最小公倍数ですから、$l$は$a_1$と$a_2$の公倍数です。
ここで、次の事実を使います。

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

$l$は$a_1$と$a_2$の公倍数である為、定理2.から、$l$は$m={\rm lcm}(a_1,a_2)$の倍数です。

$l$はもともと$l={\rm lcm}(a_1,a_2,a_3,\cdots,a_n)$だったわけですので、$l$は$a_3,\cdots,a_n$の公倍数でもあります。
故に、$l$は$m,a_3,\cdots,a_n$の公倍数ということになります。
$l^\prime$は$m,a_3,\cdots,a_n$の最小公倍数ですので、$l$は$l^\prime$の倍数です。

また、$l^\prime$に注目してみると、$l^\prime={\rm lcm}\left(m,a_3,\cdots,a_n\right)$だったわけですので、$l^\prime$は$m$の倍数、すなわち$a_1$と$a_2$の倍数です。
故に、$l^\prime$は$a_1,a_2,a_3,\cdots,a_n$の公倍数です。

さて、$l={\rm lcm}(a_1,a_2,a_3,\cdots,a_n)$、すなわち$a_1,a_2,a_3,\cdots,a_n$の最小公倍数ですので、$l^\prime$は$l$の倍数です。

以上のことから、$l$は$l^\prime$の倍数であり、同時に$l^\prime$は$l$の倍数でもあるため、$l=l^\prime$です。
実際、$k,k^\prime\in\mathbb{N}$を用いて$l=kl^\prime$、$l^\prime=k^\prime l$と書いたとします。
このとき、$l=kk^\prime l$です。
$l$は最小公倍数ですので$l\neq0$ですから、$kk^\prime=1$となります。
$k,k^\prime\in\mathbb{N}$ですから、$k=k^\prime=1$となって、$l=l^\prime$です。

定理1.の証明終わり

${\rm lcm}(a_1,a_2)$に対して、$a_1$と$a_2$が大きい数だったら元も子もないのでは？

定理1.から$a_1,a_2,a_3,\cdots,a_n\in\mathbb{Z}$に対して、
$${\rm lcm}(a_1,a_2,a_3,\cdots,a_n)={\rm lcm}\left( {\rm lcm}(a_1,a_2),a_3,\cdots,a_n\right)$$
が成り立つとは言ったものの、そもそも$a_1$と$a_2$が大きい数であれば、${\rm lcm}(a_1,a_2)$を求めることすら苦労します。

しかし、その場合は以前証明した次の事実を使います。

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

定理3.から、2つの整数の最小公倍数は最大公約数から求めることができます。
そして、その2つの整数の最大公約数はユークリッドの互除法から求めることができるのです。

実際に解いてみる。

最初に提示して問題を解いてみます。

定理1.から${\rm lcm}(123,223,29)={\rm lcm}\left( {\rm lcm}(123,223),29\right)$です。
そこで、${\rm lcm}(123,223)$を求めます。
そのために、定理3.を使います。

定理3.を使うため、まずは$\gcd(123,223)$をユークリッドの互除法で求めます。
$$\begin{eqnarray} 223&=&1\times123+100\\ 123&=&=1\times100+23\\ 100&=&4\times23+8\\ 23&=&2\times8+7\\ 8&=&1\times7+1\\ 7&=&7\times1+0 \end{eqnarray}$$
故に、$\gcd(123,223)=1$となります。

今、$123\times223=27429$ですので、定理3.から
$$27429=1\times{\rm lcm}(123,223)$$
が成り立つため、${\rm lcm}(123,223)=27429$です。

したがって、${\rm lcm}(27429,29)$を求めれば良いことになります。
これも定理3.を使うため、$\gcd(27429,29)$をユークリッドの互除法で計算します。
$$\begin{eqnarray} 27429&=&945\times29+24\\ 29&=&1\times24+5\\ 5&=&1\times4+1\\ 4&=&4\times1+0 \end{eqnarray}$$
故に、$\gcd(27429,29)=1$です。

今、$27429\times29=795441$ですので、定理3.から
$$795441=1\times{\rm lcm}(27429,29)$$
が成り立つため、${\rm lcm}(123,223)=795441$です。

もし、${\rm lcm}(123,223,29)$を愚直に計算しようとすると、$795441$が出てくるまで倍数の計算をしなければなりません。
そして、$795441$が出現するまで計算したとしても、それが最小公倍数であるかはわからないため、更にその先の倍数を求める必要もあります。
そうすると骨が折れるどころの騒ぎではありません。

しかし、今回証明した$a,b,c\in\mathbb{Z}$に対して${\rm lcm}(a,b,c)={\rm lcm}\left( {\rm lcm}(a,b),c\right)$とユークリッドの互除法を駆使することで確実に計算が容易になります。

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

本シリーズの最初に述べましたが、初等整数論は愚直に計算すれば解けるけれども、解法をすこし工夫することで劇的に簡単に解ける問題が多い、ということが面白い点だと思います。

筆者の場合極稀に「今日、冴えてるわ」という日があります。
あくまで極稀にですがね。
皆様は「今日、冴えてるわ」と思う日はどんな問題を解いた日ですか？
ぜひコメントで教えて下さい！

結

今回は大きい数の最小公倍数を求める手法を解説しました。
本質的には3以上の整数の最小公倍数は、2つの最小公倍数と残り1つの整数との最小公倍数と等しいということでした。
しかし、大きい数の最小公倍数は2つの整数だとしても骨が折れます。
そこで、最小公倍数と最大公約数の関係を使い、ユークリッドの互除法でもって計算するのです。
ユークリッドの互除法は誠に有用です。

次回は一次不定方程式を導入します。

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

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