lcm(1, 2, ... , n)의 크기

이 포스팅에서 다룰 것은 AKS primality test에 사용하는 lemma 중 하나로, \(n \ge 7\)에 대해 \(\ell_{n} := \mathrm{lcm}(1,2, ... , n) \ge 2^{n}\)이 성립한다는 것이다.

 

사실 Prime Number Theorem에 의해서 \(\ell_{n} \sim e^{n}\)이 성립하기 때문에, 충분히 큰 \(n\)에 대해서는 자명히 성립하는 부등식이다. 다만 PNT가 좀 overkill이기도 하고, 기왕 non-analytical한 증명이 있으니 이야기해보도록 하자.

증명은 다음의 글에서 가져왔다.

https://math.stackexchange.com/questions/851328/textlcm1-2-3-ldots-n-geq-2n-for-n-geq-7

---

(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)(대충 스포방지용 텍스트)

 

 

---

Lemma. 자연수 \(1 \le m \le n\)에 대해 \(\displaystyle m\binom{n}{m} | \ell_{n}\)이 성립한다.

 

proof.

다음의 적분을 생각하자.

$$ I_{m, n} = \int_{0}^{1} u^{m-1}(1-u)^{n-m} du  $$

이 값은 \(\displaystyle \frac{1}{B(m-1,n-m)} = \frac{1}{m\binom{n}{m}}\)이 됨이 알려져 있다.

한편, integrand(피적분함수)는 \(n-1\)차 정수계수 다항식이므로, 적당한 정수열 \(a_{i}\)에 대해 다음이 성립한다.

$$ I_{m, n} = \sum_{i = 1}^{n} \frac{a_{i}}{i} = \frac{\cdots}{\ell_{n}}$$

 

\(\displaystyle m\binom{n}{m}\)은 당연히 정수이므로 원하는 결과를 얻는다. \( _{\blacksquare}\)

 

모든 \(k \ge 4\)에 대해 \(\ell_{2k+2} \ge \ell_{2k+1} \ge 2^{2k+2}\)가 성립함을 보이면 충분하다. \(k = 3\)인 경우는 손으로 하면 된다.

 

Lemma의 결과에 \(m = k, n = 2k+1\)을 대입하면 \(\displaystyle k\binom{2k+1}{k} | \ell_{2k+1}\)을 얻는다.

다시 \(m = k+1, n=2k+1\)을 대입하면 \(\displaystyle (k+1)\binom{2k+1}{k+1} = (k+1)\binom{2k+1}{k} | \ell_{2k+1}\)을 얻는다.

 

\(k, k+1\)은 서로소이므로 \(\displaystyle k(k+1)\binom{2k+1}{k} | \ell_{2k+1}\)이 성립하고, 따라서 \(\displaystyle \ell_{2k+1} \ge k(k+1)\binom{2k+1}{k}\)이다.

 

이 때, \(\displaystyle \binom{2k+1}{k}\)는 \(\displaystyle \binom{2k+1}{*}\) 중 가장 큰 값이다. 따라서 \(2k+2\)개의 \(\displaystyle \binom{2k+1}{*}\) 값을 산술평균한 \(2^{2k+1} / (2k+2)\)보다 크거나 같다.

 

따라서 다음이 성립하고, \(k \ge 4\)에서 이는 \(\ell_{2k+1} \ge 2^{2k+2}\)를 의미함을 쉽게 알 수 있다. \( _{\blacksquare}\)

 

$$ \ell_{2k+1} \ge k(k+1)\binom{2k+1}{k} \ge \frac{k(k+1)2^{2k+1}}{2k+2} = k2^{2k}$$