[정수론 101 #2] Lucas Theorem
지난번에 Legendre Symbol과 이차잉여계에 대해 알아보았다면, 이번에는 Legendre의 또다른 업적 중 하나인 르장드르 공식과 관련 이론에 대해 알아보도록 하겠다.
[정수론101 #0] 에서 언급한 것에 이어 정수론은 정수들의 소인수분해에 관심이 있다. 모든 정수들은 소인수분해가 가능하고, 이 소인수분해의 결과를 이용하면 수의 성질을 면밀히 분석할 수 있다. 합성수로는 해석할 수 없는 것들이 소수, 혹은 소수의 거듭제곱의 형태로는 해석될 수 있다.
하지만, 숫자가 매우커진다면 소인수 분해하는 것이 쉽지만은 않다. 특히, 팩토리얼(!)이 붙어 있는 경우라면 더더욱 소인수분해하는 것이 어렵다.
이 어려움을 해결해 주는 것이 바로 '드 폴리낙'의 정리이다. '드 폴리낙'의 정리를 시작으로, 팩토리얼의 소인수의 최대지수에 대해서 논하는 몇가지 정리가 있다. 이들을 논리적인 순서로 배치하여 설명해 보겠다.
de Polignac's Theorem
드 폴리낙의 정리(de Polignac's theorem) 은 이름은 모르는 채 아는 경우가 많다. 정리의 내용을 살펴보면 알 수도 있을 것이다.
소수 \(p\)와 자연수 \(n\)에 대해
\[ \nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor {\frac {n}{p^{i}}}\right\rfloor \]
예를 들자면, \(n=14, p=13\)인 경우 \[\nu_13 (14!) = \left\lfloor {\frac {14}{3}}+{\frac{14}{3^2}}+{\frac{14}{3^3}}+\cdots =5 \]이다.
Legendre's Formula
드 폴리낙 정리의 내용과 르장드르의 공식은 본질적으로 동일한 내용이다. 그러나 르장드르 공식(Legendre's formula)는 진법의 표현을 이용하여 식을 표현하였다.
\(s_p(n)\)을 \(p\)진법에서 \(n\)의 각 자리수의 합으로 정의할 때, 즉 \(n = (\overline{a_m a_{m-1} \cdots a_0}) p = a_m p^m + a{m-1}p^{m-1}+\cdots +a_0 p^0\)일 때
\[s_p(n):= a_m+a_{m-1}+\cdots+a_0\]으로 정의한다면,
\[\nu_{p}(n!)= {n - s_p(n) \over {p-1}}\]이다.
예를 들어 위에서 했던 것과 마찬가지로 \(n=14, p=13\)인 경우
\[14 = 1 \cdot 3^2 + 1 \cdot 3 + 2 \cdot 3^0 = 112_{3}\]이므로 다음이 성립한다.
\[\nu_{13} (14!) = {14 - s_3(14)\over 3-1}={14-4 \over 3-1}=5\]
Kummer's Theorem
다음으로는 쿠머의 정리(Kummer's theorem) 를 보도록 하겠다. 이 또한 Legendre와 같이 진법의 개념을 사용한다. 정리의 내용은 다음과 같다.
자연수 \(m \geq n\)과 소수 \(p\)에 대해
\(\nu_p(\binom{m} {n})\)은 \(p\)진법에서 \(n+(m-n)\)을 연산할 때 생기는 자리 올림의 횟수와 같다.
Kummer 정리의 증명은 Legendre's Formula를 이용하여 증명할 수 있다. 결국 모든 이항계수(binomial coefficient) 이자 조합(combination) 은 팩토리얼의 곱과 몫으로 나타낼 수 있기 때문에 이 증명은 어렵지 않게 할 수 있다.
예를 들어 \(m=21, \ n= 7, \ p=3 \)일 때, \(m=210_{(3)}\), \(m-n=112_{(3)}\), \(n=21_{(3)}\)이므로 자리 올림이 2번 일어나게 된다.
한편 Legendre's Formula를 이용하면 \[\nu_3(21!)={21-3 \over 3-1}= 9,\ \nu_3(14!)={14-4\over3-1}=5,\ \nu_3(7!)={7-3 \over 3-1}= 2.\] \[\therefore 9-5-2=2\]이므로 성립함을 알 수 있다.
Lucas' Theorem
이제 마지막이다. 여기까지 오기 위해 드 폴리낙부터 시작해서 여러 이론을 설명한 것이다. 이제 소개할 정리는 Kummer의 정리를 조금 다른 형태로 나타낸 것인 루카스의 정리(Lucas' theorem) 이다. 내용은 다음과 같다.
두 자연수 \(m, n \)과 소수 \(p \)에 대해 \[m = m_kp^k+m_{k-1}p^{k-1}+\cdots+m_1p+m_0,\]
\[n=n_kp^k+n_{k-1}p^{k-1}+\cdots+n_1p+n_0\]이면, 다음이 성립한다.
\[\binom mn \equiv \binom {m_k}{n_k}\binom {m_{k-1}}{n_{k-1}}\cdots \binom {m_1}{n_1}\binom {m_0}{n_0} (\text{mod} \ p)\]
단, \(a<b\)이거나 \(a=0\)일 때는 \(\binom ab=0\)으로 간주한다.
마지막으로 예를 들자면, \(m=263, \ n= 7, \ p=5\)일 때,
\(m=2023_{(5)}, n=012_{(3)}\)이고, Lucas정리에 의하면
\[\binom {263} 7 \equiv \binom {2}{0}\binom {0}{0}\binom {2}{1}\binom {3}{2} \equiv 1 \ (\text{mod} \ 5)\]일 것이다. 실제로 그러한가?
\[\binom {263}{7}= {263 \cdot 262\cdot261\cdot260 \cdot259 \cdot258 \cdot257 \over 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2} =1078897248\]이고, 결국 \[1078897248 \equiv 1 \ (\text{mod} \ 5)\]이므로 성립한다.
마무리하며
조금 쌩뚱맞을 수도 있지만, 팩토리얼과 관련된 몇가지 이론을 알아보았다. 이것들은 정수론에서만 다루는, 몇몇 수학 (상 \(\cdot\)하) 교재에서 간단하게 드폴리낙을 사용했을 수도 있지만, 아주 유니크한 주제이다. 이런 원리는 정수론의 응용분야에서 최대 output이라 할 수 있는 암호화의 기본 바탕이 되기도 한다. 다음에는 앞서 설명한 Legendre기호를 어떻게 적용하는지, 활용법은 무엇인지 알아보도록 하겠다.