르장드르의 정리(Legendre's theorem)와 쿠머의 정리(Kummer's theorem)

      Comments Off on 르장드르의 정리(Legendre's theorem)와 쿠머의 정리(Kummer's theorem)

소수 $p$가 주어졌다고 하자. $0$이 아닌 임의의 정수 $n$에 대하여, $n$의 $p$진 값매김($p$-adic valuation)은 $\nu_{p}(n)$을 $p^{\nu}$가 $n$를 나누게 하는 양의 정수 $\nu$ 중 가장 큰 수로 정의한다. 또한 $\nu_{p}(0) = \infty$로 정의한다. 즉,

\[ \nu_{p}(n) = \begin{cases} \max \{\nu \in \N \, : \, p^{\nu} \mid n \} & \text{if} \;\; n \neq 0 \\[5px] \infty & \text{if} \;\; n = 0 \end{cases} \]

으로 정의된다. 따라서 정의에 의해서 $\nu_{p}(n)$은 $n$을 소인수분해 했을 때 $p$의 지수와 같음을 알 수 있다.

$ $

르장드르의 정리(Legendre's theorem)
정리. 르장드르의 공식(Legendre's formula)

소수 $p$가 주어졌다고 하자. 그러면 양의 정수 $n$에 대하여 $\nu_{p}(n!)$은 다음 식을 통해 구할 수 있다.

\[ \nu_{p}(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor \]

$ $

증명. 생략..

$ $

한 편, 주어진 양의 정수 $n$에 대한 $p$진 전개($p$-adic expansion)를 생각해 보자. 다시 말해 적당한 $a_0,\, \ldots,\, a_k \in \{0,\, 1,\, \ldots,\, p-1\}$가 유일하게 존재하여

\[ n = a_0 + a_1p + a_2p^2 + \cdots a_kp^k \]

와 같이 나타낼 수 있다. 이 때, $s_{p}(n) = a_0 + a_1 + \cdots + a_k$로 정의하자. 즉, $s_{p}(n)$은 $n$을 $p$진전개 했을 때, 각 자릿수의 합과 같음을 알 수 있다. 일반적으로 $\nu_{p}(n)$과 $s_{p}(n)$ 사이에는 큰 관련이 없지만, $\nu_{p}(n!)$과 $s_{p}(n)$ 사이에는 다음과 같이 밀접한 관련이 있음을 보일 수 있다.

$ $

정리. 르장드르의 정리(Legendre's theorem)

소수 $p$가 주어졌다고 하자. 그러면 양의 정수 $n$에 대하여 $\nu_{p}(n!)$은 다음 식을 통해 구할 수 있다.

\[ \nu_{p}(n!) = \frac{n - s_{p}(n)}{p - 1} \]

$ $

증명. 먼저 $n$의 $p$진 전개가 다음과 같이 주어졌다고 하자.

\[ n = a_0 + a_1p + a_2p^2 + \cdots a_kp^k \]

그러면 각각의 $1 \leq i \leq k$에 대하여

\[ \left\lfloor \frac{n}{p^i} \right\rfloor = a_i + a_{i+1}p + a_{i+2}p^2 + \cdots + a_kp^{k-i} = \sum_{j=i}^{k} a_{j}p^{j-i} \]

가 성립한다. 따라서 르장드르의 공식에 의해 다음을 얻는다.

\[ \begin{align*} \nu_{p}(n!) &= \sum_{i=1}^{k} \left\lfloor \frac{n}{p^i} \right\rfloor = \sum_{i=1}^{k} \sum_{j=i}^{k} a_{j}p^{j-i} = \sum_{j=1}^{k} \sum_{i=1}^{j} a_{j}p^{j-i} \\[5px] &= \sum_{j=1}^{k} a_{j} \frac{p^{j}-1}{p-1} = \sum_{j=0}^{k} a_{j} \frac{p^{j}-1}{p-1} = \frac{1}{p-1} \left( \sum_{j=0}^{k} a_{j}p^{j} - \sum_{j=0}^{k} a_{j} \right) \\[5px] &= \frac{1}{p-1} ( n - s_{p}(n) ) \tag*{$\color{myblue}{\blacksquare}$} \end{align*} \]

$ $

위 르장드르의 정리에서 $p=2$인 경우, 특별히 아래와 같이 재미있는 결론을 얻는다. 예를 들어 $n = 100$이라 하면, $100 = 1100100_{(2)}$이므로 $s_2(100) = 3$임을 알 수 있다. 따라서 $100!$의 소인수분해에서의 $2$의 지수는 $\nu_2(100!) = 100 - s_2(100) = 100 - 3 = 97$임을 알 수 있다.

$ $

따름정리.

임의의 양의 정수 $n$에 대하여, $n!$을 소인수분해 했을 때 $2$의 지수와 $n$을 이진전개 했을 때 각 자릿수의 합을 더하면 $n$과 같다. 즉, 다음이 성립한다.

\[ n = \nu_2(n!) + s_2(n) \]

$ $

쿠머의 정리(Kummer's theorem)

소수 $p$와 두 양의 정수 $m,\, n$이 주어졌다고 하자. 이제 $mn$의 소인수분해에서의 $p$의 지수는 $m$의 소인수분해에서의 $p$의 지수와 $n$의 소인수분해에서의 $p$의 지수의 합과 같다. 또한 $n^m$의 소인수분해에서의 $p$의 지수는 $n$의 소인수분해에서의 $p$의 지수에 $m$을 곱한 값과 같다. 즉,

  1. $\nu_p(mn) = \nu_p(m) + \nu_p(n)$
  2. $\nu_p(n^m) = m \cdot \nu_p(n)$

이 성립한다.

$ $

이제 이 사실들을 바탕으로 $p$진 값매김을 정수에서 유리수로 확장해 보자. 우선 (b)에서 $m = -1$를 대입하면, $\nu_p(\frac{1}{n}) = - \nu_p(n)$를 얻는다. 따라서 임의의 두 정수 $m,\,n$에 대하여 (단, $m \neq 0$)

\[ \nu_p \left( \frac{m}{n} \right) = \nu_p(n) - \nu_p(n) \]

으로 정의하는 것이 자연스럽다. 실제로 유리수에 대한 $p$진 값매김을 위와 같이 정의하면 정수에 대한 $p$진 값매김의 자연스러운 확장이 된다.

$ $

위와 같이 유리수로 확장한 $p$진 값매김과 르장드르의 정리를 이용하면 다음 쿠머의 정리(Kummer's theorem)를 간단히 보일 수 있다.

$ $

정리. 쿠머의 정리(Kummer's theorem)

소수 $p$가 주어졌다고 하자. 그러면 두 양의 정수 $m,\, n$에 대하여 다음 식이 성립한다.

\[ \nu_{p}\left( \binom{m+n}{n} \right) = \frac{s_p(m) + s_p(n) - s_p(m+n)}{p - 1} \]

여기서 위 식의 우변은, $p$진법에서 $m$과 $n$을 더할 때의 '자리 올림'의 횟수와 같다.

$ $

증명. 르장드르의 정리에 의해,

\[ \begin{align*} \nu_{p}\left( \binom{m+n}{n} \right) &= \nu_{p}\left( \frac{(m+n)!}{m! \, n!} \right) \\[5px] &= \nu_{p}((m+n)!) - \nu_{p}(m!) - \nu_{p}(n!) \\[5px] &= \frac{(m+n) - s_{p}(m+n)}{p - 1} - \frac{m - s_{p}(m)}{p - 1} - \frac{n - s_{p}(n)}{p - 1} \\[5px] &= \frac{s_p(m) + s_p(n) - s_p(m+n)}{p - 1} \end{align*} \]

이 성립한다..

$ $

위 정리를 적용하기 위하여 $p = 2$이고 $m = n = 100$인 경우를 생각해 보자. $100 = 1100100_{(2)}$이고

\[ 1100100_{(2)} + 1100100_{(2)} = 11001000_{(2)} \]

의 계산 과정에서 $3$번의 '자리 올림'이 발생하므로 $\nu_2(\binom{200}{100})$은 $3$임을 알 수 있다.

$ $

정리.

임의의 양의 정수 $n$에 대하여, 다음과 같이 정의되는 카탈란 수(Catalan number)

\[ C_n = \frac{1}{n+1} \binom{2n}{n} \]

은 언제나 정수값을 가진다. (즉, $n+1$은 $\binom{2n}{n}$을 나눈다.)

$ $

증명. 소수 $p$가 $n+1$의 소인수 중 하나라 하자. 또한 적당한 양의 정수 $k$에 대하여 $\nu_p(n+1) = k$라 하자. 그러면 $n+1$의 $p$진전개를

\[ n+1 = \overline{a_l \cdots a_1 a_0 \underbrace{0 \cdots 0}_{\text{$k$-times}}} \]

와 같이 나타낼 수 있다. 여기서 $a_0 \neq 0$이다. 그러므로 $n$의 $p$진전개는

\[ \overline{a_l \cdots a_1 (a_0-1) \underbrace{(p-1) \cdots (p-1)}_{\text{$k$-times}}} \]

와 같다. 따라서 $p$진법에서 $n+n$을 계산할 때, 적어도 $k$번의 '자리 올림'이 발생한다. 즉,

\[ \nu_{p}(n+1) = k \leq \nu_{p}\left( \binom{2n}{n} \right) \]

이 성립한다. 이는 $n+1$의 모든 소인수가 $\binom{2n}{n}$의 소인수임을 뜻하므로 $n+1$은 $\binom{2n}{n}$을 나눈다..