#0003. r개의 연속한 자연수의 곱이 r!의 배수임을 증명하기

고등학교 수학 교과서에서 \( _n C _r\)로 표기하는, 조합을 배울 때 다음과 같은 공식을 보게 됩니다.

$$ _n C _r = \frac{ _n P _r }{r!} = \frac{ n \left(n-1 \right) \cdots \left(n-r+1 \right)}{r \left(r-1 \right) \cdots 1}$$

이때 \( _n C _r \)의 값은 \(n\)개의 구분할 수 있는 공 중에서 \(r\)개를 중복을 허용하지 않고 순서에 상관없이 뽑는 경우의 수이기 때문에, 당연히 음이 아닌 정수 값일 것임을 알 수 있습니다. 그러나 실제로 분수에서 분모가 전부 약분될까요? 이러한 의문을 구글에 검색해보았습니다. 많은 사람들이 내놓는 답으로 다음과 같은 것이 있었습니다.

"\(k\)개의 연속한 자연수의 곱은 \(k\)의 배수이므로, \(n \left(n-1 \right) \cdots \left(n-r+1 \right)\)는 \(r, \ r-1, \ \cdots \ 2\)의 배수이다. 따라서 분자는 분모의 배수이다."

언뜻 보기에는 맞는 것 같지만, 잘못된 논리입니다. 예를 들어 12는 2, 3, 4의 공배수지만 4!(=24)의 배수는 아닙니다. 비록 위의 설명보다는 복잡하지만, 엄밀하게 해결해봅시다. 우선 가우스 함수 \(\left[ x \right]\)의 성질을 알아야 합니다.

<가우스 함수라는 용어에 대하여>

\( \left[ x \right]\)는 흔히 가우스 함수로 부르지만, 가우스의 이름을 딴 함수는 여러 가지이기 때문에 최대정수 함수, 바닥 함수 등으로도 불린다. 이 글에서는 가우스 함수로 용어를 통일하겠다.

여기에서는 실수 \(x\)에 대하여 가우스 함수를 다음과 같이 약속하겠습니다.

$$ \left[ x \right] \equiv \max{ \left\{ n \in \mathbb{Z} : n \leq x \right\} } $$

성질 1. 가우스 함수는 단조증가한다.

'단조증가'는 적어도 감소하지 않는다는 말입니다. 그러니까 특정 구간에서 증가하거나 상수함수라는 말입니다. 이는 사실 정의에 의하여 자명합니다. 하지만 귀류법으로 조금 설명하겠습니다.

\( x < y\)이고 \( \left[ x \right] > \left[ y \right] \)인 \(x\), \(y\)가 존재한다고 가정하자. 이때 \( \left[ y \right] < \left[ x \right] \leq x < y \)이고 \( \left[ x \right] \in \mathbb{Z} \)이므로 \(y\)를 넘지 않는 최대 정수는 \( \left[ y \right] \)가 아니다. 이는 모순이므로 주어진 명제는 성립하지 않는다. 즉 가우스 함수는 단조증가한다. 또한 \(0.3 < 0.5\) 인데 \( \left[0.3\right] = 0 = \left[0.5\right]\)이므로 가우스 함수는 순증가하지 않는다.

성질 2. 실수 \(x\)와 정수 \(n\)에 대하여 \(\left[x+n\right] = \left[x\right]+n\)이 성립한다.

\(\left[ x \right] = m\)이라 하자. 그럼 가우스 함수의 정의에 의하여 \(m \leq x < m+1\)이 성립한다. 따라서 \(m+n \leq x + n < m + n + 1\)이 성립한다. 따라서 \(\left[x+n\right] = m+n = \left[x\right]+n\)

성질 3. 실수 \(x\), \(y\)에 대하여 \(\left[x+y\right] \geq \left[x\right] + \left[y\right]\)이 성립한다.

성질 1, 2에 의하여 \(\left[x+y\right] \geq \left[x + \left[ y \right] \right] = \left[x\right] + \left[y\right]\)
이때 등호는 \(x\)또는 \(y\)가 정수일 때 성립한다.

성질 3.의 식에 \(x = x-y\)를 대입하면 다음과 동치임을 알 수 있습니다: \(\left[x\right] - \left[y\right] \geq \left[x-y\right]\)

성질 4. 자연수 \(x\), \(y\)에 대하여 \(x\)를 \(y\)로 나눈 몫은 \(\left[\frac{x}{y}\right]\)이다.

나눗셈 정리에 의하여, 다음을 만족하는 정수 \(q\), \(r\)이 유일하게 존재한다. (단 \(0 \leq r < y\))
$$x = yq + r $$
양변을 y로 나누면
$$ \frac{x}{y} = q + \frac{r}{y}$$
이때 \(0 \leq r < y\)이므로
$$ q \leq \frac{x}{y} = q + \frac{r}{y} < q + \frac{y}{y} = q+1$$
$$ \therefore \left[\frac{x}{y}\right] = q$$
이때 \(q\)가 \(x\)를 \(y\)로 나눈 몫이므로, 명제가 성립한다.

이제 본격적으로 \(r\)개의 연속한 자연수의 곱이 \(r!\)의 배수임을 증명해봅시다.

증명

어떤 소수(prime number) \(p\), 음이 아닌 정수 \(t\), \(s\)에 대하여 \( r! = p^t m\), \( n \left( n-1 \right) \cdots \left( n-r+1 \right) = p^s M\)이라 하자. 단 \(m\), \(M\)은 \(p\)와 서로소이다.

주어진 문제는 \(1 < p \leq r\)을 만족하는 모든 소수 \(p\)에 대하여 \(t \leq s\)가 성립함을 보이는 것과 같다.

어떤 자연수\(r\)을 \(p\)로 나눈 몫은 \(1\)부터 \(r\)까지 \(p\)의 개수와 같다. 목표는 \(r! = 1 \times 2 \times \cdots \times r\)에서 \(p\)가 곱해진 개수를 구하는 문제이므로, \(1, \ 2, \ 3, \ \cdots , \ r\)에서 각각 \(p\)가 곱해진 개수를 모두 더하면 된다. 이를테면 \(p^3 \mid i\)이고 \(p^4 \nmid i\)를 만족하는 \(i\)가 있다고 할 때, \(p\)가 곱해지는 개수는 3개이다. 따라서 \(r!\)에서 \(p\)가 곱해진 개수를 구하는 것은 \(1\)부터 \(r\)까지 \(p^1, \ p^2, \ \cdots \ \)가 곱해진 개수를 구하는 것과 같다.

적당히 \( p^k \leq r\)를 만족하는 최대의 자연수 \(k\)를 생각하자.

성질 3, 4에 의하여
$$ \left[ \frac{n}{p} \right] - \left[ \frac{n-r}{p} \right] \geq \left[ \frac{r}{p} \right] $$
$$ \left[ \frac{n}{p^2} \right] - \left[ \frac{n-r}{p^2} \right] \geq \left[ \frac{r}{p^2} \right] $$
마찬가지로, $$ \left[ \frac{n}{p^k} \right] - \left[ \frac{n-r}{p^k} \right] \geq \left[ \frac{r}{p^k} \right] $$
변끼리 더하면
$$ \sum_{i=1}^{k}{\left[ \frac{n}{p^i} \right]} - \sum_{i=1}^{k}{\left[ \frac{n-r}{p^i} \right]} \geq \sum_{i=1}^{k}{\left[ \frac{r}{p^i} \right]} $$

이때 \(\sum_{i=1}^{k}{\left[ \frac{n}{p^i} \right]}\)은 \(n!\)에서 \(p\)가 곱해진 개수이고, \(\sum_{i=1}^{k}{\left[ \frac{n-r}{p^i} \right]}\)은 \(\left(n-r\right)!\)에서 \(p\)가 곱해진 개수이므로 좌변은 \(n! \div \left(n-r\right)! = n \left( n-1 \right) \cdots \left( n-r+1 \right)\)에서 \(p\)가 곱해진 개수이고, 우변은 \(r!\)에서 \(p\)가 곱해진 개수이다. 위의 부등식이 \(1 < p \leq r\)을 만족하는 모든 소수 \(p\)에 대하여 성립하므로, 주어진 명제는 증명되었다.