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

The time now is Tue Feb 09, 2010 5:47 pm
All times are UTC + 2		 View posts since last visit
View unanswered posts
A 32
View previous topicView next topic
Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory
 
 
5 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 32
IMO 1979/1
Let a and b be natural numbers such that
\frac{a}{b}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots-\frac{1}{1318}+\frac{1}{1319}.
Prove that a is divisible by 1979.

PostPosted: Fri May 25, 2007 2:24 am
Last edited by Peter on Wed Jul 11, 2007 1:06 am; edited 1 time in total
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
#2
Re: A 32
IMO 1979/1
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.

Note that 1979 is a prime (I am wondering whether the IMO contestants had to check that by hand or they were supposed to know that). We are going to prove v_{1979}\left(\frac {a}{b}\right)\geq 1, because this will yield v_{1979}\left(a\right) = v_{1979}\left(\frac {a}{b}\cdot b\right) = \underbrace{v_{1979}\left(\frac {a}{b}\right)}_{\geq 1} +..., so that 1979\mid a, and thus the problem will be solved.

In order to prove that v_{1979}\left(\frac {a}{b}\right)\geq 1, we note that \frac {a}{b} = 1 - \frac {1}{2} + \frac {1}{3} - \frac {1}{4} + \cdots - \frac {1}{1318} + \frac {1}{1319} = \sum_{i = 1}^{\l..., so we have to show that v_{1979}\left(\sum_{i = 1}^{\left\lfloor 2\cdot 1979/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}\right)\geq 1. This is a particular case (p = 1979) of the following theorem:

Theorem 1. Let p be a prime such that p > 3. Then, v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}\right)\geq 1.

Proof of Theorem 1. First we prove that

(1) p - \left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor = \left\lfloor 2p/3\right\rfloor + 1.

In fact, since p is a prime and p > 3, we have 3\nmid p. Thus, either p\equiv 1\mod 3 or p\equiv 2\mod 3.

If p\equiv 1\mod 3, then \frac {p - 1}{3}\in\mathbb{Z}, so that \left\lfloor\frac {2p}{3}\right\rfloor = 2\cdot\frac {p - 1}{3} (since 2\cdot\frac {p - 1}{3}\in\mathbb{Z} (because \frac {p - 1}{3}\in\mathbb{Z}) and 2\cdot\frac {p - 1}{3}\leq\frac {2p}{3} < 2\cdot\frac {p - 1}{3} + 1) and therefore \left\lfloor\left\lfloor\frac {2p}{3}\right\rfloor /2\right\rfloor = \frac {p - 1}{3} (since \left\lfloor\frac {2p}{3}\right\rfloor /2 = \left(2\cdot\frac {p - 1}{3}\right)/2 = \frac {p - 1}{3} and \frac {p - 1}{3}\in\mathbb{Z}), so that

p - \left\lfloor\left\lfloor\frac {2p}{3}\right\rfloor /2\right\rfloor = p - \frac {p - 1}{3} = 2\cdot\frac {p - 1}{3} + 1 = ...,

and therefore (1) is proven for the case p\equiv 1\mod 3.

If p\equiv 2\mod 3, then \frac {p - 2}{3}\in\mathbb{Z}, so that \left\lfloor\frac {2p}{3}\right\rfloor = 2\cdot\frac {p - 2}{3} + 1 (since 2\cdot\frac {p - 2}{3} + 1\in\mathbb{Z} (because \frac {p - 2}{3}\in\mathbb{Z}) and 2\cdot\frac {p - 2}{3} + 1\leq\frac {2p}{3} < \left(2\cdot\frac {p - 2}{3} + 1\right) + 1) and therefore \left\lfloor\left\lfloor\frac {2p}{3}\right\rfloor /2\right\rfloor = \frac {p - 2}{3} (since \left\lfloor\frac {2p}{3}\right\rfloor /2 = \left(2\cdot\frac {p - 2}{3} + 1\right)/2 = \frac {p - 2}{3} + \frac {1}{2} and \frac {p - 2}{3}\in\mathbb{Z}), so that

p - \left\lfloor\left\lfloor\frac {2p}{3}\right\rfloor /2\right\rfloor = p - \frac {p - 2}{3} = \left(2\cdot\frac {p - 2}{3} ...,

and therefore (1) is proven for the case p\equiv 2\mod 3.

Hence, (1) is proven in both possible cases, and we can step to the actual proof of Theorem 1.

We work with fractions modulo p, noting that we can divide by every i\in\left\{1;\;2;\;...;\;p - 1\right\} modulo p. Obviously,

\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i} = \sum_{\substack{1\leq i\leq \left\lfloor ...
= \sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ; \\ i\text{ is odd}}}\frac {1}{i} + \sum_{\substack{1\leq i\leq...
= \left(\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ; \\ i\text{ is odd}}}\frac {1}{i} + \sum_{\substack{1\leq...
= \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i} - 2\sum_{j = 1}^{\left\lfloor \left\lfloor 2p/3\right\rfloor /2\r....
\equiv\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i} + \sum_{j = 1}^{\left\lfloor \left\lfloor 2p/3\right\rfloor /...
= \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i} + \sum_{i = p - \left\lfloor \left\lfloor 2p/3\right\rfloor /2\ri... (here we substituted j by p - i in the second sum)
= \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i} + \sum_{i = \left\lfloor 2p/3\right\rfloor + 1}^{p - 1}\frac {1}{... (by (1))
= \sum_{i = 1}^{p - 1}\frac {1}{i}\mod p.

Now, \sum_{i = 1}^{p - 1}\frac {1}{i}\equiv 0\mod p, as can be shown in different ways - e. g. as follows:

\sum_{i = 1}^{p - 1}\frac {1}{i} = \frac12\cdot\left(\sum_{i = 1}^{p - 1}\frac {1}{i} + \sum_{i = 1}^{p - 1}\frac {1}{i}\righ...
= \frac12\cdot\left(\sum_{i = 1}^{p - 1}\frac {1}{i} + \sum_{i = 1}^{p - 1}\frac {1}{p - i}\right) (here we substituted i by p - i in the second sum)
= \frac12\cdot\sum_{i = 1}^{p - 1}\left(\frac {1}{i} + \frac {1}{p - i}\right)\equiv\frac12\cdot\sum_{i = 1}^{p - 1}\left(\fr...;

hereby, we were allowed to divide by 2 because 2\not\equiv 0\mod p (since p > 3). Thus,

\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}\equiv \sum_{i = 1}^{p - 1}\frac {1}{i}\equi...,

so that v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}\right)\geq 1, and Theorem 1 is proven.

Darij

PostPosted: Fri May 25, 2007 2:24 am
Last edited by darij grinberg on Tue Mar 25, 2008 7:16 pm; edited 1 time in total
Euler-ls
P versus NP
P versus NP

Offline
Joined: 10 Jan 2006
Posts: 46
Location: Seoul
To rate posts you must be logged in
#3
Re: A 32 (another solution)
IMO 1979/1
1979 is prime.
1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots-\frac{1}{1318}+\frac{1}{1319}#=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\fra...
(where c, d are relative prime.)

Because c is not multiple of 1979, 1979 \mid a
_________________
L.S.H.

PostPosted: Wed Jul 25, 2007 5:26 pm
manjil
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 29 Jun 2008
Posts: 255
Location: Tezpur
India
To rate posts you must be logged in
#4
Generalisation!
The generalisation of the above is : Let p be a prime greater than 3, and q=[\frac{2p}{3}] where [x] is the greatest integer function.Let m and n be positive integers such that\frac{m}{n}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}.....+(-1)^{q-1}\frac{1}{q}. then m is divisible by p.
_________________
Manjil P. Saikia

PostPosted: Thu Aug 14, 2008 6:26 pm
Zhero
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 18 Nov 2007
Posts: 641
Location: NJ
ChinaUnited States
To rate posts you must be logged in
#5
Just an observation: if I'm not mistaken, this problem (and manjil's generalization) is a direct consequence A 24. Why?

First, I claim that when 0 \leq k < p, {p - 1 \choose k} \equiv (-1)^k \mbox{ mod p}. If k = 0, this is obvious. Otherwise, this is a consequence of the fact that \binom{p - 1}{k} = \frac{(p-1) \cdot (p-2) \cdot \ldots \cdot (p-(k+1)}{k \cdot (k-1) \cdot \ldots \cdot 1}; taking the numerator mod p and cancelling wtih the denominator, our result follows easily.

Next, observe that p \binom{p - 1}{k-1} = k\binom{p}{k}; this is a trivial consequence of the definition of \binom{n}{k}. Rearranging, we see that \frac{\binom{p-1}{k-1}}{k} = \frac{\binom{p}{k}}{p}.

Now, let p be a prime and q = \lfloor \frac{2p}{3} \rfloor. We wish to show that 1 - \frac{1}{2} + \frac{1}{3} \ldots + (-1)^{q-1} \frac{1}{q} is 0 mod p, where \frac{1}{n} is taken to be the inverse of n modulo p. Our sum is

\sum_{k = 0}^q (-1)^k \frac{1}{k} \equiv \sum_{k = 0}^q \frac{\binom{p-1}{k-1}}{k} \equiv \sum_{k=0}^q \frac{{n \choose k}}{p.... However, by problem A 24, \sum_{k=0}^q {n \choose k} \equiv 0 \mbox{ mod } p^2, so \sum_{k=0}^q \frac{{n \choose k}}{p} \equiv 0 \mbox{ mod } p, as desired.

[Clearly, we may also go in reverse and use this generalization to solve problem A 24.]
_________________
AAST 2012

PostPosted: Fri Sep 04, 2009 5:50 am
Display posts from previous:   Sort by:   
5 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