Lucas's theorem (뤼카의 정리)

// Lucas's theorem 

---

   What is Lucas's theorem?   

 

 

를 구하는 과정에서 n의 값이 상당히 클 경우 사용하면 유용한 정리이다.

 

  n의 값이 적당하다면, n!, ( n-k )!, k! 의 값을 각각 구하여 연산하면 되지만, n의 값이 10억만 되더라도

unsigned long lnog에 조차 담을 수 없게 된다. 이때 뤼카의 정리를 이용할 수 있다.

 

---

   Theorem   

  먼저, n과 k를 p진법의 전개식으로 나타내보자.

  이때, 다음의 합동식이 성립한다.

---

   Example   

 

  따라서 아래와 같이 나타낼 수 있다.

  따라서 답은 0이 된다.

---

   Proof   

// 아직 작성중인 글 입니다..