素因数分解を利用して最大公約数を求める ~ 数学について考えてみる

2022年4月18日

PLUMBAGO

「 $270,300,360$ の最大公約数を求めよ。」

　公約数はある整数 $A,B$ それぞれの約数の中で共通する数のことで、その中で最も大きい公約数のことを最大公約数と呼びます。
最大公約数は素因数分解を利用して求めることができます。

　それぞれの数を素因数分解すると

\begin{aligned} 270 & = 2 \times 3^{3} \times 5 \\ 300 & = 2^{2} \times 3 \times 5^{2} \\ 360 & = 2^{3} \times 3^{2} \times 5 \end{aligned}

$\begin{align*}270&=2×3^3×5\\[1em]300&=2^2×3×5^2\\[1em]360&=2^3×3^2×5\end{align*}$

となります。
約数はその数の素因数からいくつか取り出して掛け合わせてつくるので、公約数は共通して取り出せる素因数を掛け合わせてできる約数、最大公約数は共通して取り出せる素因数を最も多く掛け合わせてできる約数と考えることができます。

したがって、

270, 300, 360

$270,300,360$ で共通して取り出せる素因数は、

2

$2$ が1個まで、

3

$3$ が1個まで、

5

$5$ が1個までなので、最大公約数は

2 \times 3 \times 5 = 30

$2×3×5=30$

となります。

(2023/11)誤りがあったので修正しました。

数学について考えてみる