Author |
Topic: paCpb (Read 662 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
Prove that, if p is prime, then for any a,b
paCpb = aCb mod p2.
When is it true mod p3?
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
 |
Re: paCpb
« Reply #1 on: Jul 16th, 2004, 1:58am » |
 Quote  Modify
|
on Jul 13th, 2004, 11:58am, Eigenray wrote:Prove that, if p is prime, then for any a,b
paCpb = aCb mod p2 |
|
Here’s a solution I saw in “Concrete Mathematics”. The well-known identity (called Chu-Vandermonde convolution) states that
[sum](k_1+k_2=n) rCk_1* sCk_2 = r+sCn (1)
This generalizes to an arbitrary number of variables, and - applied to our case – may be written as:
apCbp = [sum](k_1+…+k_a=bp) pCk_1*…* pCk_b, (2)
where 0 [le] k_i [le] p. The key observation is that the inner product of C’s is not divisible by p2 if and only if all of k’s are divisible by p (why?). This happens only in the following combination: there are exactly b k’s equal to p, and (a-b) k’s equal to 0. But the number of such combinations is exactly aCb, and the result follows.
Quote:
This was not in “CM”, but the same approach works. Referring to formula (2), we see that every combination of k’s where at least 3 k’s are not divisible by p, gives a product divisible by p3. So, it remains to see what happens in a combination where exactly two k’s are not divisible by p. Without loss of generality, assume these are k_1, k_2. Then obviously k_1+k_2 = p, and the overall contribution to the sum is – compare to (1):
[sum](k_1+k_2=p) pCk_1* pCk_2 = 2pCp – 2.
The -2 term is due to fact that k_1, k_2 cannot be 0. Now, it may be shown that for primes p [ge] 5, 2pCp [equiv] 2 (mod p3) (this is an elementary proof of a similar result). So, the answer to this part is p > 3.
And now comes the most interesting part. While browsing the Web for the references of the last statement, I came across Wolstenholme’s Theorem, which shows a close relation between this problem and the one I posted several days ago! Isn’t it amazing?!
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
Attached is the solution I came up with a while ago. The similarities are remarkable.
It essentially uses both results from the problem you posted, which is why I immediately thought of it when I saw yours.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
paCpb.pdf