最小公倍数

1. $a=0$ または $b=0$ なら、公倍数は $0$ だけであり、$L=0$ の倍数も $0$ だけである。以下 $a,b\neq0$ とし、$L>0$ である。$L$ の倍数 $Lk$ は、$a\mid L$、$b\mid L$ から $a,b$ の公倍数である。逆に $c$ を $a,b$ の公倍数とし、除法の原理により $c=qL+r$、$0\le r< L$ と書く。$a\mid c$、$a\mid L$ なので $a\mid c-qL=r$ であり、同様に $b\mid r$ である。$r>0$ なら $r$ は $L$ より小さい正の公倍数となり、$L$ の最小性に反する。よって $r=0$、すなわち $L\mid c$ である。
2. 1 により $L$ はこの性質をもつ。$0$ 以上の整数 $L'$ も同じ性質をもつとすると、$L'$ は公倍数なので $L\mid L'$、$L$ は公倍数なので $L'\mid L$ である。$L=0$ なら $L\mid L'$ から $L'=0$ である。$L>0$ なら、$L'=0$ とすると $L'\mid L$ から $L=0$ となって矛盾するので $L'>0$ である。正の整数 $L,L'$ が互いに割り切り合うので $L\le L'\le L$、すなわち $L'=L$ である。
   3 個以上の場合も、「$a_1,\dots,a_k$ のすべてが $c$ と $L$ を割り切るなら余り $r$ も割り切る」ので、同じ議論がそのまま通る。$\square$

thm-lcm-common-multiples の 2 により、公倍数全体がちょうど $M$ の倍数全体となる $0$ 以上の整数 $M$ は最小公倍数に等しい。これを使って各項を示す。

1. 公倍数全体は $a,b$ の順序によらない。$a$ と $1$ の公倍数、$a$ と $a$ の公倍数はどちらも $a$ の倍数全体であり、それは $|a|$ の倍数全体である。
2. $m=0$ または $a=0$ または $b=0$ なら両辺とも $0$ である。そうでないとき、$c$ が $ma$ と $mb$ の公倍数なら $m\mid c$ なので $c=mc'$ と書け、$ma\mid mc'$ から $a\mid c'$、同様に $b\mid c'$ である。逆に $c'$ が $a,b$ の公倍数なら $mc'$ は $ma,mb$ の公倍数である。したがって $ma,mb$ の公倍数全体は $\{mc'\mid c'\in\operatorname{lcm}(a,b)\mathbb{Z}\}=|m|\operatorname{lcm}(a,b)\mathbb{Z}$ であり、主張が従う。
3. thm-lcm-common-multiples の 1 により、「$a\mid c$ かつ $b\mid c$」は「$\operatorname{lcm}(a,b)\mid c$」と同値である。よって $a,b,c$ の公倍数全体は $\operatorname{lcm}(a,b)$ と $c$ の公倍数全体に等しく、最小公倍数も等しい。もう一方の括り方も同様である。
4. $a\mid b$ なら $a,b$ の公倍数全体は $b$ の倍数全体であり、$\operatorname{lcm}(a,b)=|b|$ である。逆に $\operatorname{lcm}(a,b)=|b|$ なら $a\mid\operatorname{lcm}(a,b)=|b|$ なので $a\mid b$ である。$\square$

最大公約数 の記事の定理「素因数分解による最大公約数と最小公倍数」により、両辺の各素数 $p$ の指数は、$a,b,c$ の $p$ の指数を $x,y,z$ として、1 つ目の等式では $\min(x,\max(y,z))$ と $\max(\min(x,y),\min(x,z))$、2 つ目では $\max(x,\min(y,z))$ と $\min(\max(x,y),\max(x,z))$ である。両辺は $y,z$ の入れ替えで変わらないので $y\le z$ としてよい。1 つ目の左辺は $\min(x,z)$ であり、右辺は $\min(x,y)\le\min(x,z)$ なので $\min(x,z)$ で、等しい。2 つ目の左辺は $\max(x,y)$ であり、右辺は $\max(x,y)\le\max(x,z)$ なので $\max(x,y)$ で、等しい。すべての素数で指数が一致するので、素因数分解の一意性により両辺は等しい。$\square$

$|a_1\cdots a_k|$ は公倍数なので、thm-lcm-common-multiples により $\operatorname{lcm}(a_1,\dots,a_k)$ で割り切れる。符号によらないので $a_i>0$ としてよい。素数 $p$ について $a_i$ の $p$ の指数を $x_i\ge0$ とすると、最小公倍数の $p$ の指数は $\max_ix_i$、積の $p$ の指数は $\sum_ix_i$ である（2 個の場合は 最大公約数 の記事の定理「素因数分解による最大公約数と最小公倍数」、3 個以上は prop-lcm-rules の 3 により 2 個の場合を繰り返す）。$x_i\ge0$ なので $\max_ix_i\le\sum_ix_i$ であり、等号は $x_i$ のうち正のものが高々 1 つのときに限る。したがって最小公倍数と積が等しいことは、どの素数も 2 つ以上の $a_i$ を割り切らないこと、すなわち $a_1,\dots,a_k$ が対ごとに互いに素であることと同値である。$\square$

長さ $l$ の巡回 $\gamma=(x_0\ x_1\ \cdots\ x_{l-1})$ は $x_j$ を $x_{j+1}$（添字は $l$ を法として読む）へ移すので、$\gamma^m$ は $x_j$ を $x_{j+m}$ へ移す。よって $\gamma^m$ がこの $l$ 文字を動かさないことは $l\mid m$ と同値である。共通の文字をもたない巡回どうしは可換であり、$\sigma^m$ は各巡回の $m$ 乗の積である。各巡回の $m$ 乗はそれぞれ別々の文字の上でしか動かないので、$\sigma^m$ が恒等置換であることは、すべての $i$ について $l_i\mid m$ であること、すなわち $m$ が $l_1,\dots,l_k$ の公倍数であることと同値である。そのような正の $m$ の最小のものが $\operatorname{lcm}(l_1,\dots,l_k)$ である。$\square$

prop-lcm-rules の 3 を繰り返し使うと、prop-lcm-pairwise-coprime の証明と同じく、$L_n$ の素数 $p$ の指数は $1,\dots,n$ の $p$ の指数の最大値である。$p>n$ ならどの $j\le n$ も $p$ で割り切れないので指数は $0$ である。$p\le n$ とし、$p^e\le n< p^{e+1}$ となる $e\ge1$ をとる。$j=p^e$ の指数は $e$ であり、$p^{e+1}$ で割り切れる正の整数は $p^{e+1}>n$ 以上なので、$n$ 以下のどの $j$ の指数も $e$ 以下である。よって $L_n$ の $p$ の指数は $e$ である。$p^e\le n< p^{e+1}$ は $e\le\log n/\log p< e+1$ と同値なので $e=\lfloor\log n/\log p\rfloor$ であり、1 つ目の式を得る。$e$ は $p^j\le n$ となる $j\ge1$ の個数でもあるので、対数をとると 2 つ目の式になる。$\square$

$I(m,n):=\int_0^1x^{m-1}(1-x)^{n-m}\,dx$ とおく。二項定理で $(1-x)^{n-m}$ を展開して項ごとに積分すると
$$ I(m,n)=\sum_{j=0}^{n-m}(-1)^j\binom{n-m}{j}\int_0^1x^{m+j-1}\,dx=\sum_{j=0}^{n-m}(-1)^j\binom{n-m}{j}\frac1{m+j} $$
である。分母 $m+j$ は $m$ 以上 $n$ 以下の整数なので $L_n$ を割り切り、$L_n\cdot I(m,n)$ は整数である。
一方、$I(m,n)=\dfrac1{m\binom nm}$ であることを $m$ についての下向きの帰納法で示す。$m=n$ では $I(n,n)=\int_0^1x^{n-1}dx=\frac1n=\frac1{n\binom nn}$ である。$m< n$ のとき部分積分により
$$ I(m,n)=\Bigl[\frac{x^m}m(1-x)^{n-m}\Bigr]_0^1+\frac{n-m}m\int_0^1x^m(1-x)^{n-m-1}\,dx=\frac{n-m}m\,I(m+1,n) $$
であり（境界項は $x=0,1$ で $0$）、帰納法の仮定と $(m+1)\binom n{m+1}=\frac{n!}{m!\,(n-m-1)!}=(n-m)\binom nm$ から
$$ I(m,n)=\frac{n-m}m\cdot\frac1{(m+1)\binom n{m+1}}=\frac{n-m}m\cdot\frac1{(n-m)\binom nm}=\frac1{m\binom nm} $$
を得る。以上から $L_n/\bigl(m\binom nm\bigr)=L_n\cdot I(m,n)$ は整数である。$\square$

$k\ge1$ とする。lem-lcm-binomial を $(m,n)=(k+1,2k+1)$ と $(k,2k)$ に使う。$(k+1)\binom{2k+1}{k+1}=\frac{(2k+1)!}{k!\,k!}=(2k+1)\binom{2k}k$ なので、$(2k+1)\binom{2k}k$ は $L_{2k+1}$ を割り切り、$k\binom{2k}k$ は $L_{2k}$ を、したがって $L_{2k+1}$ を割り切る。$\gcd(k,2k+1)=\gcd(k,1)=1$ なので $\operatorname{lcm}(k,2k+1)=k(2k+1)$ であり、prop-lcm-rules の 2 から $(2k+1)\binom{2k}k$ と $k\binom{2k}k$ の最小公倍数は $k(2k+1)\binom{2k}k$ である。thm-lcm-common-multiples により、これが $L_{2k+1}$ を割り切る。
次に $\binom{2k}{j}\le\binom{2k}k$（$0\le j\le2k$）である。実際 $\binom{2k}{j+1}\big/\binom{2k}{j}=\frac{2k-j}{j+1}$ は $j\le k-1$ で $1$ 以上、$j\ge k$ で $1$ 未満である。$2k+1$ 個の項の和は $\sum_j\binom{2k}j=2^{2k}=4^k$ なので $(2k+1)\binom{2k}k\ge4^k$ であり、
$$ L_{2k+1}\ge k(2k+1)\binom{2k}k\ge k\cdot4^k $$
となる。$k\ge2$ なら $k\cdot4^k\ge2\cdot4^k=2^{2k+1}$ なので、奇数 $n=2k+1\ge5$ で $L_n\ge2^n$ である。$k\ge4$ なら $L_{2k+2}\ge L_{2k+1}\ge k\cdot4^k\ge4^{k+1}=2^{2k+2}$ なので、偶数 $n\ge10$ で $L_n\ge2^n$ である。残る $n=8$ では $L_8=840\ge256=2^8$ である。$\square$

prop-lcm-first-n により $L_n$ は $\pi(n)$ 個の因子 $p^{\lfloor\log n/\log p\rfloor}$ の積で、各因子は $n$ 以下である。よって $L_n\le n^{\pi(n)}$ であり、thm-lcm-lower-bound と合わせて $2^n\le n^{\pi(n)}$ である。対数をとれば主張を得る。$\square$

$\theta(x):=\sum_{p\le x}\log p$（Chebyshev の（第 1）関数）とおく。prop-lcm-first-n の和を指数 $e$ ごとに分けると、$p^e\le n$ は $p\le n^{1/e}$ と同値なので
$$ \log L_n=\sum_{e\ge1}\theta(n^{1/e}) $$
である。$n^{1/e}<2$ となる $e$ の項は $0$ なので、$e\ge2$ の項は $e\le\log n/\log2$ の範囲の高々 $\log n/\log2$ 個であり、各項は $\theta(n^{1/2})$ 以下である。素数定理 の記事の定理「Chebyshevの評価」の 1 により $\theta(n^{1/2})<(4\log2)\sqrt n$ なので
$$ 0\le\log L_n-\theta(n)<\frac{\log n}{\log2}\cdot(4\log2)\sqrt n=4\sqrt n\log n $$
である。$4\sqrt n\log n/n\to0$ なので、$\log L_n/n\to1$ は $\theta(n)/n\to1$ と同値である。$\theta$ は $[n,n+1)$ で一定で $n/x\to1$ なので、$\theta(n)/n\to1$ は $\theta(x)/x\to1$（実数 $x\to\infty$）と同値であり、素数定理 の記事の命題「素数定理の Chebyshev の関数による言い換え」によりこれは素数定理と同値である。$\square$