読者です 読者をやめる 読者になる 読者になる

最小公倍数を求める方法

l={\rm lcm}(a,b),g={\rm gcd}(a,b)とする.

定理.
ab=lgが成立する.

(証明)
a=ga',b=gb'a',b'は互い素)とする.
このときab'=a'b=ga'b'であるからl=ga'b'となる.
よってlg=ga'gb'=abとなる.(証明終)

この定理を眺めると,最小公倍数を求める手順に次のようなものがあることに気がつく.
1.ユークリッドの互除法gを求める.
2.a,bgで割り,2つの商とgの積が最小公倍数である.

やはり例のとおり素因数分解して素因数を見比べるほうが早い気がする.
その方法も一応書いておく.以下p_i素数とする.
a={p_1}^{e_1} \cdots {p_n}^{e_n},b={p_1}^{f_1} \cdots {p_n}^{f_n}素因数分解する.
このときl={p_1}^{\max \{ e_1, f_1 \} } \cdots {p_n}^{ \max \{ e_n, f_n \} }である.

例えば600, 90の最小公倍数は600 = 2^3 \cdot 3 \cdot 5^2, 90 = 2 \cdot 3^2 \cdot 5より
冪の大きい数をとることで2^3 \cdot 3^2 \cdot 5^2 = 1800が分かる.