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,n1)=0 (mod p),
then
n=p^t
(a nonzero 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 20140407 12:46:52 