倍数と約数（公倍数と公約数に関するその他の事実）
公倍数と公約数に関するその他の事実
以下の命題は、
初等整数論の基本定理
から導かれる素因数分解の一意性からすぐにわかるが、
素因数分解を用いなくても、
前ページの定理5
および
定理6
から直接導くことができる。
$\LCM[a, b]\gcd(a, b)=ab$.
$\LCM[a, b]=ak$ とおくと
定理6
より
$b\mid ak\Longleftrightarrow b/\gcd(a, b)\mid k$ であるから $k=b/\gcd(a, b)$ つまり $\LCM[a, b]=ab/\gcd(a, b)$.
$a, b$ が $n$ を割り切るとき $\LCM[a, b]$ も $n$ を割り切る。
$n=ak$ とおくと、$b\mid n=ak$ なので
定理6
より $b/\gcd(a, b)\mid k$ つまり
$$\LCM[a, b]=\frac{ab}{\gcd(a, b)}\mid (ak)=n$$
となる。
$a, b$ の公約数は $\gcd(a, b)$ を割り切る。
$d$ が $a, b$ の公約数ならば $ab/d=a(b/d)=b(a/d)$ は $a, b$ の公倍数なので
$\LCM[a, b]$ は $ab/d$ を割り切る。よって
定理2
より $\gcd(a, b)=ab/\LCM[a, b]$ は $d$ で割り切れる。
$\gcd(a, N)=\gcd(b, N)=1$ ならば $\gcd(ab, N)=1$.
$d=\gcd(ab, N)$ とおく。$\gcd(a, N)=1$ かつ $d\mid N$ だから $\gcd(a, d)=1$ となる。
一方 $d\mid ab$ だから $d\mid b$ となる。
しかし $\gcd(b, N)=1$ かつ $d\mid N$ だから $\gcd(b, d)=1$ となる。よって $\gcd(ab, N)=d=1$ である。
$N, k, a, b$ が整数で $k\geq 0, N^k=ab$ かつ $\gcd(a, b)=1$ ならば $a=\pm M^k, b=\pm L^k$ となる整数 $M, L$ が存在する。
$d=\gcd(a, N), a=da_1, N=dN_1$ とおく。
定理4
より $\gcd(a_1, N_1)=1$ である。
$ab=N^k$ より $a_1 b=N^k/d=d^{k-1} N_1^k$ となるが $d\mid a, \gcd(a, b)=1$ だから $\gcd(d, b)=1$ である。
$b\mid d^{k-1} N_1^k$ であるから、
初等整数論の基本定理
を繰り返し用いて $b$ は $N_1^k$ を割り切ることがわかる。
一方 $\gcd(a_1, N_1)=1$ かつ $N_1^k\mid a_1 b$ より $N_1^k$ は $b$ を割り切る。よって
定理2 (9)
より $b=\pm N_1^k$.
$N=dN_1$ より $a=N^k/(\pm N_1^k)=\pm d^k$.
参考文献
定理5 の証明は W. Sierpiński, Elementary Theory of Numbers, North-Holland, 2nd. Ed. edited by A. Schinzel, 1988, Section 1.6, p. 13 を参考とした。
参考文献
