Olympiad Number Theory III: Exponential Diophantine Equations

An exponential equation is a statement about valuations: the side with the smaller valuation must be matched exactly. After dividing out, one side is a unit modulo $p$ and the other is a power of $p$ — usually a contradiction unless an exponent is $0$. The same reflex settles $3^x + 3^y = 3^z$, $2^x + 3^y = 5^z$ (mod small numbers), and most "find all positive integers" equations of contest size.

Factoring is the second reflex. The pattern "two powers of $p$ whose difference is small" has finitely many solutions, all tiny — that is the elementary heart of Catalan's equation $x^a - y^b = 1$ (Mihăilescu proved the general case; the powers-of-$2$ and $3$ cases are exercises). Always finish with the small cases you excluded along the way (here $y \le 2$).

Taking logarithms, $a^b=b^a$ says $\tfrac{\ln a}{a}=\tfrac{\ln b}{b}$: two points at the same height on the graph of $g(t)=\tfrac{\ln t}{t}$. Since $g'(t)=\tfrac{1-\ln t}{t^2}$, $g$ increases on $(0,e)$ and decreases on $(e,\infty)$, so a horizontal chord with $a<b$ has $a<e<b$, i.e. $a\in\{1,2\}$. $a=1$ gives $1=b$, impossible; $a=2$ gives $b^2=2^b$, which fails at $b=3$ ($9\ne8$) and holds at $b=4$, and $2^b>b^2$ for $b\ge5$ (induction: $2^{b+1}=2\cdot2^b>2b^2\ge(b+1)^2$). The general lesson: when modular arithmetic and factoring both fail, compare growth rates, state the monotonicity precisely (with the derivative), then check the finitely many small cases by hand — the proof is incomplete without both halves.

Modulo $m$, each power $a^x$ is periodic in $x$ with period $\operatorname{ord}_m(a)$, so the equation becomes a finite table of residues. When the orders are small the table is tiny and either contradicts itself or pins an exponent's residue — most usefully its parity. An even exponent turns $c^{2w}-b^y$ into $(c^w-b^{y/2})(c^w+b^{y/2})$, and a product of two factors equal to a prime power forces both to be powers of that prime, which is usually the end. Every reduction "mod $2^k$" or "mod $3^k$" assumes the corresponding exponent is at least $k$; the smaller exponents are separate cases to check by hand.

Step 1 — small $y$ first: $y=0$ gives $3^x=8$, impossible; $y=1$ gives $3^x=9$, so $x=2$; $y=2$ gives $3^x=11$, impossible.

Step 2 — for $y\ge3$, reduce mod $8$: $3^x\equiv7\pmod8$. But powers of $3$ mod $8$ alternate $1,3,1,3,\dots$, never $7$. So the only solution is $(x,y)=(2,1)$.

How to find it. A power of $2$ disappears modulo a power of $2$, leaving a condition on $3^x$ alone; mod $8$ is the smallest modulus where $3^x$ has only two residues. The price of the reduction is the list of small $y$, which must be checked separately.

Step 1 — $n=1$: $2+12+2011=2025=45^2$.

Step 2 — even $n\ge2$: modulo $3$, $2^n\equiv1$, $12^n\equiv0$ and $2011^n\equiv1^n=1$, so the sum is $\equiv2\pmod3$; squares are $0$ or $1\bmod3$.

Step 3 — odd $n\ge3$: modulo $4$, $2^n\equiv0$, $12^n\equiv0$ and $2011^n\equiv3^n\equiv3$, so the sum is $\equiv3\pmod4$; squares are $0$ or $1\bmod4$. So $n=1$ is the only answer.

How to find it. Test small cases — $n=1$ works and $n=2$ does not — then look for a modulus in which the parity of $n$ changes the residue: mod $3$ sees $2^n=(-1)^n$, mod $4$ sees $2011^n=(-1)^n$. One modulus per parity class finishes it.

Step 1 — mod $3$: $0+1\equiv(-1)^z$, so $z$ is even; write $z=2w$.

Step 2 — now the equation factors: $3^x=5^{2w}-2^{2y}=(5^w-2^y)(5^w+2^y)$. Both factors are powers of $3$, and their difference $2^{y+1}$ is not divisible by $3$, so the smaller one is $3^0$: $5^w-2^y=1$ and $5^w+2^y=3^x$.

Step 3 — mod $3$ on $5^w=2^y+1$: $(-1)^w\equiv(-1)^y+1$. The right side is $2\equiv-1$ or $0$, and the left side is $\pm1$, so $(-1)^y=1$ and $(-1)^w=-1$: $y$ is even and $w$ is odd.

Step 4 — if $y\ge3$, then mod $8$: $5^w\equiv1$, which needs $w$ even — a contradiction. So $y\le2$ and $y$ is even: $y=2$, $5^w=5$, $w=1$, $z=2$, and $3^x=5+4=9$ gives $x=2$. The only solution is $(2,2,2)$: $9+16=25$.

How to find it. The answer $3^2+4^2=5^2$ is a Pythagorean triple, which suggests even exponents; mod $3$ produces the one parity you need to factor. After factoring, "two powers of $3$ whose difference is prime to $3$" leaves no room, and mods $3$ and $8$ finish the remaining equation $5^w=2^y+1$.

But $(x,y)=(2,1)$ is a solution: $9-2=7$. The step "$2^y\equiv0\pmod8$" holds only for $y\ge3$; for $y\in\{0,1,2\}$ the power of $2$ is $1,2,4$, not $0$. Every reduction that makes a term vanish carries a hidden lower bound on an exponent, and the cases below that bound must be checked by hand — here they contain the whole answer.

Two lemmas give it; write $S_n=\tfrac{a^n-b^n}{a-b}=a^{n-1}+a^{n-2}b+\cdots+b^{n-1}$. If $p\nmid n$, then $S_n\equiv na^{n-1}\not\equiv0\pmod p$ because $b\equiv a$: the valuation does not grow. If $n=p$, put $b=a+t$ with $p\mid t$; then $b^i\equiv a^i+ia^{i-1}t\pmod{p^2}$, so $S_p\equiv pa^{p-1}+a^{p-2}t\cdot\tfrac{p(p-1)}2\equiv pa^{p-1}\pmod{p^2}$, using that $p$ is odd. So a factor $p$ in the exponent adds exactly one to the valuation. Writing $n=p^km$ with $p\nmid m$ and applying the second lemma $k$ times and the first once gives the formula. For $p=2$ the step $n=2$ is $a^2-b^2=(a-b)(a+b)$, which adds $v_2(a+b)\ge1$ rather than $1$ — the source of the extra term. The figure shows the $p=2$ case for $3^n-1$: $1$ at odd $n$ and $2+v_2(n)$ at even $n$.

Step 1 — odd $n$: $v_2(3^n-1)=v_2(3-1)=1$, so only $n=1$ works.

Step 2 — even $n$: $v_2(3^n-1)=v_2(2)+v_2(4)+v_2(n)-1=2+v_2(n)$. We need $2+v_2(n)\ge n$.

Step 3 — $v_2(n)\le\log_2n$, and $2+\log_2n<n$ for $n\ge5$ ($n=5$: $2+\log_25<5$, and the left side grows more slowly afterwards). So $n\le4$; among even $n$, $n=2$ ($v_2(8)=3\ge2$) and $n=4$ ($v_2(80)=4\ge4$) work. The answer is $n\in\{1,2,4\}$.

How to find it. "$p^n$ divides something to the $n$-th power" is a valuation question, and LTE turns the valuation into $v_p(n)$ plus a constant. Logarithmic against linear growth leaves only small cases.

Step 1 — $2^n+1$ is odd, so $n$ is odd. Let $p$ be the least prime factor of $n$. From $2^n\equiv-1$ we get $2^{2n}\equiv1$, so $\operatorname{ord}_p(2)$ divides $\gcd(2n,p-1)$. Every prime factor of $n$ is at least $p$, so $\gcd(n,p-1)=1$ and $\gcd(2n,p-1)\mid2$. Hence $p\mid2^2-1=3$: $p=3$.

Step 2 — LTE with $p=3\mid2+1$ and $n$ odd: $v_3(2^n+1)=v_3(3)+v_3(n)=1+v_3(n)$. The condition $n^2\mid2^n+1$ needs $2v_3(n)\le1+v_3(n)$, so $v_3(n)=1$: $n=3m$ with $3\nmid m$.

Step 3 — suppose $m>1$ and let $q$ be the least prime factor of $m$, so $q\ge5$. As before $\operatorname{ord}_q(2)$ divides $\gcd(2n,q-1)$; the only prime factor of $n$ below $q$ is $3$, and it appears once, so $\gcd(2n,q-1)\mid6$ and $q\mid2^6-1=63$, i.e. $q=7$.

Step 4 — but $7\nmid2^n+1$ for every $n$: the powers of $2$ mod $7$ are $1,2,4$, never $-1\equiv6$ (the figure). So $m=1$ and $n=3$; indeed $9\mid9$.

How to find it. "$n$ divides $a^n\pm1$" is attacked through the least prime factor of $n$, whose order is squeezed by $\gcd(2n,p-1)$. After the smallest prime is identified, LTE decides its exact power, and the next-smallest prime is squeezed the same way.

Step 1 — $p$ odd gives $x+y\mid x^p+y^p=p^z$, so $x+y=p^k$ with $k\ge1$ (as $x+y\ge2$). Then $p\nmid x$: otherwise $p\mid y$ too, against $\gcd(x,y)=1$.

Step 2 — LTE for sums ($p\mid x+y$, exponent $p$ odd): $v_p(x^p+y^p)=v_p(x+y)+v_p(p)=k+1$. So $x^p+y^p=p^{k+1}=p(x+y)$.

Step 3 — size: by the power-mean inequality $x^p+y^p\ge2\left(\tfrac{x+y}2\right)^p$, so $2^{1-p}(x+y)^p\le p(x+y)$, i.e. $(x+y)^{p-1}\le p\cdot2^{p-1}$. With $x+y\ge p$ this gives $p^{p-2}\le2^{p-1}$. That holds for $p=3$ ($3\le4$) and fails for $p=5$ ($125>16$) and, since $p^{p-2}\ge5^{p-2}>2^{p-1}$, for every larger prime.

Step 4 — so $p=3$ and $(x+y)^2\le12$; $x+y$ is a power of $3$ at least $2$, so $x+y=3$: $\{x,y\}=\{1,2\}$, and $1+8=9=3^2$. The solutions are $p=3$ with $(x,y,z)=(1,2,2)$ and $(2,1,2)$.

How to find it. A sum of $p$-th powers equal to a power of $p$: the factor $x+y$ is forced to be a power of $p$, LTE says the full sum has only one more factor of $p$, and then the sum is far too small compared with its $p$-th powers. Valuations give an exact equation; size finishes it.

The first applies the odd-prime formula at $p=2$; for $p=2$ and even $n$ the correct formula has the extra term $v_2(a+b)-1$, here $v_2(4)-1=1$, giving $3$. The second ignores the hypothesis $p\mid a-b$: $3\nmid2-1$. The repair is to first pass to a power where the hypothesis holds: $3\mid2^2-1$, so $v_3(2^6-1)=v_3(4^3-1)=v_3(4-1)+v_3(3)=2$. Before quoting LTE, write down $p$, $a$, $b$ and check $p\mid a-b$, $p\nmid ab$ and the parity of $p$.