IMO 1979 Problem 1
For small values, the alternating harmonic sums reduce to fractions whose numerators often contain large prime factors.
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 10m50s
Problem
If $p$ and $q$ are natural numbers so that$$ \frac{p}{q}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+ \ldots -\frac{1}{1318}+\frac{1}{1319}, $$prove that $p$ is divisible by $1979$.
Exploration
For small values, the alternating harmonic sums reduce to fractions whose numerators often contain large prime factors. Computing the first few cases helps identify the correct structural decomposition.
For $n=1$,
$$1=\frac11.$$
For $n=2$,
$$1-\frac12=\frac12.$$
For $n=3$,
$$1-\frac12+\frac13=\frac56.$$
For $n=4$,
$$1-\frac12+\frac13-\frac14=\frac7{12}.$$
For $n=5$,
$$1-\frac12+\frac13-\frac14+\frac15=\frac{47}{60}.$$
The problem asks about
$$S=1-\frac12+\frac13-\cdots-\frac1{1318}+\frac1{1319}.$$
Since $1319=1979-660$, the prime $1979$ does not appear directly in the denominators, so divisibility by $1979$ must come from a congruence hidden inside the sum.
A natural first step is to separate odd and even terms:
$$S=\left(1+\frac13+\frac15+\cdots+\frac1{1319}\right)-\frac12\left(1+\frac12+\frac13+\cdots+\frac1{659}\right).$$
This form is not immediately adapted to congruences modulo $1979$.
Another possibility is to pair consecutive terms:
$$\frac1{2k-1}-\frac1{2k}=\frac1{2k(2k-1)}.$$
Then
$$S=\sum_{k=1}^{659}\frac1{2k(2k-1)}.$$
Every denominator here is strictly less than $1979$, hence invertible modulo $1979$. This suggests interpreting the entire fraction modulo $1979$.
To prove that the numerator is divisible by $1979$, it suffices to prove that the rational number $S$ is congruent to $0$ modulo $1979$. Since $1979$ is prime and larger than every denominator appearing, all denominators possess multiplicative inverses modulo $1979$.
The key congruence likely comes from symmetry. Since
$$1319=1979-660,$$
the numbers $1,2,\dots,659$ pair naturally with $1979-1,1979-2,\dots,1979-659$.
A more promising rewrite is
$$S=H_{1319}-H_{659},$$
where
$$H_n=\sum_{k=1}^n\frac1k.$$
Indeed,
$$H_{1319}-H_{659}=\sum_{k=660}^{1319}\frac1k.$$
Checking against the alternating form,
$$\sum_{k=1}^{1319}\frac{(-1)^{k+1}}k =\sum_{m=1}^{660}\frac1{2m-1}-\sum_{m=1}^{659}\frac1{2m}.$$
Since
$$H_{1319} =\sum_{m=1}^{660}\frac1{2m-1}+\sum_{m=1}^{659}\frac1{2m},$$
subtracting
$$2\sum_{m=1}^{659}\frac1{2m}=\sum_{m=1}^{659}\frac1m=H_{659}$$
gives the identity.
Now
$$S=\sum_{k=660}^{1319}\frac1k.$$
Modulo $1979$,
$$\frac1k+\frac1{1979-k}\equiv0.$$
The interval $660,\dots,1319$ is exactly stable under $k\mapsto1979-k$. Hence the terms cancel pairwise modulo $1979$. This should prove
$$S\equiv0\pmod{1979}.$$
Since the denominator of $S$ is relatively prime to $1979$, the numerator must be divisible by $1979$.
The delicate point is translating a congruence of rational numbers into a statement about the numerator after reduction to lowest terms. One must justify carefully that no denominator contains the prime $1979$.
Problem Understanding
The problem concerns the alternating harmonic sum
$$S=1-\frac12+\frac13-\frac14+\cdots-\frac1{1318}+\frac1{1319}.$$
After writing $S$ in lowest terms as
$$S=\frac pq,$$
with $p,q\in\mathbb N$ and $\gcd(p,q)=1$, one must prove that $1979$ divides $p$.
This is a Type B problem. The statement to be proved is a divisibility property of the numerator of a rational number.
The mathematical objects involved are rational numbers, congruences modulo a prime, and harmonic sums. The main difficulty is that the numerator $p$ is not given explicitly. Direct computation of the fraction is impossible because the common denominator is enormous. The proof must instead exploit structural symmetry inside the sum.
A naive attempt to combine all terms over a common denominator produces expressions too complicated to analyze. The essential idea is to reinterpret the sum in a form admitting cancellation modulo $1979$.
Proof Architecture
The proof will proceed through three claims.
Lemma 1 states that
$$1-\frac12+\frac13-\cdots-\frac1{1318}+\frac1{1319} =\sum_{k=660}^{1319}\frac1k.$$
This follows by expressing the alternating sum in terms of harmonic sums and simplifying.
Lemma 2 states that for every integer $k$ with $660\le k\le1319$,
$$\frac1k+\frac1{1979-k}\equiv0\pmod{1979}.$$
This follows because $1979$ is prime and
$$1979-k\equiv-k\pmod{1979}.$$
Lemma 3 states that
$$\sum_{k=660}^{1319}\frac1k\equiv0\pmod{1979}.$$
This follows from pairing the terms indexed by $k$ and $1979-k$.
The hardest point is the final passage from a congruence for a rational number modulo $1979$ to divisibility of the numerator in lowest terms. The argument must verify that the denominator is relatively prime to $1979$.
Solution
Define
$$S=1-\frac12+\frac13-\frac14+\cdots-\frac1{1318}+\frac1{1319}.$$
Lemma 1
One has
$$S=\sum_{k=660}^{1319}\frac1k.$$
Proof.
Let
$$H_n=\sum_{k=1}^n\frac1k.$$
Then
$$H_{1319} =\sum_{m=1}^{660}\frac1{2m-1}+\sum_{m=1}^{659}\frac1{2m}.$$
Also,
$$H_{659}=\sum_{m=1}^{659}\frac1m =2\sum_{m=1}^{659}\frac1{2m}.$$
Hence
\begin{align*}
H_{1319}-H_{659}
&=\sum_{m=1}^{660}\frac1{2m-1}-\sum_{m=1}^{659}\frac1{2m}\
&=1-\frac12+\frac13-\frac14+\cdots-\frac1{1318}+\frac1{1319}\
&=S.
\end{align*}
Since
$$H_{1319}-H_{659}=\sum_{k=660}^{1319}\frac1k,$$
the desired identity follows. ∎
This lemma converts the alternating sum into a consecutive harmonic block, whereas a direct treatment of alternating signs obscures the modular symmetry.
Lemma 2
For every integer $k$ with $660\le k\le1319$,
$$\frac1k+\frac1{1979-k}\equiv0\pmod{1979}.$$
Proof.
The number $1979$ is prime. Since
$$1\le k\le1319<1979,$$
the integer $k$ is not divisible by $1979$, so $k$ possesses a multiplicative inverse modulo $1979$. Likewise, $1979-k$ is not divisible by $1979$.
Because
$$1979-k\equiv-k\pmod{1979},$$
taking inverses modulo $1979$ yields
$$\frac1{1979-k}\equiv-\frac1k\pmod{1979}.$$
Therefore
$$\frac1k+\frac1{1979-k}\equiv0\pmod{1979}.$$
∎
This lemma identifies the exact cancellation mechanism, whereas merely comparing numerical values of paired terms gives no modular information.
Lemma 3
One has
$$S\equiv0\pmod{1979}.$$
Proof.
By Lemma 1,
$$S=\sum_{k=660}^{1319}\frac1k.$$
The transformation
$$k\mapsto1979-k$$
permutes the set
$${660,661,\dots,1319},$$
because
$$1979-660=1319,\qquad 1979-1319=660.$$
Hence the terms of the sum can be partitioned into pairs
$$\left(\frac1k,\frac1{1979-k}\right).$$
By Lemma 2, each pair has sum congruent to $0$ modulo $1979$. Consequently,
$$S\equiv0\pmod{1979}.$$
∎
This lemma establishes the global congruence by exhaustive pairing, whereas canceling only a portion of the interval would leave uncanceled terms.
Now write
$$S=\frac pq$$
in lowest terms, with $p,q\in\mathbb N$ and $\gcd(p,q)=1$.
Every denominator appearing in
$$S=\sum_{k=660}^{1319}\frac1k$$
is strictly smaller than $1979$. Hence, after reducing to lowest terms, the denominator $q$ is not divisible by $1979$. Therefore $q$ possesses a multiplicative inverse modulo $1979$.
Since
$$\frac pq=S\equiv0\pmod{1979},$$
multiplying by $q$ modulo $1979$ gives
$$p\equiv0\pmod{1979}.$$
Thus $1979$ divides $p$.
This completes the proof.
∎
Verification of Key Steps
The identity
$$S=\sum_{k=660}^{1319}\frac1k$$
is delicate because an incorrect index shift changes the entire interval. Re-deriving it directly,
\begin{align*}
S
&=\sum_{m=1}^{660}\frac1{2m-1}-\sum_{m=1}^{659}\frac1{2m}\
&=\left(\sum_{m=1}^{660}\frac1{2m-1}+\sum_{m=1}^{659}\frac1{2m}\right)-2\sum_{m=1}^{659}\frac1{2m}\
&=H_{1319}-H_{659}\
&=\sum_{k=660}^{1319}\frac1k.
\end{align*}
A careless argument often replaces $H_{659}$ with $\sum_{m=1}^{660}\frac1{2m}$, which inserts an extra term $\frac1{1320}$ and destroys the symmetry.
The congruence
$$\frac1{1979-k}\equiv-\frac1k\pmod{1979}$$
depends crucially on invertibility modulo a prime. Starting from
$$1979-k\equiv-k\pmod{1979},$$
multiplying by the inverse of $k(1979-k)$ gives
$$\frac1{1979-k}\equiv-\frac1k\pmod{1979}.$$
A careless proof may divide by $k$ without first verifying that $1979\nmid k$.
The final step from
$$S\equiv0\pmod{1979}$$
to
$$1979\mid p$$
requires checking that the reduced denominator is invertible modulo $1979$. If the denominator contained a factor $1979$, multiplication by $q$ would not preserve equivalence. Here every original denominator is less than $1979$, so the least common denominator is also not divisible by $1979$.
Alternative Approaches
Another approach begins with the paired form
$$S=\sum_{k=1}^{659}\left(\frac1{2k-1}-\frac1{2k}\right)+\frac1{1319} =\sum_{k=1}^{659}\frac1{2k(2k-1)}+\frac1{1319}.$$
Modulo $1979$, one can pair the term indexed by $k$ with the term indexed by $660-k$. The denominators then combine into complementary residues modulo $1979$, leading again to cancellation. This method is more computational because the algebra inside each pair is less transparent.
A second strategy uses the classical congruence
$$\sum_{k=1}^{p-1}\frac1k\equiv0\pmod p$$
for primes $p$. Since
$$\sum_{k=1}^{1978}\frac1k\equiv0\pmod{1979},$$
and since
$$\sum_{k=1}^{659}\frac1k+\sum_{k=1320}^{1978}\frac1k\equiv0\pmod{1979},$$
one obtains
$$\sum_{k=660}^{1319}\frac1k\equiv0\pmod{1979}.$$
This argument is elegant but relies on recognizing the appropriate decomposition of the complete harmonic sum modulo a prime. The main proof is preferable because every cancellation appears directly from the symmetry of the interval $[660,1319]$.