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$.
Problem
Source:
Tags: floor function, Divisibility Theory
25.05.2007 03:24
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} + \underbrace{v_{1979}\left(b\right)}_{\geq 0\text{, since }b\text{ is an integer}}\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}^{\left\lfloor 2\cdot 1979/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}$, 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 = \left\lfloor\frac {2p}{3}\right\rfloor + 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} + 1\right) + 1 = \left\lfloor\frac {2p}{3}\right\rfloor + 1$, 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 2p/3\right\rfloor ; \\ i\text{ is odd}}}\frac {\left( - 1\right)^{i - 1}}{i} + \sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ; \\ i\text{ is even}}}\frac {\left( - 1\right)^{i - 1}}{i}$ $ = \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\lfloor 2p/3\right\rfloor ; \\ i\text{ is even}}}\frac { - 1}{i} = \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\lfloor 2p/3\right\rfloor ; \\ i\text{ is even}}}\frac {1}{i}$ $ = \left(\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\lfloor 2p/3\right\rfloor ; \\ i\text{ is even}}}\frac {1}{i}\right) - 2\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ; \\ i\text{ is even}}}\frac {1}{i} = \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i} - 2\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ; \\ i\text{ is even}}}\frac {1}{i}$ $ = \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\right\rfloor}\frac {1}{2j} = \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i} + \sum_{j = 1}^{\left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor}\frac {1}{ - j}$. $ \equiv\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i} + \sum_{j = 1}^{\left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor}\frac {1}{p - j}$ $ = \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i} + \sum_{i = p - \left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor}^{p - 1}\frac {1}{i}$ (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}{i}$ (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}\right)$ $ = \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(\frac {1}{i} + \frac {1}{ - i}\right) = \frac12\cdot\sum_{i = 1}^{p - 1}0 = 0\mod p$; 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}\equiv 0\mod p$, 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
25.07.2007 18:26
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+\frac{1}{1318}+\frac{1}{1319}-2(\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{1318}) \#=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{1318}+\frac{1}{1319}-(1+\frac{1}{2}+\cdots+\frac{1}{659})\#=\frac{1}{660}+\frac{1}{661}+\cdots+\frac{1}{1319}\#=(\frac{1}{660}+\frac{1}{1319})+(\frac{1}{661}+\frac{1}{1318}) \cdots+( \frac{1}{989}+\frac{1}{990}) =1979 \frac{d}{c}$ (where $ c, d$ are relative prime.) Because $ c$ is not multiple of 1979, $ 1979 \mid a$
14.08.2008 19:26
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$.
04.09.2009 06:50
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} \mbox{ mod } 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.]
04.05.2022 14:30
We don't need generalizations https://artofproblemsolving.com/community/c6h61006p367332