Solving an Exponential Diophantine Equation with Modular Arithmetic

Date: 11/23/2005 at 07:36:15
From: Amar
Subject: number theory

Solve for positive integers a,b,c:

  (5^a)*(7^b) + 4 = 3^c

eg  a = 1, b = 0, c = 2 is a solution.

Date: 11/23/2005 at 22:00:13
From: Doctor Vogler
Subject: Re: number theory

Hi Amar,

Thanks for writing to Dr. Math.  What you have is an exponential
Diophantine equation.  Finding all solutions (in positive integers)
for such an equation is not an easy task.  Many such equations can be
solved using modular arithmetic, often quite a bit of modular arithmetic.

  Mod, Modulus, Modular Arithmetic
    http://mathforum.org/library/drmath/sets/select/dm_mod.html 

There are some exponential Diophantine equations that simply won't
fall to modular arithmetic, and then more sophisticated ideas must
come into play.  The most usual is Baker's method, which uses linear
forms in logarithms.  That is, Alan Baker and others have proven
various results about how small an expression like

  a log 5 + b log 7 - c log 3

can be, where a, b, and c are integers (or rational numbers, or even
algebraic numbers).  Of course, it can be arbitrarily small, but that
would require a, b, and c to be very large (or to have very large
numerators or denominators, or to have large "height").  So the lower
bound that you get depends on a, b, and c.  This method generally gets
you some very large upper bounds on a, b, and c, which you can reduce
using lattice reduction (also called LLL after three mathematicians
who first developed this technique), and then a computer search will
finish the problem.  This method tends to take a lot more work,
however, so we like to use the modular arithmetic method when we can.
Let's give it a try.

Now, if you had an exponential Diophantine equation with no solutions,
like

  7^b + 4 = 3^c,

then you would like to find some modulus m so that

  7^b + 4 = 3^c (mod m)

has no solutions, because then you could check all of the powers of 7
mod m, and all of the powers of 3 mod m (there are finitely many of
each), and if none of them give you solutions, then there are no
solutions in positive integers to your equation.


But consider what happens if we know that there is a solution, such as

  5^a + 4 = 3^c

has the solution a=1, c=2.  Then, at least if m is not divisible by 3
or 5, then no matter what m we choose, the best we might be able to
hope to conclude is that

  a = 1 (mod the order of 5 mod m), and
  c = 2 (mod the order of 3 mod m),

which will never be enough to conclude that a=1 and c=2 is the only
solution.  So we must choose some m that is divisible by a power of 3
or 5 that is _larger_ than the largest solution to the equation.  That
means that we should start with either m = 27, or m = 25.

Notice also that the Chinese Remainder Theorem says that we can do
this in stages; we can use lots of different moduluses (and we can
limit ourselves to powers of primes if we like), and see what each one
tells us about a, b, and c.  So let's give this a try and see what we get.

Before I get to the details, I'd like to say a few words about how I
came up with what I'm about to say:  I made extensive use of GNU Pari
for many of these calculations.  You can download that very nice math
program for free at

    http://pari.math.u-bordeaux.fr/ 

Now, I didn't know what moduluses would be the ones I would need, so I
tried lots of them to see what each could provide me.  I already told
you why 25, 27, 7, 49, and similar powers of 3, 5, and 7 would be
useful.  For other numbers (co-prime to 3, 5, and 7), I used the
following Pari instructions to find all solutions in that modulus:

  r=znorder(Mod(5,m)); s=znorder(Mod(7,m)); t=znorder(Mod(3,m));
  for(a=0, r-1, for(b=0, s-1, for(c=0, t-1,
  if(Mod(5,m)^a * Mod(7,m)^b + 4 - Mod(3,m)^c == 0,
  print([a,b,c]))))); [r,s,t]

(take out the line breaks before entering this as one line into Pari).
In choosing moduluses, I tried to find ones where 3, 5, and 7 have
relatively small order.  It's hard to get all three numbers of small
order, but you do what you can.  One way to find these is to pick a
small order k and then find all moduluses where, say, 3 has order
dividing k.  Those will be the ones dividing 3^k - 1, so we ask Pari

  factor(3^12-1)

and so forth.  And we can do two at once with

  factor(gcd(3^12-1,5^12-1))

and similar things.

Then I tried combining these to find as much as I could about a, b,
and c (in the form of various congruences) until I got a 
contradiction.  For starters, I assumed that a, b, and c were as large
as I needed them to be (for mod 25, 27, 49, etc.).  But, of course, I
didn't use all of those assumptions.

So, first I will try to eliminate the possibility of additional large
solutions, and I will start by trying mod 3.  I expect you already did
this, so it should be review.  It is clear that c=0 does not give any
solutions, since

  3^c - 4 = 1 - 4 = -3

is not a power of five times a power of 7.  So 3^c is divisible by 3,
which means that

  (5^a)(7^b) + 4 = 3^c = 0 (mod 3),

which can be simplified as

  (-1)^a = -1 (mod 3),

from which we conclude that a is odd.  Now we reduce mod 8:

  (5^a)*(7^b) + 4 = 3^c (mod 8).

Now, 5^2 = 1 mod 8, and a is odd, so that means that 5^a = 5 mod 8. 
Also, 3^2 = 1 mod 8, so 3^c = 1 or 3 mod 8, and we multiply both sides
of the equation by 5 to simplify things, and we get

  5^(a+1) * (-1)^b = 5*(3^c - 4) (mod 8)
  (-1)^b = 1 (mod 8), if c is even,
      or = 3 (mod 8), if c is odd.

which implies that b is even, and (though we won't need this) c is even.

Now, like I already said, at some point we have to use a modulus that
is a higher power of one of our bases than the solution we already
know, because otherwise we would end up proving that there are no
solutions at all.  So now we use the modulus 25, and here is where we
need to assume that a is at least 2, so that

  (5^a)(7^b) + 4 = 3^c (mod 25)

becomes

  4 = 3^c (mod 25).

Well, 3 has order 20 mod 25, and

  4 = 3^6 (mod 25),

so that means that

  c = 6 (mod 20).

In particular, it is important that c = 1 mod 5.  Because the clincher
is mod 11.

  3^5 = 1 (mod 11),

so

  3^c = 3^1 = 3 (mod 11),

and therefore

  (5^a)(7^b) = -1 (mod 11).

We check all the possible solutions to this equation, and we find that
b must be odd.  But we already determined that b was even.

So that means that if a >= 2, then there are no solutions.  So now we
only have to check two more cases:  Namely, a = 0 and a = 1.

We already know there will be a solution with a = 1, so let's see if
we can eliminate the case a = 0 first, as it will probably be easier.
Then we have the equation

  7^b + 4 = 3^c

that I mentioned at the beginning.  I did a similar analysis on this
equation as on the previous, only I didn't have to worry about getting
around known solutions, and I only had two bases (3 and 7) to concern
me.  (It's easier to get two numbers with small order than three.)  From

  (-1)^b = 3^c - 4 (mod 8),

I get that b and c must both be odd.  That, together with

  7^b + 4 = 3^c (mod 13)

told me that b is divisible by 3.  Choosing a factor of (7^3 - 1), I
find that

  3^c = 7^b + 4 = 1 + 4 = 5 = 3^4 (mod 19),

where 3 has order 18, implies that c can't be odd.  So there are no
solutions to

  7^b + 4 = 3^c.

So we will be done if we can show that the only solution with a = 1,
that is, the only solution to

  5*7^b + 4 = 3^c

is a = 1, b = 0, and c = 2.

Now b = 0 implies that

  3^c = 5 * 1 + 4 = 9,

and therefore c = 2.  So let's show that there are no solutions with b
positive.  Let's try mod 7.  If b is positive, then

  4 = 3^c (mod 7)

implies that

  c = 4 (mod 6).

So now let's pick another factor of (3^6 - 1) and try

  5*7^b + 4 = 3^c (mod 13).

Since

  3^3 = 1 (mod 13),

we know that

  3^c = 3^4 = 3^1 = 3 (mod 13),

and

  5*7^b + 4 = 3 (mod 13)

implies that

  b = 3 (mod 12).

And then

  7^3 = 1 (mod 19)

implies that

  5*1 + 4 = 9 = 3^2 = 3^c (mod 19)

and therefore

  c = 2 (mod 18)

which contradicts

  c = 4 (mod 6).

And so we are done!  The only solution in nonnegative integers is the
one you mentioned.  And, of course, there are no solutions with
negative integers, since this would give a fraction on at least one
side of the equation, and the other side couldn't have the same
denominator.  So the only solution in integers is

  a = 1, b = 0, and c = 2.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/24/2005 at 15:13:52
From: Amar
Subject: Thank you (number theory)

Thank you very much for the solution--it was great!  But I have a
question.  How should we decide which number should be used for the
mod?  Is there any definite strategy?  I would not have thought of
using a modulus of 13, 19 or 25.

Date: 11/24/2005 at 20:26:22
From: Doctor Vogler
Subject: Re: Thank you (number theory)

Hi Amar,

Like I said, I found useful moduluses by two methods.  One method was
to try lots of things (like small primes) and use ones where the bases
in your equation, namely 3, 5, and 7, have relatively small order (in
particular, they are not primitive roots).  The math program Pari was
useful for doing this quickly.  The other method was, especially when
I knew an exponent mod some number k, and I wanted a modulus where
that base (say 7) had order dividing k, then I would pick a prime
factor of (7^k - 1), because the order of 7 mod m divides k if and
only if m divides (7^k - 1), right?  And I already explained why you
would want to use powers of your bases (3, 5, and 7) higher than what
you have in your known solution.

Perhaps I should add one more point, that I didn't mention.  To get
started on solving this kind of equation, I assume that a, b, and c
are large and try the equations mod powers of them.  I try to write
congruences that a, b, and c have to satisfy in order to solve those
equations.  Then I try those "useful" moduluses that I mentioned
already, ones where the bases had relatively small order.  I had Pari
list off all solutions, and I recorded the ones that also satisfied
previous conditions.  I kept doing this until I found a contradiction,
i.e. too many conditions for one of the exponents to satisfy.  Then I
went back and cleaned things up by seeing which moduluses I really
needed to get this contradiction, and which ones gave me information
that I never used, and also what assumptions about the size of the
exponents I really used (e.g. I needed a >= 2).  I gave you the
cleaned-up version, with some description of how I got there.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/