Number Theory #4 : Using Appropriate Moduli to Solve Exponential Diophantine Equations

We’ve all seen the solutions that say “trivial by modulo $32892372387$ ” by maxal and a few other prominent AoPS users. How do they come up with these crazy numbers? Well, the trick is not to focus on using only one modulus, in fact it is to use many! Its simply easier to check if the solution works through a computer if you are using only one modulus, which is why these solutions appear so often on AoPS. However, we will explore this process to learn how you can construct these solutions by hand, albeit being a little tedious.

The key intuition to this strategy is to just take modulo a lot of numbers and attempt to derive a contradiction. Its really simple, but there are a few techniques introduced in the following problems which will heavily speed up your approach.

Let’s start first with a simple innocent looking problem.

Problem 1: Find the natural numbers $n$ for which $5^n +3$ is a power of $2$ .

Solution: We solve the exponential Diophantine Equation $5^n + 3 = 2^m$ . The solution of $(3,7)$ is rather daunting but it motivates the solution. First, remark that if $m \le 7$ the only solutions are $(1,3), (3,7)$ . Note take $m \ge 8$ . By modulo $256$ one quickly deduces $n \equiv 35 \pmod{64}$ (do you see why this is immediate from $(3,7)$ being a solution? The fact that $\text{ord}_{2^n}(5) = 2^{n-2}$ for $n \ge 3$ is used here). Now, recall that $641|(2^{32} + 1)$ and that $641$ is prime. This means $\text{ord}_{641}(2) = 64$ . One can painfully check that $\text{ord}_{641}(5) = 64$ as well. This means the LHS is fixed for all values of $n$ . Looking modulo $5$ we get $m \equiv 3 \pmod{4}$ . Now check the $16$ cases to see there are no solutions modulo $641$ so we are done. $\square$

Remark: Maxal probably would have posted a solution simply stating use modulo $164096$ , however this is heavily obfuscated in that one gains no intuition from reading such a solution. The motivation of looking modulo $256$ is clear since we need to bypass the large $(3,7)$ solutions. As this tells us $n \pmod{64}$ , we then find a number $p$ for which $\text{ord}_p(5) = 64$ . There really isn’t a feasible way to do this other than checking primes $1 \pmod{64}$ or remembering Euler’s proof that $641|(2^{32} + 1)$ .

The above solution demonstrates that using various moduli is extremely helpful in solving exponential Diophantine equations. The most important step for picking your moduli is first to pick $m$ , where $m$ is divisible by at least one of the components of the largest solution but is strictly greater than it (i.e. like if a $9^2$ is part of a solution then picking $m = 243$ might work, note that the fact that for $k > 2$ we have $243|9^k$ is essential). Without this step, your solution cannot possibly be correct. Fore the next step, suppose $a$ is one of the numbers raised to an exponent in the problem and we have in the problem $a^x$ , and by step one we achieved $x \equiv k \pmod{n}$ . Now, choose numbers $m$ such that $\text{ord}_m(a)|n$ . The intuition behind this is we are trying to draw a contradiction, and this is the only way to draw one. Simply repeat this process many times and you will almost surely get a contradiction. There are lots of shortcuts that can make your mod bashing work a lot faster, but those are mostly picked up with experience and it is very hard to teach them.

Let’s do another example, except the solution does not involve as much bashing. To my knowledge there does not exist a “nice” solution, i.e. does not take modulo “random” numbers.

Problem 2: Solve $2^x+3^y=5^z$ for positive integers $x,y,z$ .

Solution:

Suppose $a=1$ . Then I claim $2 + 3^b = 5^c$ only has the solution of $b=1,c=1$ . Suppose there is a solution with $c \ge 2$ . Check modulo $25$ to deduce $b \equiv 13 \pmod{20}$ . Now check modulo $11$ to deduce there are no solutions as the LHS is fixed as $7$ , which is not a power of $5$ modulo $11$ due to $5$ being a quadratic residue while $7$ not being one. A similar tactic holds to show $a = 2$ has no solutions.

Now, suppose $a \ge 3$ . Then remark that by checking modulo $4$ we need $b$ to be even so let $b = 2b'$ . So let’s solve $2^a + 3^{2b'} = 5^c$ . Checking modulo $8$ we get $c$ is even so let $c = 2c'$ . Then:

$2^a = (5^{c'} - 3^{b'})(5^{c'}+3^{b'})$

We get $5^{c'} - 3^{b'} = 2^m, 5^{c'}+3^{b'} = 2^n$ for some $m,n$ .
But then $2 \cdot 5^{c'} = 2^m + 2^n$ , forcing $m=1$ . Thus we need $5^{c'} - 3^{b'} = 2$ . But we already showed this only has the solution $b' = 1, c' = 1$ . Thus it follows the only solution where $a \ge 3$ is with $a=4, b = 2, c= 2$ .

Putting every together, we have proven the only solutions are $(1,1,1), (4,2,2)$ . $\square$

We present another problem now.

Problem 3: Find all positive integers $m,n$ such that $9^m - 7^n = 2$ .

Solution: First, note that $(m,n) = (1,1)$ is a solution. Now look at the equation modulo $27$ and we get that $n \equiv 4 \pmod{9}$ (do you see why we can derive this so quickly?). Now, as $\text{ord}_{37}(7) = 9$ we are motivated to look modulo $37$ . First checking modulo $7$ we get $m \equiv 1 \pmod{3}$ . Then as $\text{ord}_{37}(9) = 9$ , it follows we need only check $3$ cases. One deduces there are no solutions for those cases, so it follows $(m,n) = (1,1)$ is the only solution. $\square$

As the technique is rather simple, we shall now close this entry with a few problems the readers can try as this technique is learned much more easily through experience than reading solutions.

Problem 4: (India) Solve the equation $7^x = 3^y + 4$ over the positive integers.

Problem 5: Solve the equation

$2^a \cdot 3^b - 5^c \cdot 7^d = 1$

over the non-negative integers.

Problem 6: (Warning : very computationally heavy) Solve

$2^{e}(2^{c}(2^{a}-3^{d+f+k-2})-3^{f+k-1})=3^{k}+1$

over the positive integers.

Problem 7: Find all positive integer solutions to $2^x - 5 = 11^y$ .

4 Responses to Number Theory #4 : Using Appropriate Moduli to Solve Exponential Diophantine Equations

Sa says:

March 19, 2013 at 3:37 am

excellent

sa says:

March 19, 2013 at 8:41 pm

exSAllent

phamquangtoan says:

August 25, 2013 at 2:52 am

great!! Thank you very much!!

sa says:

October 6, 2013 at 12:06 am

exSAlent the SAcond