뤼카의 정리 문서 원본 보기

{{위키데이터 속성 추적}}
'''뤼카의 정리'''(Lucas' theorem, -定理)는 [[정수론|수론]]과 [[조합론]]에서 이용되는 [[정리]]로, [[프랑스인]] [[수학자]] [[에두아르 뤼카]](Édouard Lucas)의 이름이 붙어 있다. 이 정리는 어떤 [[조합]]의 수를 [[소수 (수론)|소수]] p에 대해 법 p 상에서 구할 때 간편한 계산 방식을 제공한다. 에두아르 뤼카가 처음 이 정리를 발표한 것은 [[1878년]] 논문에서였다.<ref>
* {{저널 인용| author=Édouard Lucas |title=Théorie des Fonctions Numériques Simplement Périodiques| jstor=2369308 |journal=[[American Journal of Mathematics]] |year=1878 |volume=1 |issue=2 |pages=184–196 |doi=10.2307/2369308| mr=1505161}} (part 1);
* {{저널 인용| author=Édouard Lucas |title=Théorie des Fonctions Numériques Simplement Périodiques| jstor=2369311 |journal=[[American Journal of Mathematics]] |year=1878 |volume=1 |issue=3 |pages=197–240 |doi=10.2307/2369311| mr=1505164}} (part 2);
* {{저널 인용| author=Édouard Lucas |title=Théorie des Fonctions Numériques Simplement Périodiques| jstor=2369373 |journal=[[American Journal of Mathematics]] |year=1878 |volume=1 |issue=4 |pages=289–321 |doi=10.2307/2369373| mr=1505176}} (part 3)</ref>

== 공식화 ==
임의의 음이 아닌 [[정수]] m과 n, 소수 p에 대하여 뤼카의 정리는 다음과 같이 [[합동식]]으로 표현할 수 있다.

* <math>\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,</math>

여기서 첨자가 붙은 수들은 m과 n을 소수 p에 대해 다음과 같이 p진 전개했을 때 얻어지는 것이다. 덧붙여, 한쪽의 전개가 k에서 끝나지 않더라도 더 이상 전개하지 않고 정리를 적용시키는 것이 가능하다.

# <math>m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,</math>
# <math>n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0</math>

이상과 같은 뤼카의 정리는 임의의 [[자연수]] q에 대해 법 p의 q제곱 형태로 일반화할 수 있다. 그 자세한 형태는 이 문단에 달린 주석의 논문을 참조.<ref>{{저널 인용 |author=[[Andrew Granville]] |title=Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers |journal=Canadian Mathematical Society Conference Proceedings |volume=20 |pages=253–275 |year=1997 |url=http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf |mr=1483922 |확인날짜=2016년 9월 30일 |보존url=https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf |보존날짜=2017년 2월 2일 |url-status=dead }}</ref>

== 증명 ==
뤼카의 정리를 증명하는 데는 여러 방법이 있다. 여기서는 초등적인 이론만을 이용하는 증명을 소개한다. 앞에서와 같이 m, n, p를 택하고, m과 n의 p-진 전개를 위와 같이 쓸 때, [[이항정리|이항 정리]]에 의해 다음이 성립한다.(x는 정수)

: <math>(1 + x)^{p^m} \equiv 1 + x^{p^m} \pmod p</math>

이를 이용해서 다음과 같이 전개하여,

: <math>\sum_{n=0}^m \binom{m}{n}x^n \equiv (1+x)^m \equiv \prod_{i=0}^k\left[(1+x)^{p^i}\right]^{m_i} \equiv \prod_{i=0}^k\left[1+x^{p^i}\right]^{m_i} \pmod p</math>

다시 이항 정리를 써서 안쪽의 식을 풀어내면,

: <math>\equiv \prod_{i=0}^k\left[\sum_{n_i=0}^{m_i}\binom{m_i}{n_i}x^{n_ip^i}\right] \equiv \sum_{n=0}^m \left[\prod_{i=0}^k\binom{m_i}{n_i}\right]x^n \pmod p</math>

이 된다. 법 p에 대한 [[형식적 멱급수]] 전개에서 모든 차수마다의 계수는 같으므로, 원하는 결과를 얻는다.

== 각주 ==
{{각주}}

== 외부 링크 ==
* [http://planetmath.org/encyclopedia/LucassTheorem.html 플래닛매스 - 뤼카의 정리] {{웹아카이브|url=https://web.archive.org/web/20070930225936/http://planetmath.org/encyclopedia/LucassTheorem.html}}

{{전거 통제}}

[[분류:소수에 관한 정리]]