All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers > Sequences
Directly from Lucas (Posted on 2014-04-04) Difficulty: 3 of 5
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).

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Show, yes. Prove, no. Comment 1 of 1
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information