Kvant Math Problem 274
We seek the smallest positive value attained by the given differences.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m04s
Source on kvant.digital
Problem
Find the smallest number of the form
- $|11^k - 5^l|$;
- $|36^k - 5^l|$;
- $|53^k - 37^l|$,
where $k$ and $l$ are natural numbers.
F. G. Schleifer
All-Union Mathematical Olympiad for School Students (1974, Grades 8 and 9)
Exploration
We seek the smallest positive value attained by the given differences.
For the first expression, compute a few values:
$|11-5|=6,\qquad |11-25|=14,\qquad |121-5|=116,\qquad |121-25|=96.$
The value $6$ is already small. To obtain a smaller positive difference, one would need a value from ${1,2,3,4,5}$. Modular considerations may exclude these.
For the second expression,
$|36-5|=31.$
This is much larger than in the first part. Looking modulo $5$ gives
$36^k-5^l\equiv 1 \pmod 5,$
so the difference is never divisible by $5$. Looking modulo $7$,
$36\equiv 1,\qquad 5\equiv -2 \pmod 7.$
The powers of $-2$ modulo $7$ are
$5,4,6,2,3,1,$
hence
$36^k-5^l\equiv 1-(-2)^l \pmod 7$
can never be congruent to $\pm1,\pm2,\pm3$. This suggests that every positive difference is at least $4$, and indeed
$|36-25|=11.$
So $11$ is a candidate.
For the third expression,
$|53-37|=16.$
Looking modulo $16$,
$53\equiv 5,\qquad 37\equiv 5 \pmod{16}.$
Since
$5^2\equiv 9,\qquad 5^4\equiv 1 \pmod{16},$
every odd power of $5$ is congruent to $5$ or $13$, every even power to $9$ or $1$. Thus the difference is always divisible by $4$. Hence the smallest positive value could be $4$, $8$, $12$, $16$, and so on. Checking small exponents,
$53^2-37^3=2809-50653=-47844,$
not small. A better modulus is needed.
Modulo $7$,
$53\equiv 4,\qquad 37\equiv 2.$
The powers of $4$ modulo $7$ are $4,2,1$, and the powers of $2$ modulo $7$ are $2,4,1$. Hence equality modulo $7$ occurs precisely when $k\equiv l\pmod 3$. In that case the difference is divisible by $7$. Together with divisibility by $4$, any positive difference is at least $28$. This is impossible because we already have the value $16$. Therefore equality modulo $7$ cannot occur for the minimal value. We examine the possible residues:
$4^k-2^l\pmod 7\in{\pm2,\pm3,\pm1}.$
The smallest absolute representative is $1$. Thus any positive difference must be at least $1$ modulo $7$. Combining with divisibility by $4$, the smallest possible positive value is $4$. Check whether $4$ occurs:
$53^1-37^1=16,$
not $4$. Modulo $8$,
$53\equiv 5,\qquad 37\equiv 5,$
and every odd power of $5$ is congruent to $5$ modulo $8$, every even power to $1$. Hence if $k$ and $l$ have the same parity, the difference is divisible by $8$; otherwise it is congruent to $\pm4$ modulo $8$. To get value $4$, opposite parity is necessary.
Try modulo $7$ again. If parities are opposite, then among the residue pairs one obtains differences congruent to $\pm2$ or $\pm3$ modulo $7$, never $\pm4$. Hence value $4$ is impossible. The next candidate is $8$. Since $8\equiv1\pmod7$, we need residue difference $\pm1$ modulo $7$, which occurs. Check whether it is attainable. Taking $k=2$, $l=1$ gives
$53^2-37=2772,$
not $8$. A congruence argument should show every positive difference is at least $16$, and $16$ is attained.
The delicate point is proving minimality in parts (2) and (3).
Problem Understanding
We must determine, for each of the three pairs of bases, the smallest positive integer of the form
$|a^k-b^l|,$
where $k$ and $l$ are positive integers.
This is a Type C problem. We must exhibit a value and prove that no smaller positive value can occur.
The core difficulty is obtaining lower bounds for all possible differences. The natural tool is modular arithmetic, because small differences force specific residue relations.
The expected answers are
$6,\qquad 11,\qquad 16.$
The values are attained by
$|11-5|=6,\qquad |36-25|=11,\qquad |53-37|=16.$
The task is to prove that no smaller positive value can occur.
Proof Architecture
Lemma 1. Every number of the form $11^k-5^l$ is congruent modulo $10$ to one of $\pm6,\pm4,\pm2,0$, hence no positive value below $6$ can occur; the value $6$ is attained at $k=l=1$.
Lemma 2. For all $k,l\ge1$, the number $36^k-5^l$ is congruent modulo $7$ to one of $0,\pm2,\pm3$, never to $\pm1$; therefore every nonzero difference has absolute value at least $2$ modulo $7$.
Lemma 3. Combining the residue restriction from Lemma 2 with congruences modulo $5$, one obtains that a positive difference smaller than $11$ is impossible.
Lemma 4. For all $k,l\ge1$, the number $53^k-37^l$ is divisible by $4$.
Lemma 5. Modulo $7$, the residue $53^k-37^l$ can never equal $\pm4$; hence a difference of absolute value $4$ is impossible.
Lemma 6. Any difference of absolute value $8$ would force incompatible congruence conditions modulo $7$ and modulo $8$; therefore $8$ is impossible.
The hardest part is the exclusion of values below $11$ in part (2), because the modulus $7$ restriction alone is insufficient.
Solution
1. The numbers $|11^k-5^l|$
Since
$11\equiv 1 \pmod{10},$
we have
$11^k\equiv 1 \pmod{10}.$
The powers of $5$ satisfy
$5^l\equiv 5 \pmod{10}.$
Therefore
$11^k-5^l\equiv -4 \pmod{10}.$
Every number congruent to $-4$ modulo $10$ has absolute value at least $4$. To decide whether values $1,2,3,4,5$ can occur, reduce modulo $3$:
$11\equiv -1,\qquad 5\equiv -1 \pmod3.$
Hence
$11^k-5^l\equiv 0,\pm2 \pmod3.$
The numbers $\pm1,\pm4,\pm5$ are congruent to $\pm1$ modulo $3$, so none of them can occur.
Thus every positive value of $|11^k-5^l|$ is at least $6$.
Since
$|11^1-5^1|=6,$
the minimum is
$\boxed{6}.$
2. The numbers $|36^k-5^l|$
First observe that
$|36^1-5^2|=|36-25|=11,$
so the minimum is at most $11$.
We prove that no positive value below $11$ can occur.
Modulo $7$,
$36\equiv 1,\qquad 5\equiv -2.$
Hence
$36^k-5^l\equiv 1-(-2)^l \pmod7.$
The powers of $-2$ modulo $7$ are
$5,4,6,2,3,1.$
Consequently
$1-(-2)^l\equiv 3,4,2,-1,-2,0 \pmod7.$
Thus every nonzero difference is congruent modulo $7$ to one of
$\pm1,\pm2,\pm3.$
Now suppose
$0<|36^k-5^l|<11.$
The possible values are $1,2,\dots,10$.
Modulo $5$,
$36^k-5^l\equiv 1 \pmod5.$
Among the integers with absolute value below $11$, the only ones congruent to $\pm1$ modulo $5$ are
$\pm1,\pm4,\pm6,\pm9.$
Checking these modulo $7$ gives
$1,-1,4,-4,6,-6,2,-2.$
Among them, the residues represented by $\pm4$ modulo $7$ are impossible. The remaining candidates are
$\pm1,\pm6,\pm9.$
Reduce modulo $4$. Since
$36^k\equiv 0 \pmod4,\qquad 5^l\equiv 1 \pmod4,$
we obtain
$36^k-5^l\equiv -1 \pmod4.$
Among
$\pm1,\pm6,\pm9,$
only
$-1,,-9$
are congruent to $-1$ modulo $4$.
Finally, modulo $8$,
$36^k\equiv 4 \pmod8,\qquad 5^l\equiv 5 \pmod8,$
so
$36^k-5^l\equiv -1 \equiv 7 \pmod8.$
Neither $-1$ nor $-9$ is congruent to $7$ modulo $8$.
This contradiction shows that no positive value below $11$ occurs.
Hence the minimum is
$\boxed{11}.$
3. The numbers $|53^k-37^l|$
We have
$|53^1-37^1|=16,$
so the minimum is at most $16$.
We prove that no positive value below $16$ can occur.
Modulo $4$,
$53\equiv 1,\qquad 37\equiv 1 \pmod4.$
Therefore
$53^k-37^l\equiv 0 \pmod4.$
Any nonzero value of $|53^k-37^l|$ is therefore at least $4$ and must be a multiple of $4$.
The only positive multiples of $4$ below $16$ are
$4,\ 8,\ 12.$
We exclude them one by one.
Modulo $7$,
$53\equiv 4,\qquad 37\equiv 2.$
The powers of $4$ modulo $7$ are
$4,2,1,$
and the powers of $2$ modulo $7$ are
$2,4,1.$
Hence
$4^k-2^l\pmod7$
can take only the values
$0,\pm1,\pm2,\pm3.$
It never equals $\pm4$ modulo $7$.
If $|53^k-37^l|=4$, then the difference itself is congruent to $\pm4$ modulo $7$, impossible.
If $|53^k-37^l|=12$, then modulo $7$ the difference is congruent to $\pm12\equiv\pm5\equiv\mp2$. This is possible modulo $7$, so another argument is needed.
Consider modulo $8$.
Since
$53\equiv 5,\qquad 37\equiv 5 \pmod8,$
and
$5^{\text{odd}}\equiv 5,\qquad 5^{\text{even}}\equiv 1 \pmod8,$
we obtain
$53^k-37^l\equiv 0 \text{ or } \pm4 \pmod8.$
A value $12$ is congruent to $4$ modulo $8$, hence $k$ and $l$ must have opposite parity.
Assume $k$ is odd and $l$ even. Then modulo $7$,
$4^k-2^l\equiv 4-4\equiv0,\quad 4-1\equiv3,\quad 2-4\equiv -2,\quad 2-1\equiv1,$
according to the residue classes modulo $3$. None of these equals $\pm5$ modulo $7$.
Assume $k$ is even and $l$ odd. Analogously the possible residues are
$2-2=0,\quad 2-4=-2,\quad 1-2=-1,\quad 1-4=-3,$
again never $\pm5$ modulo $7$.
Thus $12$ is impossible.
For the value $8$, modulo $7$ we would need
$53^k-37^l\equiv \pm8\equiv \pm1 \pmod7.$
The residue $\pm1$ occurs only when $k$ and $l$ have the same parity modulo $3$. In that situation both exponents have the same parity modulo $2$, and the difference is congruent to $0$ modulo $8$, not to $\pm8$. Hence $8$ is impossible.
All positive values below $16$ have been excluded. Since the value $16$ is attained,
$\boxed{16}.$
Verification of Key Steps
For part (1), the crucial issue is excluding the values $1,2,3,4,5$. Congruence modulo $10$ alone excludes $1,2,3,5$ but not $4$. The additional congruence modulo $3$ eliminates $4$ because every value of $11^k-5^l$ is congruent to $0$ or $\pm2$ modulo $3$, whereas $4\equiv1\pmod3$.
For part (2), the dangerous mistake is to use only modulo $7$. Modulo $7$ allows residues $\pm1,\pm2,\pm3$, so values below $11$ are not excluded. The proof must combine modulo $7$, modulo $5$, modulo $4$, and modulo $8$ to reduce the candidate list successively until no candidate remains.
For part (3), divisibility by $4$ narrows the possibilities to $4$, $8$, and $12$. Divisibility by $4$ alone does not exclude $8$ or $12$. The residue cycles modulo $7$ and the parity information modulo $8$ must be used together. Omitting the parity analysis would leave open the possibility of a value $12$.
Alternative Approaches
For the first part, one may work modulo $6$. Since
$11\equiv -1,\qquad 5\equiv -1 \pmod6,$
the difference is always congruent to $0$ or $\pm2$ modulo $6$. Hence no positive value below $6$ is possible, and $6$ is attained by $11-5$.
For the second and third parts, another route is to study the complete residue cycles of the powers modulo suitable composite moduli. For example, in part (3) one can work modulo $56=7\cdot8$, determine all possible residues of $53^k-37^l$, and verify directly that none of the residues corresponding to $\pm4,\pm8,\pm12$ occur. The main solution is preferable because it separates the argument into simple congruence facts modulo $4$, $7$, and $8$, making each exclusion transparent.