アルゴリズム論特論（塩田）第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)}}$
$\require{color}$
Ex.2 総積記号 $\displaystyle{\prod_p}$ は全ての素数 $p$ についての積を表す記号で、
$a = 630 = 2^\textcolor{red}{1} \times 3^\textcolor{blue}{2} \times 5^\textcolor{green}{1} \times 7^\textcolor{#8B4513}{1},$
$b = 168 = 2^\textcolor{fuchsia}{3} \times 3^\textcolor{purple}{1} \times 5^\textcolor{teal}{0} \times 7^\textcolor{#FF8C00}{1}\,$
のときは、$e_p$, $f_p$ は
$\textcolor{red}{e_2 = 1}$, $\textcolor{blue}{e_3 = 2}$, $\textcolor{green}{e_5 = 1}$, $\textcolor{#8B4513}{e_7 = 1}$, その他の $e_p$ は $0$,
$\textcolor{fuchsia}{f_2 = 3}$, $\textcolor{purple}{f_3 = 1}$, $\textcolor{teal}{f_5 = 0}$, $\textcolor{#FF8C00}{f_7 = 1}$, その他の $f_p$ は $0$
となります。べき指数の小さい方を掛け合わせたのが $\gcd$, 大きい方を掛け合わせたのが $\mbox{lcm}$ になります：
$\gcd(630,168) = 2^\textcolor{red}{1} \times 3^\textcolor{purple}{1} \times 5^\textcolor{teal}{0} \times 7^\textcolor{#8B4513}{1} = 42,\phantom{0}$
$\mbox{lcm}(630,168) = 2^\textcolor{fuchsia}{3} \times 3^\textcolor{blue}{2} \times 5^\textcolor{green}{1} \times 7^\textcolor{#8B4513}{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)$ の計算時間.