素因数分解を用いて GCD と LCM を計算します

素因数分解を用いて GCD と LCM を計算します

 素因数分解を用いると最大公約数 (GCD) と最小公倍数 (LCM) を簡単に計算することができます。たとえば 126 と 600 をそれぞれ素因数分解すると
 
\[\begin{align*}126=2^1\times 3^2\times5^0\times 7^1\\[6pt]
600=2^3\times 3^1\times 5^2\times 7^0\end{align*}\]
となります。比較しやすくするために、指数部分が 0 や 1 である場合も書いてあります。最大公約数は各因数からベキ指数の小さいほう(正確に言うと大きくないほう)を選んで掛け合わせます:
 
\[(126,\:600)=2^1\times 3^1\times 5^0\times 7^0=6\]
 最小公倍数はベキ指数の大きいほう(正確に言うと小さくないほう)を選んで
 
\[\{126,\:600\}=2^3\times 3^2\times 5^2\times 7^1=12600\]
と計算できます。一般には次のように計算します。

[定理 B7] 2 つの正整数 $a,\:b$ を素因数分解して
\[\begin{align*}a=p_1^{u_1}\,p_2^{u_2}\,\cdots\,p_i^{u_i}\,\cdots\\[6pt]
b=p_1^{v_1}\,p_2^{v_2}\,\cdots\,p_i^{v_i}\,\cdots
\end{align*}\]のように表せたとします。ただし $u_i,\:v_i$ は 0 または正整数です。このとき
\[\begin{align*}\mathrm{min}(u_i,\:v_i)=s_i\\[6pt]
\mathrm{max}(u_i,\:v_i)=t_i\end{align*}\]とおくと、最大公約数と最小公倍数はそれぞれ
\[\begin{align*}(a,\:b)=p_1^{s_1}\,p_2^{s_2}\,\cdots\,p_i^{s_i}\,\cdots\\[6pt]
\{a,\:b\}=p_1^{t_1}\,p_2^{t_2}\,\cdots\,p_i^{t_i}\,\cdots\end{align*}\]と計算することができます。

 ここで $\mathrm{min}(a,\:b)$ は $a,\:b$ のうち大きくないほう、$\mathrm{max}(a,\:b)$ は$a,\:b$ のうち小さくないほうを表します。詳しくは 小さくない数と大きくない数 の記事を参照してください。

 ≫ 素因数分解による無理数性の証明 ≫ 初等整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。