[정수론](26)[이항정리]

이항정리

이항계수와 이항정리

• 이항계수
  n개 중 k개를 뽑는 경우의 수
  nCk = {n(n-1)(...)(n-k+1)} / {k!}
  = n! / { (n-k)! k! }
• 이항계수 덧셈공식
  nC(k-1) + nCk = (n+1)Ck
  증명
  1. 직접 이항계수 계산해보기
  2. (A+B)^(n+1) = (A+B)^n * (A+B)이용하기
  3. 조합론적 접근
     1~n+1의 수 중 k개를 뽑는다고 하자.
     그냥 1~n+1 까지 뽑는 경우의 수
     = n+1이 포함된 경우의 수 + n+1이 포함되지 않은 경우의 수 로
     나누어질 수 있다.
     즉, (n+1)Ck = nC(k-1) + nCk
• 이항정리
  너무 유명한 거라 적기만 함...
  $$(A+B)^{n} = \sum_{k=0}^{n}{ {n\choose k}A^{n-k}B^k }$$

 

법 p에 대한 이항정리

1. p가 소수일 때, 0<=k<=p 이라면
   {1<=k<=p-1}이라면? pCk ≡ 1 (mod p)
   {k=0 or p}라면? pCk ≡ 0 (mod p)
   • 증명
     pC0 = 1, pCp = 1임은 자명하다.
     1<=k<=p-1이라면
     pCk = p! / { (p-k)! k! }에서 (p-k), k < p이므로
     분자에 있는 p!의 p를 약분하지 못한다.
     따라서 언제나 mod p에서 0이 나온다.
2. 임의의 수 A, B에 대해
   (A+B)^p ≡ A^p + B^p (mod p)
   • 증명
     아까 1번에서 보인 것을 바탕으로 이항계수 전개를 하면
     처음 A^p와 마지막인 B^p 만 0이 아닌 계수가 나오므로
     성립한다.

 

이항정리를 이용한 페르마의 소정리 증명

수학적 귀납법으로 증명해보자.
정수 a, p = 소수, gcd(a, p) = 1일떄,

• a = 0 이라면?
• 0^p ≡ 0 (mod p) 이므로 참
• a = k일때 참이라 가정, a = k+1?
• k^p ≡ k (mod p) 가 참이라 가정한다고 한다.
• mod p에서 이항정리에 의해
• (k+1)^p ≡ k^p + 1^p ≡ k + 1 (mod p)
• 따라서 k+1에서도 성립한다.
• 따라서 수학적 귀납법에 의해 페르마의 소정리는 참이다.