LOGIN/REGISTER
Please Wait...
It is currently Sep 02, 2010, 11:44 am
Post new topic Reply to topic  Page 1 of 1
  [ 7 posts ]  Share: Facebook
Author Message
Peter
Birch & Swinnerton Dyer
User avatar

Posts: 5245
Location: Ghent
Belgium
Post Posted: May 24, 2007, 5:24 pm • # 1 


Let p>3 is a prime number and k=\lfloor\frac{2p}{3}\rfloor. Prove that {p \choose 1}+{p \choose 2}+\cdots+{p \choose k} is divisible by p^{2}.
 
 
darij grinberg
Birch & Swinnerton Dyer
User avatar

Posts: 5937
Location: Karlsruhe / Munich
Post Posted: May 24, 2007, 5:24 pm • # 2 


Peter wrote:
Let p > 3 is a prime number and k = \lfloor\frac {2p}{3}\rfloor. Prove that
{p \choose 1} + {p \choose 2} + \cdots + {p \choose k}
is divisible by p^{2}.


I will assume paragraphs 1. and 2. of http://www.artofproblemsolving.com/Forum/viewtopic.php?t=150391 (or http://www.problem-solving.be/pen/viewtopic.php?t=25 ) post #4 as known.

We have to prove that p^{2}\mid\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}.

In http://www.artofproblemsolving.com/Forum/viewtopic.php?t=150400 (or http://www.problem-solving.be/pen/viewtopic.php?t=34 ) post #2, Theorem 1, I showed that v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}\right)\geq 1. This rewrites as \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}\equiv 0\mod p, where we are working with fractions modulo p (what is allowed in our case because the denominators are integers i satisfying 1\leq i\leq\left\lfloor 2p/3\right\rfloor, and these integers are not divisible by p). In other words, \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\left( - 1\right)^{i - 1}\equiv 0\mod p.

Now we prove a simple lemma:

Lemma 1. If p is a prime and i is an integer satisfying 0\leq i\leq p - 1, then \binom{p - 1}{i}\equiv\left( - 1\right)^{i}\mod p.

Proof of Lemma 1. We have \binom{p - 1}{i} = \frac {\left(p - 1\right)\cdot\left(p - 2\right)\cdot ...\cdot\left(p - i\right)}{i!}, and thus

i!\cdot\binom{p - 1}{i} = \left(p - 1\right)\cdot\left(p - 2\right)\cdot ...\cdot\left(p - i\right)\equiv\left( - 1\right)\cd...
= \left( - 1\right)^{i}\cdot\left(1\cdot 2\cdot ...\cdot i\right) = \left( - 1\right)^{i}\cdot i!\mod p.

Now, i! is coprime with p (since i! = 1\cdot 2\cdot ...\cdot i, and all the numbers 1, 2, ..., i are coprime with p since p is a prime and i < p); hence, we can divide this congruence by i!, and obtain \binom{p - 1}{i}\equiv\left( - 1\right)^{i}\mod p. Lemma 1 is proven.

Now, for every integer i satisfying 1\leq i\leq\left\lfloor 2p/3\right\rfloor, Lemma 1 yields \binom{p - 1}{i - 1}\equiv\left( - 1\right)^{i - 1}\mod p, so that \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\left( - 1\right)^{i - 1}\equiv 0\mod p becomes \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\equiv 0\mod p. In other words,

v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\right)\geq 1.

Together with v_{p}\left(p\right) = 1, this yields

v_{p}\left(p\cdot\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\right) = v_{p}\left(p\right) +....

But

p\cdot\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1} = p\cdot\sum_{i = 1}^{\left\lfloor 2p/3\r...
= \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {p\cdot\left(p - 1\right)!}{\left(i\cdot\left(i - 1\right)!\right)\cdot\....

Hence, we get v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}\right)\geq 2. Since \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i} is an integer, this means p^{2}\mid \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}, qed.

Note that this problem also appeared as question 2 in the 11th Annual Vojtech Jarnik International Mathematical Competition 2001, Category I. See also http://www.artofproblemsolving.com/Forum/viewtopic.php?t=151379 .

Darij


Last edited by darij grinberg on Jan 17, 2009, 2:55 pm, edited 3 times in total.
 
 
ricardokaka
Hodge Conjecture

Posts: 84
Post Posted: Nov 19, 2007, 10:17 pm • # 3 


Where's the lemma no 2? :D, Mr darij grinberg?
 
 
ricardokaka
Hodge Conjecture

Posts: 84
Post Posted: Nov 20, 2007, 8:20 am • # 4 


We haven't any exact and simple solutions, example: the Darij's solution! I think that this isn't a hard problem and we can solve it more simply and purer! I cann't understand the termes, example: "p-ardic"... Help me, please!
 
 
Peter
Birch & Swinnerton Dyer
User avatar

Posts: 5245
Location: Ghent
Belgium
Post Posted: Nov 20, 2007, 7:31 pm • # 5 


ricardokaka wrote:
I think that this isn't a hard problem and we can solve it more simply and purer!
Then post your solution, please! :)

I also believe p-adic numbers can be avoided.

_________________
Boo!
 
 
ZetaX
Birch & Swinnerton Dyer
User avatar

Posts: 6340
Location: München
Germany
Post Posted: Nov 21, 2007, 11:39 am • # 6 


Sorry, but p-adic numbers were never used in any of the proofs (even not in the linked ones).

_________________
IMO Shortlist 2010 revealed!
 
 
Rust
Birch & Swinnerton Dyer

Posts: 3853
Post Posted: Nov 24, 2007, 9:20 am • # 7 


darij grinberg wrote:
Now, for every integer i satisfying 1\leq i\leq\left\lfloor 2p/3\right\rfloor, Lemma 1 yields \binom{p - 1}{i - 1}\equiv\left( - 1\right)^{i - 1}\mod p, so that \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\left( - 1\right)^{i - 1}\equiv 0\mod p becomes \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\equiv 0\mod p. In other words,
Darij

I don't see prove. I give full solution at least 2 times.
Let S(a,b)=\sum_{a<i<b}\frac 1i \mod p. Then
\sum_{0<i<2p/3}\frac{(-1)^{i-1}}{i}=\sum_{0<i<2p/3, i-odd}\frac 1i -\frac 12 S(0,\frac p3) =-\sum_{p/3<i<p,...
Let S_i=S(\frac{ip}{6},\frac{(i+1)p}{6})\mod p,i=0,1,2,3,4,5. Obviosly S_i+S_{5-i}=0.
Consider
T_a=\frac{a^{p-1}-1}{p}\sum_{x=1}^{p-1}x^{p-1}=\frac 1p \sum_{x=1}^{p-1}(ax)^{p-1}-x^{p-1}=\sum_{j=1}^{p-1}j(p-1)\sum_{jp/a&l...
It give \sum_{i=0}^{[(a-2)/2]}(a-1-2i)S_{i,a}=aT_a\mod p, were S_{i,a}=\sum_{ip/a<x<(i+1)p/a}\frac 1x \mod p.
Because T_6=T_2+T_3, we get
5S_0+3S_1+S_2-3(S_0+S_1+S_2)-2(2S_0+2S_1)=6T_6-3*(2T_2)-2*(3T_3)=0\mod p.
It give 0=S_0+2S_1+S_2=S(\frac p6,\frac p2 )+S(0,\frac p3 )\mod p
 
 
Display posts from previous:  Sort by  
  Share on Facebook Previous topic | Next topic 

Community » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory

All times are UTC - 8 hours [ DST ]
Share: Facebook
Post new topic Reply to topic  Page 1 of 1
  [ 7 posts ] 

Login
Username:   Password:   Log me on automatically each visit  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Articles
Want to know what we think? We've written lots of articles to tell you! Learn our advice, our recommendations, and our innermost thoughts.
Alcumus
Art of Problem Solving's FREE innovative online learning system. Over 3,500 problems and solutions!