自然数列の最小公倍数の下界

ゆうき

2004 年 3 月 5 日

概要

最初の n 自然数たちの最小公倍数を下から評価する。証明は M.Nair の On Chebyshev-Type Inequalities for Primes, 1982 をのものを参考にした。

1 評価

Definition 1 (d_{n}). d_{n} を、自然数 1, 2, 3, …, n の最小公倍数をとする。

Lemma 1 (d_{n} の下界). d_{n} ≥ 2^{n}

2 証明

まず最初に

I = I(m, n) = ∫_{0}^{1} x^{m−1}(1 − x)^{n−m} dx for 1 ≤ m ≤ n

と定義する。この I を 2 通りに評価することで

∀m (1 ≤ m ≤ n) m\binom{n}{m} | d_{n}

を示したい。最初に、 I を部分積分の繰り返しで評価する。

I = \frac{1}{m} [x^{m}(1 − x)^{n−m}]_{0}^{1} + \frac{n − m}{m} ∫_{0}^{1} x^{m}(1 − x)^{n−m−1} dx
= \frac{n − m}{m} ∫_{0}^{1} x^{m}(1 − x)^{n−m−1} dx （∵ 前式第 1 項は 0）

= \frac{1}{m}(n − m)\{\frac{1}{m + 1} [x^{m+1}(1 − x)^{n−m}]_{0}^{1}

+\frac{n − m − 1}{m + 1} ∫_{0}^{1} x^{m+1}(1 − x)^{n−m−1} dx\}

= \frac{1}{m} · \frac{(n − m)(n − m − 1)}{m + 1} ∫_{0}^{1} x^{m+1}(1 − x)^{n−m−1} dx

(1)

⋮

⋮  (n + m) 回繰り返す

⋮

= \frac{1}{m} · \frac{(n − m)(n − m − 1) ⋯ 3 · 2}{(m + 1)(m + 2) ⋯ (n − 1)} · ∫_{0}^{1} x^{n−1}(1 − x)^{0} dx
= \frac{1}{m} · \frac{(n − m)(n − m − 1) ⋯ 3 · 2}{(m + 1)(m + 2) ⋯ (n − 1)} · \frac{1}{n} [x^{n}]_{0}^{1}
= \frac{1}{m} · \frac{(n − m)(n − m − 1) ⋯ 3 · 2 · 1}{(m + 1)(m + 2) ⋯ (n − 1) · n}

= 1 / (m\binom{n}{m})  (2)

一方、二項定理より

I = ∫_{0}^{1} x^{m−1}(1 − x)^{n−m} dx

= ∫_{0}^{1} x^{m−1} ( ∑_{r=0}^{n−m}(−1)^{r}\binom{n − m}{r}x^{r}) dx

= ∑_{r=0}^{n−m} [(−1)^{r}\binom{n − m}{r} ∫_{0}^{1} x^{m+r−1} dx]

= ∑_{r=0}^{n−m} [(−1)^{r}\binom{n − m}{r} · \frac{1}{m + r} [x^{m+r}]_{0}^{1}]

= ∑_{r=0}^{n−m} [(−1)^{r}\binom{n − m}{r}\frac{1}{m + r} ]  (3)

今、 ∑ の各項について r ≤ n−m より m+r ≤ n である。従って (m+r) | d_{n} となり、 d_{n}/(m + r) は正整数。従って I · d_{n} も正整数。

今、 I = (m\binom{n}{m})^{−1} なのだから、

∀m (1 ≤ m ≤ n), m\binom{n}{m} | d_{n}  (4)

が示された。特に (4) において n → 2n, m → n とすれば n\binom{2n}{n} | d_{2n} d_{2n} | d_{2n+1} だから

n\binom{2n}{n} | d_{2n+1}  (5)

同様に (4) において n → 2n + 1, m → n + 1 とすれば

(n + 1)\binom{2n + 1}{n + 1} | d_{2n+1}  (6)

ここで、

(2n + 1)\binom{2n}{n} = (2n + 1)\frac{(2n)!}{n!(2n − n)!}
= \frac{n + 1}{n + 1} · \frac{(2n + 1)(2n)!}{n!n!}
= (n + 1) · \frac{(2n + 1)(2n)!}{(n + 1)n! × \{(2n + 1) − (n + 1)\}!}
= (n + 1) · \frac{(2n + 1)!}{\{}(n + 1)!(2n + 1) − (n + 1)\}!
= (n + 1)\binom{2n + 1}{n + 1}

従って、 (6) より

(2n + 1)\binom{2n}{n} | d_{2n+1}  (7)

ユークリッドの互除法より n, 2n + 1 は互いに素だから (5) と (7) を合わせると

n(2n + 1)\binom{2n}{n} | d_{2n+1}

従って、 d_{2n+1} ≥ n(2n + 1)\binom{2n}{n} 更に、二項定理より

4^{n} = (1 + 1)^{2n} = ∑_{k=0}^{2} n\binom{2n}{k}1^{k} · 1^{n−k} ≤ ∑_{k=0}^{2} n\binom{2n}{n} = (2n + 1)\binom{2n}{n}

なので、

d_{2n+1} ≥ n · 4^{n}  (8)

これより、 n ≥ 2 ならば

d_{2n+1} ≥ n · 4^{n} ≥ 2 · 4^{n} = 2^{2n+1}

つまり、 5 以上の奇数 k について d_{k} ≥ 2^{k} また n ≥ 4 ならば

d_{2n+2} ≥ d_{2n+1} ≥ n · 4^{n} ≥ 4 · 4^{n} = 2^{2n+2}

つまり、 10 以上の偶数について d_{k} ≥ 2^{k}

また、 d_{8} = 840 ≥ 256 = 2^{8}, d_{6} = 60 ≱ 64 = 2^{6} だから、 n ≥ 7 について d_{n} ≥ 2^{n} が言える。

参考文献

[1] M.Nair, On Chebyshev-Type Inequalities for Primes, The American Mathematical Monthly, Vol89, No.2(Feb., 1982), 126-129