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

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

【広告】

最小公倍数と素因数分解

例題
$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になっていることが確認できるでしょう。

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

おわりに

ここでは、最小公倍数からもとの整数を求める問題を考えました。素因数分解によって最小公倍数がどのように書けるかを理解していれば、もとの整数を求めるときにも同じ考えを応用することができます。