アルゴリズム論特論（塩田）第3回 (2) 素因数分解と $\gcd$, $\mbox{lcm}$
素因数分解と $\gcd$, $\mbox{lcm}$
Th.1 ふたつの自然数 $a$, $b$ の素因数分解を
$a=\displaystyle{\prod_{p} p^{e_p}},\qquad$
$b=\displaystyle{\prod_{p} p^{f_p}}$
とすると、
$\gcd(a,b)=\displaystyle{\prod_{p} p^{\min(e_p,f_p)}},\quad$
$\mbox{lcm}(a,b)=\displaystyle{\prod_{p} p^{\max(e_p,f_p)}}$
Ex.2 総積記号 $\prod_p$ は全ての素数 $p$ についての積を表す記号で、
$a = 630 = 2^1 \times 3^2 \times 5^1 \times 7^1,$
$b = 168 = 2^3 \times 3^1 \times 5^0 \times 7^1\,$
のときは、$e_p$, $f_p$ は
$e_2 = 1$, $e_3 = 2$, $e_5 = 1$, $e_7 = 1$, 他の $e_p = 0,$
$f_2 = 3$, $f_3 = 1$, $f_5 = 0$, $f_7 = 1$, 他の $f_p = 0\,$
となります。べき指数の小さい方を掛け合わせたのが $\gcd$, 大きい方を掛け合わせたのが $\mbox{lcm}$ になります：
$\gcd(630,168) = 2^1 \times 3^1 \times 5^0 \times 7^1 = 42,\phantom{0}$
$\mbox{lcm}(630,168) = 2^3 \times 3^2 \times 5^1 \times 7^1 = 2520$
数字ならできる、と言っても、
記号で書かないとプログラミングできませんので、
記号の使い方を覚えてください。
Cor.3 $\gcd(a,b) \times \mbox{lcm}(a,b)=a \times b.$
証明
$\dps{
\min(x,y)+\max(x,y) =
\left\{
\begin{array}{ll}
x + y, &\mbox{ if }\ x \leqq y \\
y + x = x + y, &\mbox{ if }\ x \gt y \\
\end{array}
\right.
}$
ゆえ、いずれの場合も
$\min(x,y)+\max(x,y) = x + y$
が成り立つ。
従って
左辺の $p$ のべき指数 $= \min(e_p,f_p)+\max(e_p,f_p)$
$\phantom{00000000000000000}= e_p + f_p =$ 右辺の $p$ のべき指数
となる。(証明終)
Cor.4 $\mbox{lcm}(a,b)$ の計算時間 ≒ $\gcd(a,b)$ の計算時間.