MathLinks Forum LaTeX Help AoPS Classes Books Classroom MathLinks Contest Math Resources

The time now is Tue Feb 09, 2010 6:59 pm
All times are UTC + 2		 View posts since last visit
View unanswered posts
A 23
View previous topicView next 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
Birch & Swinnerton Dyer


Offline
Joined: 05 May 2004
Posts: 5214
Location: Ghent
Belgium
To rate posts you must be logged in
#1
A 23
[GhEw pp.104]
(Wolstenholme's Theorem) Prove that if 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1} is expressed as a fraction, where p \ge 5 is a prime, then p^{2} divides the numerator.

PostPosted: Fri May 25, 2007 2:24 am
TomciO
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 22 May 2005
Posts: 523
Location: Poland, Cracow.
Poland
To rate posts you must be logged in
#2
We will treat rational numbers, which have their denominator relatively prime to p, as residues mod p.
From the Fermat's Little Theorem: \frac{1}{i} \equiv i^{p-2} \mod{p}
So we see that:
\sum_{i=1}^{p-1} \frac{1}{i} \equiv \sum_{i=1}^{p-1} i^{p-2} = \sum_{i=1}^{\frac{p-1}{2}} i^{p-2} + (p-i)^{p-2} \equiv \sum_{...
The last congruence comes from the fact that the rest term vanishes mod p^2. We are left with proving that:
\sum_{i=1}^{\frac{p-1}{2}} i^{p-3} \equiv 0 \mod{p}
or (one more time from FTL):
\sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i^2} \equiv 0 \mod{p}
Now if i, j \leq \frac{p-1}{2} and \frac{1}{i^2} \equiv \frac{1}{j^2} \mod{p} then also (i-j)(i+j) \equiv 0 \mod{p} but since i, j \leq \frac{p-1}{2} we must have i=j. So the numbers: \frac{1}{i^2} for i=1,2,...,\frac{p-1}{2} are all different quadratic residues (and there are exactly \frac{p-1}{2} quadratic residues), as well as the numbers i^2 for i=1,2,...,\frac{p-1}{2} so:
\sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i^2} \equiv \sum_{i=1}^{\frac{p-1}{2}} i^2 = \frac{p(p-1)(p+1)}{24} \equiv 0 \mod{p}
which ends the proof.

PostPosted: Fri May 25, 2007 2:24 am
Ilthigore
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 31 Dec 2005
Posts: 305
Location: Bristol, UK
United Kingdom
To rate posts you must be logged in
#3
I love it. This is a beautiful proof.

PostPosted: Fri May 25, 2007 2:24 am
darij grinberg
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 10 Feb 2004
Posts: 5806
Location: Karlsruhe / Munich
To rate posts you must be logged in
#4
Re: A 23
[GhEw pp.104]
Peter wrote:
(Wolstenholme's Theorem) Prove that if
1 + \frac {1}{2} + \frac {1}{3} + \cdots + \frac {1}{p - 1}
is expressed as a fraction, where p \ge 5 is a prime, then p^{2} divides the numerator.


This is an updated version of an older MathLinks post of mine, and I am submitting it here since I will refer to it in a number of other proofs.

I will generalize the problem, but first I explain some preliminaries about primes.

1. p-adic evaluation

Let p be an arbitrary prime. We denote by \mathbb{Z}_{p} the field of residues of integers modulo p.

For any rational number x, we will now define a so-called p-adic evaluation of x. This evaluation will be denoted by v_{p}\left(x\right), and it is defined as follows: If x\neq 0, then v_{p}\left(x\right) is the greatest integer k such that \frac {x}{p^{k}} can be written as a fraction of two integers with the denominator not being divisible by p. Besides, we set v_{p}\left(0\right) = + \infty, where + \infty is just a symbol satisfying + \infty > a and + \infty + a = + \infty for any integer a (what we will mainly need is that v_{p}\left(0\right) > v_{p}\left(x\right) for any nonzero x).

We can easily see how to compute v_{p}\left(x\right) for rationals x\neq 0:
If x is a nonzero integer, then v_{p}\left(x\right) is the greatest integer k such that p^{k} divides x (particularly, v_{p}\left(x\right) = 0 if p doesn't divide x); if x is a fraction of two nonzero integers, say x = \frac {a}{b} with integers a and b, then v_{p}\left(x\right) = v_{p}\left(a\right) - v_{p}\left(b\right).

Note that there is a simple way to interpret the sign of the p-adic evaluation v_{p}\left(x\right) of a rational number x: If we write x as a reduced fraction (i. e. a fraction with numerator and denominator coprime; if x is an integer, then just write it in the form x = \frac {x}{1}), and it turns out that the numerator is divisible by p, then v_{p}\left(x\right) > 0; if neither the numerator nor the denominator is divisible by p, then v_{p}\left(x\right) = 0; if the denominator is divisible by p, then v_{p}\left(x\right) < 0.

It is rather easy to prove that for any two rational numbers x and y, we have v_{p}\left(xy\right) = v_{p}\left(x\right) + v_{p}\left(y\right) and v_{p}\left(x + y\right)\geq\min\left(v_{p}\left(x\right);\;v_{p}\left(y\right)\right).

2. Working with fractions modulo p

We will also need some familiarity with fractions in \mathbb{Z}_{p}. The main idea is to extend the notion of congruence modulo p from integers to rational numbers with nonnegative p-adic evaluation: If x and y are two rational numbers such that v_{p}\left(x\right)\geq 0 and v_{p}\left(y\right)\geq 0, then we say that x\equiv y\mod p if and only if v_{p}\left(x - y\right) > 0. Thus we have defined an equivalence relation (that it is an equivalence relation is easy to prove - do it for yourself) on the set of all rational numbers with nonnegative p-adic evaluation. Now one could expect that, in this way, we would obtain a kind of new group of remainders, say \mathbb{Q}_{p} - but in fact, we get nothing but our old familiar \mathbb{Z}_{p}, since for every rational number x, there is one and only one integer n satisfying 0\leq n < p such that x\equiv n\mod p (this is again easy to prove). Hence, you can work with rational numbers whose p-adic evaluation is nonnegative in the same way as you work with remainders modulo p. This also means that modulo p, you can uniquely divide by any integer not divisible by p. [A nice application of this is problem 4 of the IMO 2005 - see Fedor Petrov's proof in post #2.]

3. Generalization of Wolstenholme's Theorem

Now, the problem A 23 asks us to show that if p is a prime number such that p\geq 5, then v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k}\right)\geq 2. This is a particular case (namely, the u = 1 case) of the following result:

Theorem 1. If p is a prime number and u is an odd integer such that p\geq u + 3 and u\geq 0, then

v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2.

Proof of Theorem 1. We will first work in \mathbb{Q} and only later come over into \mathbb{Z}_{p}. Note that p > 2 (since p\geq u + 3 and u\geq 0). We start with the Gauss trick:

2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {1}{k^{u}} + \sum_{k = 1}^{p - 1}\frac {1}{\left(p - k\righ....

Now denote s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i} for every k\in\left\{1,2,...,p-1\right\}. Obviously, s_k is an integer for every k. We can expand \left(p - k\right)^{u} according to the binomial formula:

\left(p - k\right)^{u}=\sum_{i=0}^u\left(-1\right)^{u-i}\binom{u}{i}p^ik^{u-i}
=\left(-1\right)^{u-0}\binom{u}{0}p^0k^{u-0}+\left(-1\right)^{u-1}\binom{u}{1}p^1k^{u-1}+\sum_{i=2}^u\left(-1\right)^{u-i}\bi...
=\left(-1\right)^uk^u+\left(-1\right)^{u-1}upk^{u-1}+p^2\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}
=\left(-1\right)^uk^u+\left(-1\right)^{u-1}upk^{u-1}+p^2s_k=\left(-1\right)k^u+1upk^{u-1}+p^2s_k (since u is odd, so that \left(-1\right)^u=-1 and \left(-1\right)^{u-1}=1)
=-k^u+upk^{u-1}+p^2s_k.

Thus, k^u+\left(p-k\right)^u = upk^{u-1}+p^2s_k for every k\in\left\{1,2,...,p-1\right\}, and therefore

2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {k^{u} + \left(p - k\right)^{u}}{k^{u}\left(p - k\right)^{u...
= p \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}.

But since 2 isn't divisible by p (since p > 2), we have v_{p}\left(2\right) = 0, so that

v_{p}\left(2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = \underbrace{v_{p}\left(2\right)}_{=0} + v_{p}\left(\sum_{k = 1}^{p ....

On the other hand,

v_{p}\left(2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left( p \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left...
= 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right).

Thus,

v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\lef....

Hence, instead of showing v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2, it will be enough to prove v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)\geq 1. This is equivalent to v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) > 0, i. e. to \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv 0\mod p. Now we start working in \mathbb{Z}_{p}. In fact, for every k\in\left\{1,2,...,p-1\right\}, we can consider the fraction \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} in \mathbb{Z}_{p}, since it has a nonnegative p-adic evaluation (because its denominator, k^{u}\left(p - k\right)^{u}, is not divisible by p, since 1\leq k\leq p - 1 and since p is a prime). Modulo p, the numerator uk^{u-1}+ps_k of this fraction can be simplified to uk^{u - 1} (since p\equiv 0\mod p, and thus all terms containing p can be omitted). Also, the denominator can be simplified: Since p - k\equiv - k\mod p, we have k^{u}\left(p - k\right)^{u}\equiv k^{u}\left( - k\right)^{u} = \left( - 1\right)^{u}k^{2u} \mod p. Hence, \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv \frac {uk^{u-1}}{\left(-1\right)^u k^{2u}}\mod p. Therefore,

(1) \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\sum_{k = 1}^{p - 1}\frac {uk^{u - 1}}{\left( - ....

But by Fermat's small theorem, k^{p - 1}\equiv 1\mod p for every integer k such that 1\leq k\leq p - 1. Thus, k^{ - u - 1}\equiv k^{ - u - 1}k^{p - 1} = k^{p - u - 2}\mod p, and the relation (1) becomes

\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p ....

Now, p - u - 2\geq 1 (since p\geq u + 3) and p - u - 2\leq p - 2. Also, p is an odd prime (since p is a prime and p > 2). Now, according to http://www.problem-solving.be/pen/viewtopic.php?t=676 part a) (and also http://www.mathlinks.ro/Forum/viewtopic.php?t=40171 ), we have:

Theorem 2. If p is an odd prime and \rho is an integer such that 1\leq\rho\leq p - 2, then p\mid\sum_{k = 1}^{p - 1}k^{\rho}.

Applying this Theorem 2 to our prime p and \rho = p - u - 2 (we know that p is an odd prime and \rho = p - u - 2 satisfies 1\leq p - u - 2\leq p - 2), we get p\mid\sum_{k = 1}^{p - 1}k^{p - u - 2}, so that \sum_{k = 1}^{p - 1}k^{p - u - 2}\equiv 0\mod p, and thus

\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\frac {u}{\left( - 1\right)^{u}} \underbrace{\su....

This completes the proof of Theorem 1.

4. A divisibility by p^3

We can use almost the same tactics to prove a similar result:

Theorem 3. If p is a prime number such that p>3, then

v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)\geq 3.

Proof of Theorem 3. It is known that for every integer i such that 0<i<p, we have p\mid \binom{p}{i} (since p is prime); in other words, \binom{p}{i}\equiv 0\mod p.

Besides, p-2>0 (since p>3>2).

Set u=p. Also, denote s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i} for every k\in\left\{1,2,...,p-1\right\}. Obviously, s_k is an integer for every k. Then, every k\in\left\{1,2,...,p-1\right\} satisfies

s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}=\sum_{i=2}^p\left(-1\right)^{p-i}\binom{p}{i}p^{i-2}k^{p-i} (since u=p)
=\sum_{i=2}^{p-1}\left(-1\right)^{p-i}\underbrace{\binom{p}{i}}_{\substack{\equiv 0\mod p,\\ \text{ since } 0<i<p}}p^{i...
\equiv \underbrace{\sum_{i=2}^{p-1}\left(-1\right)^{p-i}0p^{i-2}k^{p-i}}_{=0}+\underbrace{\left(-1\right)^{p-p}\binom{p}{p}0k....

We will first work in \mathbb{Q} and only later come over into \mathbb{Z}_{p}. Just as in the proof of Theorem 1, we can show that

(2) v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\lef....

Since u=p, we have

v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)

and

v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) = v_{p}\left( \sum_{k = 1}^{p - 1...
= v_{p}\left( p\cdot \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) (since \sum_{k = 1}^{p - 1} \frac {pk^{p-1}+ps_k}{k^p\left(p - k\right)^p} = \sum_{k = 1}^{p - 1} \frac {p\left(k^{p-1}+s_k\right)}{...)
= \underbrace{v_p\left(p\right)}_{=1} + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) =....

Thus, (2) becomes

v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 1 + \left(1 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\l....

In other words,

v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 2 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\....

Hence, instead of showing v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{p}}\right)\geq 3, it will be enough to prove v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)\geq 1. This is equivalent to v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) > 0, i. e. to \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv 0\mod p. Now we start working in \mathbb{Z}_{p}. In fact, for every k\in\left\{1,2,...,p-1\right\}, we can consider the fraction \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} in \mathbb{Z}_{p}, since it has a nonnegative p-adic evaluation (because its denominator, k^p\left(p - k\right)^p, is not divisible by p, since 1\leq k\leq p - 1 and since p is a prime). Modulo p, the numerator k^{p-1}+s_k of this fraction can be simplified to k^{p-1} (since s_k\equiv 0\mod p, and thus the term s_k can be omitted). Also, the denominator can be simplified: Since p - k\equiv - k\mod p, we have k^p\left(p - k\right)^p\equiv k^p\left( - k\right)^p = \left( - 1\right)^pk^{2p} \mod p. Hence, \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac {k^{p-1}}{\left( - 1\right)^pk^{2p}} \mod p. Therefore,

(3) \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \sum_{k = 1}^{p - 1}\frac {k^{p-1}}{\left( - 1\right....

But by Fermat's small theorem, k^p\equiv k\mod p for every integer k. Thus, \left(k^p\right)^2\equiv k^2\mod p, so that k^{2p}=\left(k^p\right)^2\equiv k^2\mod p. Hence, the relation (3) becomes

\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}\und....

Now, p-3\geq 1 (since p>3 yields p-3>0, and p-3\in\mathbb{Z}) and p-3\leq p-2. Also, p is an odd prime (since p is a prime and p > 2). Applying Theorem 2 to our prime p and \rho = p - 3 (we know that p is an odd prime and \rho = p-3 satisfies 1\leq p-3\leq p - 2), we get p\mid\sum_{k = 1}^{p - 1}k^{p - 3}, so that \sum_{k = 1}^{p - 1}k^{p - 3}\equiv 0\mod p, and thus

\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \underbrace{\sum_{k = 1}....

This completes the proof of Theorem 3.

[EDIT: Made the proof of Theorem 1 slightly more formal, and added section 4. See the other thread for the old version of this post.]

Darij

PostPosted: Fri May 25, 2007 2:24 am
Last edited by darij grinberg on Sun Feb 07, 2010 1:57 am; edited 3 times in total
kdano
Hodge Conjecture
Hodge Conjecture

Offline
Joined: 14 Nov 2006
Posts: 87
Location: Budapest, Hungary
Hungary
To rate posts you must be logged in
#5
TomciO wrote:

\sum_{i = 1}^{p - 1} \frac {1}{i} \equiv \sum_{i = 1}^{p - 1} i^{p - 2}


Why is this true mod p^2?

PostPosted: Thu Jul 03, 2008 6:11 pm
TomciO
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 22 May 2005
Posts: 523
Location: Poland, Cracow.
Poland
To rate posts you must be logged in
#6
Yes, you are right. Thank you for pointing out the mistake. I have corrected the proof accordingly since it's not a big difference.

We will treat rational numbers, which have their denominator relatively prime to p, as residues mod p.
From the Euler's Theorem: \frac {1}{i} \equiv i^{p(p-1) - 1} \mod{p^2}
So we see that:
\sum_{i = 1}^{p - 1} \frac {1}{i} \equiv \sum_{i = 1}^{p - 1} i^{p(p-1) - 1} = \sum_{i = 1}^{\frac {p - 1}{2}} i^{p(p-1) - 1}...
The congruence come from the fact that the rest term vanishes mod p^2. We are left with proving that:
\sum_{i = 1}^{\frac {p - 1}{2}} i^{p(p-1) - 2} \equiv 0 \mod{p}
or from FTL:
\sum_{i = 1}^{\frac {p - 1}{2}} \frac {1}{i^2} \equiv 0 \mod{p}
Now if i, j \leq \frac {p - 1}{2} and \frac {1}{i^2} \equiv \frac {1}{j^2} \mod{p} then also (i - j)(i + j) \equiv 0 \mod{p} but since i, j \leq \frac {p - 1}{2} we must have i = j. So the numbers: \frac {1}{i^2} for i = 1,2,...,\frac {p - 1}{2} are all different quadratic residues (and there are exactly \frac {p - 1}{2} quadratic residues), as well as the numbers i^2 for i = 1,2,...,\frac {p - 1}{2} so:
\sum_{i = 1}^{\frac {p - 1}{2}} \frac {1}{i^2} \equiv \sum_{i = 1}^{\frac {p - 1}{2}} i^2 = \frac {p(p - 1)(p + 1)}{24} \equi...
which ends the proof.

PostPosted: Thu Jul 03, 2008 6:40 pm
manjil
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 29 Jun 2008
Posts: 255
Location: Tezpur
India
To rate posts you must be logged in
#7
Fields
Maybe we can use fields to solve this in a more efficient way!
_________________
Manjil P. Saikia

PostPosted: Thu Aug 14, 2008 4:15 am
Display posts from previous:   Sort by:   
7 Posts • Page 1 of 1
Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory
 
View previous topicView next 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