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

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

ν_{p} (n) = {\begin{cases} max {ν \in N : p^{ν} ∣ n} & if n \neq 0 \\ \infty & if n = 0 \end{cases}

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

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

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

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

ν_{p} (n!) = \sum_{i = 1}^{\infty} ⌊ \frac{n}{p^{i}} ⌋

증명. 생략..

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

n = a_{0} + a_{1} p + a_{2} p^{2} + \dots a_{k} p^{k}

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

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

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

ν_{p} (n!) = \frac{n - s_{p} (n)}{p - 1}

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

n = a_{0} + a_{1} p + a_{2} p^{2} + \dots a_{k} p^{k}

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

⌊ \frac{n}{p^{i}} ⌋ = a_{i} + a_{i + 1} p + a_{i + 2} p^{2} + \dots + a_{k} p^{k - i} = \sum_{j = i}^{k} a_{j} p^{j - i}

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

\begin{aligned} ν_{p} (n!) & = \sum_{i = 1}^{k} ⌊ \frac{n}{p^{i}} ⌋ = \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} \\ = \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} (\sum_{j = 0}^{k} a_{j} p^{j} - \sum_{j = 0}^{k} a_{j}) \\ = \frac{1}{p - 1} (n - s_{p} (n)) \end{aligned}

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

따름정리.

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

n = ν_{2} (n!) + s_{2} (n)

쿠머의 정리(Kummer's theorem)

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

$ν_{p} (m n) = ν_{p} (m) + ν_{p} (n)$
$ν_{p} (n^{m}) = m \cdot ν_{p} (n)$

이 성립한다.

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

ν_{p} (\frac{m}{n}) = ν_{p} (n) - ν_{p} (n)

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

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

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

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

ν_{p} ((\binom{m + n}{n})) = \frac{s_{p} (m) + s_{p} (n) - s_{p} (m + n)}{p - 1}

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

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

\begin{aligned} ν_{p} ((\binom{m + n}{n})) & = ν_{p} (\frac{(m + n)!}{m! n!}) \\ = ν_{p} ((m + n)!) - ν_{p} (m!) - ν_{p} (n!) \\ = \frac{(m + n) - s_{p} (m + n)}{p - 1} - \frac{m - s_{p} (m)}{p - 1} - \frac{n - s_{p} (n)}{p - 1} \\ = \frac{s_{p} (m) + s_{p} (n) - s_{p} (m + n)}{p - 1} \end{aligned}

이 성립한다..

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

1100100_{(2)} + 1100100_{(2)} = 11001000_{(2)}

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

정리.

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

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})

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

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

n + 1 = \overset{―}{a_{l} \dots a_{1} a_{0} \underset{k -times}{\underset{⏟}{0 \dots 0}}}

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

\overset{―}{a_{l} \dots a_{1} (a_{0} - 1) \underset{k -times}{\underset{⏟}{(p - 1) \dots (p - 1)}}}

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

ν_{p} (n + 1) = k \leq ν_{p} ((\binom{2 n}{n}))

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

Math Storehouse

A collection of mathematical odds and ends

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