Exponential Diophantine Equations

Date: 06/26/2005 at 16:56:16
From: OC
Subject: Exponential Diophantine equations

I'm wondering how to solve the following Diophantine equation.  I need
to get as many non-trivial solutions as possible.

  a^A = bB + c^C as a,b,c are given and relatively prime.

And what about this one?

  a^A*b^B = cC + d^D*e^E as a,b,c,d,e are given and relatively prime

And this one?

  a^A*b^B*c^C = dD + e^E*f^F*g^G as a,b,c,d,e,f,g are given and 
relatively prime

What about solving this general form

  a1^A1*a2^A2*a3^A3...*an^An = bB + c1^C1*c2^C2*c3^C3...*cm^Cm as
ai,b,cj are given and relatively prime for i=1 to n ,j=1 to m where
m,n >=1 and b>=1

I used a brute force algorithm, but I'm wondering if there is a better
way?

Date: 06/28/2005 at 21:10:22
From: Doctor Vogler
Subject: Re: Exponential Diophantine equations

Hi OC,

Thanks for writing to Dr. Math.  Let's look at that first equation

  a^A = b*B + c^C

given integers a, b, and c.  First let's suppose that b = 1.  Then the
equation is easy!  We can pick any positive integer C, and any
positive integer A, and then set

  B = a^A - c^C.

Voila!  So the only thing that complicates the problem is when b is 
not 1, how do we choose A and C so that a^A - c^C is a number
divisible by b?  And anytime you ask the question when is something
divisible by some constant, you fall back to modular arithmetic.  If
you are unfamiliar with the subject, you can start here:

  Mod, Modulus, Modular Arithmetic
    http://mathforum.org/library/drmath/view/62930.html 

If you are familiar with the subject, then you may proceed as follows.
The only part you need to worry about is how to choose A and C so that

  a^A = c^C (mod b).

Then you can set

  B = (a^A - c^C)/b.

So how do we choose A and C?  Well, first we ask what happens to 
powers in modular arithmetic.  The answer is that they cycle.  In 
fact, since a and c are relatively prime to b, that means we can
compute the number phi(b)

  Totient Function
    http://mathworld.wolfram.com/TotientFunction.html 

and then

  a^phi(b) = 1 (mod b)
  c^phi(b) = 1 (mod b).

That means that one way we can choose A and C is to make sure both
sides of the equation are 1 mod b.  That is, choose A to be any
multiple of phi(b) and choose C to be any multiple of phi(b).  Then
define B as above.  And there you are!  Infinitely many solutions to
your equation with very little effort.

But we can do even better!  We can describe *all* solutions!  For
that, you'll need a little more theory, and a little more work.  We
could *almost* choose C to be any number at all, and then choose A so that

  a^A = c^C (mod b).

Then you can add any multiple of phi(b) to C, or any multiple of the
order of c mod b (which will be a divisor of phi(b)).  And this works
for *most* numbers a, but not *all* numbers a.  More correctly, we
should find a primitive root mod b, and call it r.  That is a number
whose *smallest* power that is 1 mod b is phi(b).  There are typically
lots of them available (and often times a or c are primitive).  Then
you can write

  a = r^i
  c = r^j.

Now your equation is

  (r^i)^A = (r^j)^C (mod b)
  r^(iA) = r^(jC) (mod b)

which is true if and only if

  iA = jC (mod phi(b)).

So as long as A is a multiple of gcd(phi(b),j), you can find a C that
satisfies this equation.  And then you can add to C any multiple of
the order of c mod b, which is phi(b)/gcd(phi(b),j).  Then B is

  B = (a^A - c^C)/b.

And this will, in fact, give you all solutions.


As for the other equations, providing more variables only allows more
solutions.  For example, in the equation

  a^A * b^B = c*C + d^D * e^E,

you can simply take B = 0, E = 0, and then you have the first case,
and you can find infinitely many solutions of that equation. 
Alternately, you can do the same kind of analysis.  All you need is

  a^A * b^B = d^D * e^E (mod c).

So you can almost let A, B, and C be any numbers at all, and then find
some E that will satisfy the equation.  Or, better yet, you can find a
primitive root r, and then get exponents

  a = r^i
  b = r^j
  d = r^k
  e = r^l

and then you only need to satisfy the linear equation

  iA + jB = kD + lE (mod phi(c)),

for which you can get a parametric solution with three parameters.

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/