MathLinks :: View topic

Art of Problem Solving \| News \| Galleries \| Blogs \| About \| Home
	$LaTeX Help$

Advanced Section

College Playground

International Mathematical Olympiad

National Forums

Galleries

Memberlist

Usergroups

The time now is Tue Feb 09, 2010 6:40 pm
All times are UTC + 2

View posts since last visit
View unanswered posts

A 24

Post new topic Reply to topic

Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory

7 Posts • Page 1 of 1

Author

Message

Peter
Birch & Swinnerton Dyer

Offline
Joined: 05 May 2004
Posts: 5214
Location: Ghent

A 24
Putnam 1996

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}$ .

Posted: Fri May 25, 2007 2:24 am

Profile PM WWW Album

darij grinberg
Birch & Swinnerton Dyer

Offline
Joined: 10 Feb 2004
Posts: 5806
Location: Karlsruhe / Munich

Re: A 24
Putnam 1996

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.mathlinks.ro/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.mathlinks.ro/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.mathlinks.ro/Forum/viewtopic.php?t=151379 .

Darij

Posted: Fri May 25, 2007 2:24 am
Last edited by darij grinberg on Sat Jan 17, 2009 11:55 pm; edited 3 times in total

Profile PM WWW

ricardokaka
Hodge Conjecture

Offline
Joined: 08 Nov 2007
Posts: 84

Where's the lemma no 2? Mr. Green

, Mr darij grinberg?

Posted: Tue Nov 20, 2007 7:17 am

Profile PM Email

ricardokaka
Hodge Conjecture

Offline
Joined: 08 Nov 2007
Posts: 84

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!

Posted: Tue Nov 20, 2007 5:20 pm

Profile PM Email

Peter
Birch & Swinnerton Dyer

Offline
Joined: 05 May 2004
Posts: 5214
Location: Ghent

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! Smile

I also believe p-adic numbers can be avoided.

_________________
Boo!

Posted: Wed Nov 21, 2007 4:31 am

Profile PM WWW Album

ZetaX
Birch & Swinnerton Dyer

Offline
Joined: 21 Dec 2004
Posts: 6168
Location: München

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

_________________
The one and only place to get next year's IMO problems already now!

Posted: Wed Nov 21, 2007 8:39 pm

Profile PM WWW

Rust
Birch & Swinnerton Dyer

Offline
Joined: 10 Feb 2006
Posts: 3695

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$

Posted: Sat Nov 24, 2007 6:20 pm

Profile PM

7 Posts • Page 1 of 1

Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory

Post new topic Reply to topic

Jump to:

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 vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum

Created and Maintained by Valentin Vornicu - (c) AoPS Inc. 2004-2008