%26#039;n%26#039; a natural number.
Show:
http://www.forkosh.dreamhost.com/mimetex...
Best Answer - Chosen by Voters
Using the notation (aCb) for a!/[b!(a-b)!]Show ((p^n)Cp) = p^(n-1) mod p^n
Equivalently show p((p^n)Cp) = p^n mod p^n = 0 mod p^n
This is equivalent to showing p^n divides p((p^n)Cp). Expanding:
p((p^n)Cp) = p(p^n)!/[p!((p^n)-p)!].
Dividing out ((p^n)-p)! and the p in the numerator and denominator gives:
(p^n)((p^n)-1)((p^n)-2) ... ((p^n)-p+2)((p^n)-p+1)/((p-1)!)
Notice that
((p^n)-1)((p^n)-2) ... ((p^n)-p+2)((p^n)-p+1) is the product of p-1 consecutive numbers ==%26gt; it is divisible by (p-1)!. So there is an integer k %26gt;=1 such that k(p-1)! = ((p^n)-1)((p^n)-2) ... ((p^n)-p+2)((p^n)-p+1). So the LHS is of the form (p^n)k and is divisible by p^n, thus:
p((p^n)Cp) = 0 mod p^n and
((p^n)Cp) = p^(n-1) mod p^n. 100% 1 Vote
Other Answers (0)
No other answers.