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つの整数だとしても骨が折れます。
そこで、最小公倍数と最大公約数の関係を使い、ユークリッドの互除法でもって計算するのです。
ユークリッドの互除法は誠に有用です。

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

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

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