Kvant Math Problem 591
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m40s
Source on kvant.digital
Problem
Let $p$ and $q$ be natural numbers such that $$\frac{p}{q}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\ldots-\frac{1}{1318}+\frac{1}{1319}.$$. Prove that the number $p$ is divisible by 1979.
International Mathematical Olympiad for School Students (XXI, 1979)
Exploration
Let
$$S=1-\frac12+\frac13-\frac14+\cdots-\frac1{1318}+\frac1{1319}.$$
We write $S=\frac pq$ in lowest terms and must prove $1979\mid p$.
The number $1979$ is suspicious because
$$1319=\frac{1979-1}{,?}$$
does not suggest anything immediately. A more relevant observation is
$$1319=\frac{1979-1}{2}+330,$$
which is not useful. Since $1979$ is much larger than $1319$, every denominator occurring in the sum is invertible modulo $1979$. This suggests reducing the sum modulo $1979$.
First check that $1979$ is prime. Since $\sqrt{1979}<45$, it suffices to test divisibility by the primes $2,3,5,7,11,13,17,19,23,29,31,37,41,43$; none divides $1979$. Thus arithmetic modulo $1979$ takes place in a field.
If $S=p/q$ with $(p,q)=1$ and $1979\nmid q$, then $1979\mid p$ is equivalent to $S\equiv0\pmod{1979}$. Since every denominator $1,\dots,1319$ is nonzero modulo $1979$, the denominator $q$ of the reduced fraction cannot be divisible by $1979$. Hence it is enough to prove
$$S\equiv0\pmod{1979}.$$
The alternating harmonic sum can be rewritten as
$$S=\sum_{k=1}^{1319}\frac1k-2\sum_{k=1}^{659}\frac1{2k}.$$
Since $\frac1{2k}=\frac12\frac1k$,
$$S=H_{1319}-H_{659},$$
where $H_n=\sum_{k=1}^n\frac1k$.
Thus
$$S=\sum_{k=660}^{1319}\frac1k.$$
Now the interval $660,\dots,1319$ has length $660$. Since
$$660+1319=1979,$$
the terms pair naturally:
$$k \longleftrightarrow 1979-k.$$
For $660\le k\le1319$, both $k$ and $1979-k$ lie in the same interval. Modulo $1979$,
$$\frac1{1979-k}\equiv -\frac1k.$$
Each pair therefore sums to $0$ modulo $1979$. This should give the result.
The delicate point is justifying rigorously that the interval is exactly partitioned into such pairs and that no fixed point occurs. A fixed point would satisfy $k=1979-k$, hence $2k=1979$, impossible because $1979$ is odd.
Problem Understanding
We are given the alternating harmonic sum
$$1-\frac12+\frac13-\cdots-\frac1{1318}+\frac1{1319}$$
and write it in lowest terms as $p/q$. The task is to prove that the numerator $p$ is divisible by $1979$.
This is a Type B problem, a pure proof.
The core difficulty is to connect the rational number with arithmetic modulo $1979$. Since $1979>1319$, every denominator occurring in the sum is invertible modulo $1979$, allowing the entire sum to be interpreted modulo $1979$. The essential idea is to rewrite the alternating sum as a block of consecutive reciprocals and then pair terms $k$ and $1979-k$.
Proof Architecture
First show that $1979$ is prime; this guarantees that every nonzero residue modulo $1979$ has a multiplicative inverse.
Next rewrite the alternating harmonic sum as $H_{1319}-H_{659}$, where $H_n=\sum_{k=1}^n 1/k$; this simplifies to $\sum_{k=660}^{1319}1/k$.
Then prove that the interval ${660,\dots,1319}$ is invariant under the map $k\mapsto1979-k$ and splits into disjoint pairs ${k,1979-k}$.
Show that for every such pair,
$$\frac1k+\frac1{1979-k}\equiv0\pmod{1979}.$$
Summing over all pairs yields $S\equiv0\pmod{1979}$.
Finally, since the reduced denominator $q$ is not divisible by $1979$, deduce from $p/q\equiv0\pmod{1979}$ that $1979\mid p$.
The step most likely to fail under scrutiny is the passage from the rational number $p/q$ to its residue modulo $1979$, which requires checking that $1979\nmid q$.
Solution
Let
$$S=1-\frac12+\frac13-\frac14+\cdots-\frac1{1318}+\frac1{1319}.$$
Write $S=p/q$ in lowest terms.
Since
$$\sqrt{1979}<45,$$
a direct check shows that none of the primes
$$2,3,5,7,11,13,17,19,23,29,31,37,41,43$$
divides $1979$. Hence $1979$ is prime.
Define
$$H_n=\sum_{k=1}^{n}\frac1k.$$
Separating the even terms in the alternating sum gives
$$S=H_{1319}-2\sum_{k=1}^{659}\frac1{2k}.$$
Since
$$2\sum_{k=1}^{659}\frac1{2k} =\sum_{k=1}^{659}\frac1k =H_{659},$$
we obtain
$$S=H_{1319}-H_{659} =\sum_{k=660}^{1319}\frac1k.$$
Consider this sum modulo $1979$. Every denominator $k$ satisfies
$$1\le k\le1319<1979,$$
so $k\not\equiv0\pmod{1979}$ and therefore has a multiplicative inverse modulo $1979$.
For $660\le k\le1319$,
$$660\le1979-k\le1319.$$
Thus the set ${660,\dots,1319}$ is mapped to itself by $k\mapsto1979-k$.
A fixed point would satisfy
$$k=1979-k,$$
hence $2k=1979$, impossible because $1979$ is odd. Therefore the set splits into disjoint pairs ${k,1979-k}$.
For each pair,
$$1979-k\equiv -k \pmod{1979},$$
so
$$\frac1{1979-k} \equiv \frac1{-k} \equiv -\frac1k \pmod{1979}.$$
Consequently,
$$\frac1k+\frac1{1979-k}\equiv0\pmod{1979}.$$
Summing over all pairs yields
$$S=\sum_{k=660}^{1319}\frac1k\equiv0\pmod{1979}.$$
Now $S=p/q$ in lowest terms. Since every denominator appearing in the original sum is less than $1979$, the denominator $q$ is not divisible by $1979$. Hence $q$ is invertible modulo $1979$. From
$$\frac pq=S\equiv0\pmod{1979}$$
we obtain
$$p\equiv0\pmod{1979}.$$
Therefore $1979\mid p$.
This completes the proof.
∎
Verification of Key Steps
The identity
$$S=H_{1319}-H_{659}$$
comes from
$$S=H_{1319}-2\sum_{k=1}^{659}\frac1{2k}.$$
Replacing $\frac1{2k}$ by $\frac12\cdot\frac1k$ gives
$$2\sum_{k=1}^{659}\frac1{2k} =\sum_{k=1}^{659}\frac1k,$$
hence
$$S=H_{1319}-H_{659}.$$
A common mistake is to forget the factor $2$.
The pairing argument depends on the interval exactly. If $660\le k\le1319$, then
$$1979-1319=660,\qquad 1979-660=1319,$$
so $1979-k$ again lies between $660$ and $1319$. Since $2k=1979$ has no integer solution, no term is paired with itself.
The final modular step requires $1979\nmid q$. Every denominator in the original sum is less than $1979$, so after bringing the terms to a common denominator and reducing, the denominator cannot acquire a factor $1979$. Thus $q$ is invertible modulo $1979$, and $p/q\equiv0$ indeed implies $p\equiv0$.
Alternative Approaches
Instead of rewriting the alternating sum as $H_{1319}-H_{659}$, one may directly work with
$$S=\sum_{m=1}^{660}\frac1{2m-1}-\sum_{m=1}^{659}\frac1{2m}.$$
Modulo $1979$, the odd denominator $2m-1$ pairs with $1979-(2m-1)$, which is even, and every even denominator $2m$ pairs with $1979-2m$, which is odd. After reorganizing the terms, each pair contributes zero modulo $1979$.
The method using
$$S=\sum_{k=660}^{1319}\frac1k$$
is preferable because the pairing $k\leftrightarrow1979-k$ becomes completely transparent and avoids bookkeeping between odd and even denominators.