【標準】最小公倍数と素因数分解（最小公倍数からもとの整数を求める）

🕒 2018/07/24 🔄 2023/05/01

ここでは、最小公倍数から、もとの整数が何だったかを求める問題を考えます。素因数分解を利用して考えていきます。

📘 目次

最小公倍数と素因数分解

例題

$a$ と $18$ との最小公倍数が $180$ となるような、正の整数 $a$ をすべて求めなさい。

最小公倍数が $180$ ということは、 $a$ は $180$ 以下だということがわかります。でも、一つずつ調べていくのは無理ですね。もっと候補を減らして考えたいところです。

最小公倍数は倍数でもあることから、 $180$ は $a$ の倍数であり、 $a$ は $180$ の約数でもあるわけですね。このような「約数」を考える際には、素因数分解を使うと扱いやすくなることがあるのでした（参考：【基本】素因数分解と約数の個数）。ここでも、素因数分解を使って考えてみましょう。

$180$ を素因数分解すると\[ 180=2^2\times 3^2\times 5 \]となります。よって、 $a$ は $2,3,5$ 以外の素因数をもたないことはわかります。これだけでもだいぶ絞れましたが、まだ多いですね。

$18$ の方も素因数分解をしてみます。\[ 18=2\times 3^2 \]となります。これには、素因数 $5$ が含まれていないので、 $a$ は必ず素因数 $5$ をもたないといけない、ということがわかります。このように、素因数分解をすれば、素因数に関する情報が得られるケースがあります。

さて、そうなると、 $a$ の各素因数 $2,3,5$ について、指数がどうなるかを考えなくてはいけません。これが決まれば、 $a$ は決まります。最小公倍数と素因数分解については、【基本】最大公約数と最小公倍数#最小公倍数と素因数分解で見ましたね。2つの整数の最小公倍数を求めるには、素因数分解をし、各素因数について、指数が大きい方を選んでいけばいいのでした。

$a$ と $18=2\times 3^2$ の最小公倍数が $180=2^2\times 3^2\times 5$ であることから、 $a$ の各素因数の指数がどうなるかを考えてみましょう。

まず、素因数 $2$ については、 $18$ の方は指数が $1$ で、 $180$ の方は指数が $2$ です。ということは、 $a$ は、 $2^2$ を含んでいないといけないことがわかります。指数が $1$ 以下なら、最小公倍数の $2$ の指数も $1$ 以下になるし、 $3$ 以上なら、最小公倍数の $2$ の指数も $3$ 以上になってしまいます。よって、 $a$ の素因数 $2$ の指数は $2$ しかありえません。

素因数 $3$ については、 $18$, $180$ ともに、指数が $2$ です。なので、 $a$ については、指数は $2$ 以下ならいいことがわかります。 $2$ である必要はないことに注意しましょう。 $3^0,3^1,3^2$ の3通りがありえます。 $0$ がありえることにも注意しましょう。

最後に、素因数 $5$ については、 $18$ には含まれていません。 $180$ の指数は $1$ です。なので、 $a$ は、 $5$ の指数が $1$ になるということがわかります。

以上から、 $a$ を素因数分解したときには、含まれる素因数は $2,3,5$ だけで、 $2$ の指数は $2$ のみ、 $3$ の指数は $0,1,2$ の3通り、 $5$ の指数は $1$ のみであることがわかります。
\begin{eqnarray} 2^2\times 3^0\times 5^1 &=& 20 \\[5pt] 2^2\times 3^1\times 5^1 &=& 60 \\[5pt] 2^2\times 3^2\times 5^1 &=& 180 \\[5pt] \end{eqnarray}となるので、 $a=20,60,180$ となることがわかります。実際に計算してみると、最小公倍数が180になっていることが確認できるでしょう。

慣れてくれば、もっとサクッと出すことができるでしょう。素因数分解をして、各素因数について、指数の大きい方を選べば最小公倍数になる、ということから、各素因数の指数を簡単に絞ることができます。