アルゴリズム論特論(塩田)第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)$ の計算時間.