르장드르의 정리(Legendre's theorem)와 쿠머의 정리(Kummer's theorem)
written by jjycjn 2018. 8. 16. 23:24
소수 $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)
$ $
증명. 생략..
$ $
한 편, 주어진 양의 정수 $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)$ 사이에는 다음과 같이 밀접한 관련이 있음을 보일 수 있다.
$ $
$ $
증명. 먼저 $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$임을 알 수 있다.$ $
$ $
쿠머의 정리(Kummer's theorem)[/subtitle]
소수 $p$와 두 양의 정수 $m,\, n$이 주어졌다고 하자. 이제 $mn$의 소인수분해에서의 $p$의 지수는 $m$의 소인수분해에서의 $p$의 지수와 $n$의 소인수분해에서의 $p$의 지수의 합과 같다. 또한 $n^m$의 소인수분해에서의 $p$의 지수는 $n$의 소인수분해에서의 $p$의 지수에 $m$을 곱한 값과 같다. 즉,
- $\nu_p(mn) = \nu_p(m) + \nu_p(n)$
- $\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)를 간단히 보일 수 있다.$ $
$ $
증명. 르장드르의 정리에 의해,\[ \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$임을 알 수 있다.
$ $
$ $
증명. 소수 $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}$을 나눈다.
.
'Algebra > Number Theory' 카테고리의 다른 글
산술 도함수(arithmetic derivative)에 대하여 - 2. 유리수로의 확장 (1) | 2020.07.29 |
---|---|
산술 도함수(arithmetic derivative)에 대하여 - 1. 정의와 기본 성질 (0) | 2020.07.29 |
군론(group theory)를 이용한 정수론의 정리 증명 (0) | 2018.08.11 |
택시캡수(taxicab number)와 캡택시수(cabtaxi number) (1) | 2018.08.03 |
짝수 완전수(perfect number)와 메르센 소수(Mersenne prime) (0) | 2018.06.16 |