Kvant Math Problem 524

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m40s
Source on kvant.digital

Problem

Prove that for no natural $m$ does the number $1978^m-1$ divide $1000^m-1$.

S. V. Konyagin

All-Union Mathematical Olympiad for School Students (XII, 1978, 8th grade)

Exploration

Consider the numbers $1978^m - 1$ and $1000^m - 1$ for small values of $m$. For $m = 1$, $1978^1 - 1 = 1977$ and $1000^1 - 1 = 999$, and $1977$ does not divide $999$. For $m = 2$, $1978^2 - 1 = 1978^2 - 1$ is roughly $3.91 \cdot 10^6$ while $1000^2 - 1 = 999999$, clearly smaller; division is impossible. Increasing $m$ only increases $1978^m - 1$ faster than $1000^m - 1$, suggesting that if $1978^m - 1$ were to divide $1000^m - 1$, $m$ would have to be very small.

We can attempt to factor using the difference of powers formula: $a^m - 1 = (a - 1)(a^{m-1} + \cdots + 1)$. Then the divisibility condition becomes $1978 - 1$ times a large sum dividing $1000^m - 1$. Observing that $1978 - 1000 = 978$, we see the two bases differ significantly; their multiplicative order modulo each other is unlikely to align.

One could also consider modulo arithmetic: if $1978^m - 1$ divides $1000^m - 1$, then $1000^m \equiv 1 \pmod{1978^m - 1}$. For large $m$, this seems impossible since $1000^m < 1978^m$ for $m \ge 2$. The crucial insight is that $1978^m - 1 > 1000^m - 1$ for all $m \ge 2$, so only $m = 1$ could possibly work, and we already saw it does not. This suggests the proof reduces to comparing sizes and considering $m = 1$ explicitly.

A more sophisticated approach could invoke the Lifting The Exponent lemma or properties of gcd of numbers of the form $a^m - 1$ and $b^m - 1$, but small case analysis seems sufficient. The delicate step is verifying that $m = 1$ indeed fails and no larger $m$ can work.

Problem Understanding

The problem asks to prove that for no natural number $m$ does $1978^m - 1$ divide $1000^m - 1$. This is a Type B problem: a direct proof of impossibility. The core difficulty lies in the enormous size and rapid growth of the exponents, which prevents any naive division, and in verifying that no small $m$ accidentally satisfies the divisibility. The intuitive reason the statement is true is that $1978 > 1000$, so for $m \ge 2$, $1978^m - 1$ already exceeds $1000^m - 1$, making divisibility impossible; for $m = 1$, direct calculation shows divisibility fails.

Proof Architecture

Lemma 1: For all integers $m \ge 2$, $1978^m - 1 > 1000^m - 1$. This follows from the fact that $1978 > 1000$ and the function $f(x) = x^m$ is strictly increasing for $x > 0$ and $m \in \mathbb{N}$.

Lemma 2: For $m = 1$, $1978^1 - 1 = 1977$ does not divide $1000^1 - 1 = 999$. This can be verified by computing the division and observing the remainder.

The main argument uses these lemmas to conclude that no natural $m$ satisfies the divisibility condition. The hardest part is Lemma 1, ensuring that for all $m \ge 2$, the inequality holds rigorously.

Solution

For $m = 1$, $1978^1 - 1 = 1977$ and $1000^1 - 1 = 999$. Dividing $1000 - 1$ by $1978 - 1$ gives $999 / 1977$, which is not an integer. Hence, $m = 1$ does not satisfy the condition.

Consider $m \ge 2$. The function $f(x) = x^m$ is strictly increasing for $x > 0$, so $1978^m > 1000^m$. Subtracting $1$ from both sides yields $1978^m - 1 > 1000^m - 1$. Therefore, $1978^m - 1$ is strictly larger than $1000^m - 1$, making it impossible for $1978^m - 1$ to divide $1000^m - 1$, as a larger positive integer cannot divide a smaller positive integer.

Since $m = 1$ fails and no $m \ge 2$ can work, there exists no natural number $m$ such that $1978^m - 1$ divides $1000^m - 1$.

This completes the proof.

∎

Verification of Key Steps

For Lemma 1, consider $m = 2$: $1978^2 = 3,912,484$ and $1000^2 = 1,000,000$, confirming $1978^2 - 1 > 1000^2 - 1$. For $m = 3$: $1978^3 = 7,736,013,352$ and $1000^3 = 1,000,000,000$, confirming the inequality again. This pattern continues, and the inductive-like argument on $m$ using strict monotonicity of $x^m$ is valid for all $m \ge 2$.

For $m = 1$, the exact division yields $999 / 1977 \approx 0.505$, not an integer, confirming the direct check. No subtle remainders or negative considerations exist since all numbers are positive.

Alternative Approaches

An alternative approach would consider the greatest common divisor of numbers of the form $a^m - 1$ and $b^m - 1$, using $\gcd(a^m - 1, b^m - 1) = a^{\gcd(m, n)} - 1$ in some formulations. One could also attempt to apply modular arithmetic, assuming $1000^m \equiv 1 \pmod{1978^m - 1}$ and showing this is impossible. The main approach is preferable because it requires no sophisticated number-theoretic machinery and rests purely on size comparison and small case verification, making it rigorous and elementary.