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 7:32 pm
All times are UTC + 2

View posts since last visit
View unanswered posts

E 16

Post new topic Reply to topic

Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Primes and Composite Numbers

2 Posts • Page 1 of 1

Author

Message

Peter
Birch & Swinnerton Dyer

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

E 16
MM, Problem 1392, George Andrews

Prove that for any prime $p$ in the interval $\left]n, \frac{4n}{3}\right]$ , $p$ divides $\sum^{n}_{j=0}{{n}\choose{j}}^{4}.$

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: E 16
MM, Problem 1392, George Andrews

EDIT: An edited and extended (Theorem 1 generalized even further, Theorem 5 extended and proved anew) version of the below solution can be found here:
http://projectpen.files.wordpress.com/2009/04/pen-e16.pdf
or here:
http://www.cip.ifi.lmu.de/~grinberg/pene16.pdf

Peter wrote:

Prove that for any prime $p$ in the interval $\left]n, \frac {4n}{3}\right]$ , $p$ divides
$\sum^{n}_{j = 0}{{n}\choose{j}}^{4}.$

Nice and instructive problem. Let's generalize:

Theorem 1. If $n$ and $k$ are positive integers and $p$ is a prime such that $\frac {2k - 1}{2k}\left(p - 1\right) < n < p$ , then $p\mid\sum_{j = 0}^{n}\binom{n}{j}^{2k}$ .

Before we prove this, we first show some basic facts about binomial coefficients and remainders modulo primes.

Definition. The binomial coefficient $\binom{x}{u}$ is defined for all reals $x$ and for all integers $u$ as follows: $\binom{x}{u} = \frac {x\cdot\left(x - 1\right)\cdot ...\cdot\left(x - u + 1\right)}{u!}$ if $u$ is a positive integer, $\binom{x}{0} = 1$ , and $\binom{x}{u} = 0$ if $u$ is a negative integer.

Theorem 2, the upper negation identity. If $n$ is a real, and $r$ is an integer, then $\binom{ - n}{r} = \left( - 1\right)^{r}\binom{n + r - 1}{r}$ .

Proof of Theorem 2. We will only consider the case of $r$ being positive (the other cases are trivial). Then, using the definition of binomial coefficients,

$\binom{ - n}{r} = \frac {\left( - n\right)\cdot\left( - n - 1\right)\cdot ...\cdot\left( - n - r + 1\right)}{r!} = \left( - 1...$
$= \left( - 1\right)^{r}\cdot\frac {\left(n + r - 1\right)\cdot ...\cdot\left(n + 1\right)\cdot n}{r!} = \left( - 1\right)^{r}...$ .

This proves Theorem 2.

Theorem 3. If $p$ is a prime, if $u$ and $v$ are two integers such that $u\equiv v\mod p$ , and if $k$ is an integer such that $k < p$ , then $\binom{u}{k}\equiv\binom{v}{k}\mod p$ .

Proof of Theorem 3. If $k\leq 0$ , then $\binom{u}{k} = \binom{v}{k}$ , so that Theorem 3 is trivial. Thus, it remains to consider the case $k > 0$ only. In this case, $k!$ is coprime with $p$ (since $k! = 1\cdot 2\cdot ...\cdot k$ , and all numbers $1$ , $2$ , ..., $k$ are coprime with $p$ , since $p$ is a prime and $k < p$ ).

Now, $u\equiv v\mod p$ yields

$k!\cdot\binom{u}{k} = k!\cdot\frac {u\cdot\left(u - 1\right)\cdot ...\cdot\left(u - k + 1\right)}{k!} = u\cdot\left(u - 1\rig...$
$\equiv v\cdot\left(v - 1\right)\cdot ...\cdot\left(v - k + 1\right) = k!\cdot\frac {v\cdot\left(v - 1\right)\cdot ...\cdot\le...$
$= k!\cdot\binom{v}{k}\mod p$ .

Since $k!$ is coprime with $p$ , we can divide this congruence by $k!$ , and thus we get $\binom{u}{k}\equiv\binom{v}{k}\mod p$ . Hence, Theorem 3 is proven.

Finally, a basic property of binomial coefficients:

Theorem 4. For every nonnegative integer $n$ and any integer $k$ , we have $\binom{n}{k} = \binom{n}{n - k}$ .

This is known, but it is important not to forget the condition that $n$ is nonnegative (it is necessary!).

Now to something completely different:

Theorem 5. If $p$ is a prime, and $f$ is a polynomial of degree $< p - 1$ whose coefficients are all integers, then $\sum_{j = 0}^{p - 1}f\left(j\right)\equiv 0\mod p$ .

Proof of Theorem 5. Since $f$ is a polynomial of degree $< p - 1$ whose coefficients are all integers, it can be written in the form $f\left(X\right) = \sum_{i = 0}^{p - 2}f_{i}X^{i}$ with $f_{i}$ being an integer (not necessarily nonzero) for every $i\in\left\{0;\;1;\;...;\;p - 3;\;p - 2\right\}$ .

Hence,

$\sum_{j = 0}^{p - 1}f\left(j\right) = \sum_{j = 0}^{p - 1}\sum_{i = 0}^{p - 2}f_{i}j^{i} = \sum_{i = 0}^{p - 2}f_{i}\cdot\sum...$ .

But for every $i\in\left\{0;\;1;\;...;\;p - 3;\;p - 2\right\}$ , we have $\sum_{j = 0}^{p - 1}j^{i}\equiv 0\mod p$ (in fact, for $i = 0$ , this is clear since $\sum_{j = 0}^{p - 1}j^{0} = \sum_{j = 0}^{p - 1}1 = p$ , and for $i\geq 1$ , this is equivalent to $\sum_{j = 1}^{p}j^{i}\equiv 0\mod p$ (since $\sum_{j = 0}^{p - 1}j^{i}\equiv \sum_{j = 1}^{p}j^{i}\mod p$ , because $0^{i}\equiv p^{i}\mod p$ ), what follows from http://www.problem-solving.be/pen/viewtopic.php?t=676 part a) because $p - 1\nmid i$ ). Thus,

$\sum_{j = 0}^{p - 1}f\left(j\right) = \sum_{i = 0}^{p - 2}f_{i}\cdot\sum_{j = 0}^{p - 1}j^{i}\equiv\sum_{i = 0}^{p - 2}f_{i}\...$ ,

and Theorem 5 is proven.

Proof of Theorem 1. We have $p - n - 1\geq 0$ , since $n < p$ yields $n + 1\leq p$ .

Also, $\frac {2k - 1}{2k}\left(p - 1\right) < n$ yields $\left(2k - 1\right)\left(p - 1\right) < 2kn$ , so that $2k\left(p - 1\right) - \left(p - 1\right) < 2kn$ , thus $2k\left(p - 1\right) - 2kn < p - 1$ , or, equivalently, $2k\left(p - n - 1\right) < p - 1$ .

We have to prove that $p\mid\sum_{j = 0}^{n}\binom{n}{j}^{2k}$ . This rewrites as $\sum_{j = 0}^{n}\binom{n}{j}^{2k}\equiv 0\mod p$ . This is equivalent to $\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$ (in fact, since $n < p$ , the two sums $\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}$ and $\sum_{j = 0}^{n}\binom{n}{j}^{2k}$ differ only in some terms $\binom{n}{j}^{2k}$ with indices $j$ in the interval $\left]n;\;p - 1\right]$ , and these terms are zero, so we have $\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k} = \sum_{j = 0}^{n}\binom{n}{j}^{2k}$ ).

For every integer $j$ with $0\leq j < p$ , we have

$\binom{n}{j} = \binom{ - \left( - n\right)}{j} = \left( - 1\right)^{j}\binom{\left( - n\right) + j - 1}{j}$ (after Theorem 2)
$\equiv\left( - 1\right)^{j}\binom{p - n + j - 1}{j}$ (by Theorem 3, since $\left( - n\right) + j - 1\equiv p - n + j - 1\mod p$ and $j < p$ )
$= \left( - 1\right)^{j}\binom{p - n + j - 1}{\left(p - n + j - 1\right) - j}$ (by Theorem 4, since $p - n + j - 1$ is nonnegative, since $p - n - 1\geq 0$ and $j\geq 0$ )
$= \left( - 1\right)^{j}\binom{p - n + j - 1}{p - n - 1}\mod p$ ,

so that

$\binom{n}{j}^{2k}\equiv\left(\left( - 1\right)^{j}\binom{p - n + j - 1}{p - n - 1}\right)^{2k} = \binom{p - n + j - 1}{p - n ...$ (since $2k$ is even).

Therefore,

(1) $\left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv\left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p ...$
$= \sum_{j = 0}^{p - 1}\left(\left(p - n - 1\right)!\cdot\binom{p - n + j - 1}{p - n - 1}\right)^{2k}$
$= \sum_{j = 0}^{p - 1}\left(\left(p - n - 1\right)!\cdot\frac {\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + ...$
$= \sum_{j = 0}^{p - 1}\left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + j - 1\right) - u\right)\right)^{2k}...$ .

Now,

$\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + X - 1\right) - u\right)$

is a polynomial of the variable $X$ whose degree is $p - n - 1$ . Thus,

$\left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + X - 1\right) - u\right)\right)^{2k}$

is a polynomial of the variable $X$ whose degree is $2k\left(p - n - 1\right)$ . Since $2k\left(p - n - 1\right) < p - 1$ , it is therefore a polynomial of degree $< p - 1$ . Since the coefficients of this polynomial are all integers, Theorem 5 thus yields

$\sum_{j = 0}^{p - 1}\left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + j - 1\right) - u\right)\right)^{2k}\e...$ .

Using (1), this becomes

$\left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$ .

Now, $\left(p - n - 1\right)!$ is coprime with $p$ (since $\left(p - n - 1\right)! = 1\cdot 2\cdot ...\cdot\left(p - n - 1\right)$ , and all numbers $1$ , $2$ , ..., $p - n - 1$ are coprime with $p$ because $p$ is a prime and $p - n - 1 < p$ ). Hence, we can divide this congruence by $\left(p - n - 1\right)!^{2k}$ , and obtain $\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$ . As we said, this proves Theorem 1.

Darij

Posted: Fri May 25, 2007 2:24 am

Profile PM WWW

2 Posts • Page 1 of 1

Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Primes and Composite Numbers

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