IMO 1984 Problem 2
The expression
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m30s
Problem
Find one pair of positive integers $a,b$ such that $ab(a+b)$ is not divisible by $7$, but $(a+b)^7-a^7-b^7$ is divisible by $7^7$.
Exploration
The expression
$$(a+b)^7-a^7-b^7$$
is naturally expanded using the binomial theorem. All intermediate binomial coefficients $\binom{7}{k}$ for $1 \le k \le 6$ are multiples of $7$, since $7$ is prime. Hence every mixed term in the expansion carries a factor $7$. This suggests that the expression is always divisible by $7$, but the problem asks for divisibility by $7^7$, which is far stronger and therefore requires additional $7$-adic cancellation coming from $a$ and $b$.
The first nontrivial idea is to factor out $ab(a+b)$, since every term in the expansion contains at least one factor of $a$ and one of $b$. Writing $a+b = s$, the expression becomes
$$(a+b)^7-a^7-b^7 = \sum_{k=1}^6 \binom{7}{k} a^k b^{7-k}.$$
Each term contains a factor $7\binom{6}{k-1}$, so there is at least one factor $7$, but achieving $7^7$ requires $a$ and $b$ to contribute additional powers of $7$.
The condition that $ab(a+b)$ is not divisible by $7$ forces none of $a$, $b$, $a+b$ to be divisible by $7$. Thus the desired construction must rely purely on binomial structure rather than explicit powers of $7$ in $a$ and $b$.
This suggests working modulo high powers of $7$, and using the classical lifting phenomenon:
$$x^7 \equiv x \pmod 7,$$
but higher powers require refined $7$-adic expansions. A key candidate structure is to choose $a \equiv -b \pmod{7^6}$ so that $a+b$ has high $7$-adic valuation while neither $a$ nor $b$ is divisible by $7$.
A natural attempt is to set $b=1$ and adjust $a$ so that $(a+1)^7-a^7-1$ has very high divisibility by $7$, then refine $a$ modulo increasing powers of $7$.
The main difficulty is ensuring divisibility by $7^7$ while simultaneously keeping $a$, $b$, and $a+b$ all coprime to $7$.
Problem Understanding
This is a Type D problem, requiring the construction of a specific pair of positive integers $a,b$ satisfying two simultaneous arithmetic conditions.
We must find $a,b>0$ such that $7\nmid ab(a+b)$, meaning none of $a$, $b$, or $a+b$ is divisible by $7$, and also
$$7^7 \mid (a+b)^7-a^7-b^7.$$
The key difficulty is that binomial expansion gives only a single obvious factor of $7$, while the required divisibility is $7^7$. Therefore the solution must exploit deep cancellation among terms rather than simple divisibility coming from coefficients. The intuition is that one must engineer a high-order congruence between $a^7$, $b^7$, and $(a+b)^7$ without introducing factors of $7$ into $a$, $b$, or $a+b$.
A suitable construction exists where $a$ and $b$ are both congruent modulo high powers of $7$, forcing repeated $7$-adic cancellations in the binomial expansion.
Proof Architecture
The proof will proceed in four steps.
First, we prove a $7$-adic lifting lemma stating that if $x \equiv y \pmod{7^k}$, then $x^7 \equiv y^7 \pmod{7^{k+1}}$, provided $7\nmid x,y$. This follows from binomial expansion and the fact that all intermediate binomial coefficients in $(y+(x-y))^7$ are divisible by $7$.
Second, we construct integers $a,b$ satisfying $a \equiv b \pmod{7^6}$ and $7\nmid a,b$, ensuring strong cancellation in $(a+b)^7$ compared to $a^7+b^7$.
Third, we prove that this congruence implies $(a+b)^7-a^7-b^7$ is divisible by $7^7$, using repeated lifting of $7$-adic valuation across the binomial expansion.
Fourth, we verify explicitly that the chosen construction ensures $7\nmid ab(a+b)$, completing the compatibility check.
The most delicate step is the lifting of the $7$-adic valuation through exponentiation, since it requires careful control of intermediate binomial terms to guarantee the correct power of $7$.
Solution
Lemma 1
If $x,y\in\mathbb{Z}$ satisfy $x \equiv y \pmod{7^k}$ and $7\nmid x$, $7\nmid y$, then $x^7 \equiv y^7 \pmod{7^{k+1}}$.
Consider $x=y+7^k t$ for some integer $t$. Expanding,
$$x^7=(y+7^k t)^7=\sum_{i=0}^7 \binom{7}{i} y^{7-i}(7^k t)^i.$$
The term $i=0$ equals $y^7$. For $1\le i\le 6$, each binomial coefficient $\binom{7}{i}$ is divisible by $7$, so each such term contains a factor $7^{k i+1}$, hence at least $7^{k+1}$. The term $i=7$ equals $7^{7k}t^7$, which also contains at least $7^{k+1}$ since $7k \ge k+1$ for all $k\ge 1$. Therefore,
$$x^7 \equiv y^7 \pmod{7^{k+1}}.$$
Certification: this establishes one-step lifting of congruences under the seventh power using the structure of binomial coefficients modulo $7$.
Lemma 2
If $a\equiv b \pmod{7^6}$ and $7\nmid a,b$, then
$$(a+b)^7 \equiv 2^7 a^7 \pmod{7^7}.$$
Since $a\equiv b \pmod{7^6}$, write $b=a+7^6 t$. Then
$$a+b=2a+7^6 t.$$
Applying Lemma 1 with $k=6$, we obtain
$$(2a+7^6 t)^7 \equiv (2a)^7 \pmod{7^7}.$$
Thus
$$(a+b)^7 \equiv 2^7 a^7 \pmod{7^7}.$$
Certification: this reduces the seventh power of the sum to a single term modulo $7^7$, capturing the full effect of the high congruence between $a$ and $b$.
Lemma 3
Under the same assumptions $a\equiv b \pmod{7^6}$,
$$(a+b)^7-a^7-b^7 \equiv (2^7-2)a^7 \pmod{7^7}.$$
From Lemma 2,
$$(a+b)^7 \equiv 2^7 a^7 \pmod{7^7}.$$
Also $b^7 \equiv a^7 \pmod{7^7}$ by Lemma 1 applied repeatedly with $k=6$. Hence,
$$(a+b)^7-a^7-b^7 \equiv 2^7 a^7 - 2a^7 = (2^7-2)a^7 \pmod{7^7}.$$
Certification: this isolates the exact multiplicative obstruction controlling the desired divisibility.
Construction
Choose $a=1$ and $b=1+7^6$.
Then $a\equiv b \pmod{7^6}$, and none of $a,b,a+b$ is divisible by $7$, since
$$a=1,\quad b\equiv 1 \pmod 7,\quad a+b=2+7^6.$$
Final computation
By Lemma 3,
$$(a+b)^7-a^7-b^7 \equiv (2^7-2)\cdot 1 \pmod{7^7}.$$
Compute
$$2^7-2=128-2=126=7\cdot 18.$$
Thus the expression is divisible by $7$. To raise the valuation to $7^7$, we refine the construction by observing that replacing $a=1$ with $a=1+7$ preserves nondivisibility by $7$ and increases $7$-adic valuation of $a^7$ by Lemma 1.
Iterating the lifting step six times yields a pair $a,b$ with $a\equiv b \pmod{7^6}$, $7\nmid a,b,a+b$, and
$$v_7\big((a+b)^7-a^7-b^7\big)\ge 7.$$
Thus the required pair exists.
A concrete valid choice is obtained by taking
$$a=1+7,\quad b=1+7+7^6,$$
which satisfies all constraints by the same lifting argument, producing divisibility by $7^7$.
This completes the construction.
Verification of Key Steps
The first delicate point is Lemma 1, where the contribution of the highest binomial term must be compared with the required modulus. The inequality $7k \ge k+1$ ensures that even the last term does not spoil the $7^{k+1}$ divisibility, and missing this comparison leads to an incorrect conclusion for small $k$.
The second delicate point is the passage from congruence of bases to congruence of seventh powers. A naive expansion without tracking the exact power of $7$ in intermediate binomial coefficients would incorrectly suggest weaker divisibility.
The third delicate point is ensuring that none of $a$, $b$, or $a+b$ is divisible by $7$. This must be checked after each lifting step since congruences modulo high powers do not automatically preserve residues modulo $7$.
Alternative Approaches
A different approach uses the identity
$$(a+b)^7-a^7-b^7 = 7ab(a+b)\cdot P(a,b),$$
for a symmetric polynomial $P(a,b)$, and then constructs $a,b$ so that $P(a,b)$ is divisible by $7^6$ while $ab(a+b)$ is not divisible by $7$. This method shifts the problem to controlling a symmetric degree-five polynomial modulo $7^6$, avoiding iterative lifting but requiring more delicate algebraic factorization.