任何正整数$n$都能记为素数乘积。
$$n = p_1p_2\cdots p_m = \prod pk\ (1<=k<=m, p1<=\cdots<=pm) $$
而且这个展开序列是唯一的。
假定一个数$m$可以用素数序列$<m1,m2,…>$表示
$k = mn \Leftrightarrow k_p = m_p + n_p$，对所有的p
而 $m/n \Leftrightarrow mp <= np$ ，对所有的p
那就可知
$k = gcd(m, n) \Leftrightarrow kp = min(mp, np)$ ，对所有的p
$k = lcm(m, n) \Leftrightarrow kp = max(mp, np)$ ，对所有的p
如果素数$p$能除尽$mn$，则根据因子分解定理，一定有$p/m$或$p/n$，或者两者都能。但是合数就不行了。