뤼카의 정리

1 개요

Lucas' theorem

Lucas의 定理

뤼카의 정리

• 수론과 조합론에서 이용되는 정리
• 어떤 조합의 수를 소수 p에 대해 법 p 상에서 구할 때 간편한 계산 방식을 제공하는 정리
• 1878년, 프랑스 수학자 에두아르 뤼카의 논문에서 처음 발표됨

2 내용

• 임의의 음이 아닌 정수 m과 n, 소수 p에 대해 합동식으로 표현할 수 있음

[math]\displaystyle{ \binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p, }[/math]

여기서 첨자가 붙은 수들은 m과 n을 소수 p에 대해 다음과 같이 p진 전개했을 때 얻어지는 것

한쪽의 전개가 k에서 끝나지 않더라도 더 이상 전개하지 않고 정리를 적용시키는 것이 가능함

1. [math]\displaystyle{ m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0, }[/math]
2. [math]\displaystyle{ n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0 }[/math]

→ 임의의 자연수 q에 대해 법 p의 q제곱 형태로 일반화할 수 있음

3 같이 보기

• Kummer의 정리
• 에두아르 뤼카
• 앤드류 그랜빌

4 참고

• 위키백과 "뤼카의 정리"
• 다음백과 "뤼카의 정리"
• 네이버백과 "뤼카의 정리"