#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$에 대하여 성립하므로, 주어진 명제는 증명되었다.