Let us denote by(n,k) the standard combination (select k elements from a set of n).
Show that if
(n,1)=(n,2)=...=(n,n-1)=0 (mod p),
then
n=p^t
(a non-zero power of a prime number p).

It's pretty easy to show if n is a prime then p=n, t=1 and n=p^1
For example with n=11,
(11,1)=11/1
(11,2)=(11*10)/(2*1)
(11,3)=(11*10*9)/(3*2*1)
...
(11,10)=(11*10*9*8*7*6*5*4*3*2)/(10*9*8*7*6*5*4*3*2*1)
Each if these is clearly a multiple of 11 because the numerator has a factor of 11 but the denominator does not. 
It is pretty obvious this will work for any prime.

For a number with two different primes in its factorization it will not work.  When n=10
(10,2)=(10*9)/(2*1)
is not a multiple of 10 (or a power of 10) since the 2 in the denominator reduces the only factor of 2 in the numerator.
(So the "if" part of the statement does not hold)

What's left are prime powers.   For example when n=9=3^2.
(9,3)=(9*8*7)/(3*2*1)
The 3 in the denominator does reduce one of the factors of 3 in the numerator but there is still one left.
(9,6)=(9*8*7*6*5*4)/(6*5*4*3*2*1)
And so p=3 and n=p^2
By the time there's a second factor of 3 in the denominator there is an extra one in the numerator.
A prime power loads extra p^t loads enough extra factors of p in the numerator that they won't all get reduced.

Posted by Jer on 2014-04-07 12:46:52