Olympiad Number Theory III: Exponential Diophantine Equations

Study Sheet

Olympiad Number Theory III: Exponential Diophantine Equations

Powers of two, difference of squares, Catalan-type equations, and the parity–valuation reflex

Equations in Exponents

Tip
Divide out the smallest power, then look at parity

2x+2y=2z2^x + 2^y = 2^z: dividing by 2min⁡(x,y)2^{\min(x,y)} leaves 1+2k=2m1 + 2^k = 2^m, forcing k=0k = 0; so the solutions are exactly (x,x,x+1)(x, x, x+1). In general, comparing pp-adic valuations of both sides is the first move.

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 pp and the other is a power of pp — usually a contradiction unless an exponent is 00. The same reflex settles 3x+3y=3z3^x + 3^y = 3^z, 2x+3y=5z2^x + 3^y = 5^z (mod small numbers), and most "find all positive integers" equations of contest size.

Tip
Difference of squares and difference of powers

m2−n2=2km^2 - n^2 = 2^k splits as (m−n)(m+n)(m-n)(m+n) with both factors powers of 22 of the same parity; 2n+1=m22^n + 1 = m^2 becomes 2n=(m−1)(m+1)2^n = (m-1)(m+1), two powers of 22 differing by 22, so n=3n = 3; 3x−2y=13^x - 2^y = 1 needs xx even (mod 88) and then (3x/2−1)(3x/2+1)=2y(3^{x/2} - 1)(3^{x/2} + 1) = 2^y gives (2,3)(2, 3) besides (1,1)(1, 1).

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

Tip
Growth arguments and ab=baa^b = b^a

ab=baa^b = b^a with a<ba < b has the unique solution (2,4)(2, 4): ln⁡tt\tfrac{\ln t}{t} increases on (0,e)(0, e) and decreases after, so one of the two is ≤2\le 2.

When modular arithmetic and factoring both fail, compare growth rates: an exponential beats a polynomial eventually, and a calculus fact about a real function can bound integer solutions. State the monotonicity precisely (with the derivative), then check the finitely many small cases by hand — the proof is incomplete without both halves.

Side note
The bounding checklist

Every "find all positive integer solutions" problem is solved by some mix of: valuations/parity, a modulus that kills a residue class (mod 3,4,7,8,9,163, 4, 7, 8, 9, 16), factoring into coprime pieces, size comparison (squeezing between consecutive squares or powers), and descent. Write which one you are using at each step; graders award partial credit per correctly justified reduction.

Try it
Try it: squeeze

Show that n2+n+1n^2 + n + 1 is never a perfect square for n≥1n \ge 1.

Since n2<n2+n+1<n2+2n+1=(n+1)2n^2 < n^2 + n + 1 < n^2 + 2n + 1 = (n+1)^2 for n≥1n \ge 1, it lies strictly between consecutive squares.