Challenging Diophantine Equation

Date: 09/30/2004 at 21:14:07
From: Hannah
Subject: diophantine equations

Find all solutions of 2^m = 3^n + 5.  It has only 2 solutions.  I
thought I had the answer as I have shown it had 2 solutions but it 
was pointed out I made an error in the calculations.  

The case bothering me is when I have shown m has to be of form 4k+1
and n of the form 4K+3 for some k,K and further that K has to be even
to ensure 3^(4K+3)+5 is congruent to 0 mod 32.  

What I'm trying to show is then although it is 0 mod 32, it has an odd
factor, but it is not proving that easy.  What I get is that
3^(4K+3)+5=32m where m ends in 6 or 1, so I am close but can't quite
get the last part.  Any pointers will be most appreciated.

Date: 10/26/2004 at 11:58:26
From: Doctor Vogler
Subject: Re: diophantine equations

Hi Hannah,

Thanks for writing to Dr. Math.  I'm terribly sorry about the delay in
replying to you.  You had a hard problem, and no one had a good
solution, so it went on by and was soon lost.

But I love Diophantine equations, so I kept thinking about it.  And I
think I'm getting somewhere, so I'll tell you what I've done.  I hope
it's not too late to give you a response.

You see, my first thought is to use modular arithmetic, since that's a
great way to solve these kinds of integer exponent problems.  But it's
made difficult by the fact that there are already two solutions.

I'd like to say:  Find some number M and consider all of the powers of
2 mod M, and all of the powers of 3 mod M, and find all of the pairs
whose difference is 5 mod M.

Of course, if you just pick any old M, then there will probably be 
lots of solutions.  But if you pick some M so that 2 and 3 have
(relatively) small order, then you get better results.  For example,
take M = 511.  Then the order of 2 is 9, and the order of 3 is 12, so
there are only 9 powers of 2 and only 12 powers of 3, and hence only
9*12 = 108 differences, and it turns out that only 2 of them equal 5.
So we can conclude that if

  2^m = 3^n + 5 (mod 511)

then either

  m = 3 mod 9  and  n = 1 mod 12, or
  m = 5 mod 9  and  n = 3 mod 12.

But the problem is that (1, 3) and (3, 5) are solutions to the 
equation.  So no matter what M we choose, there will always be two
possible solutions.

But that is only true if M is not divisible by 2 or 3.  The idea is to
realize that we must have something that distinguishes between small m
and n and large m or n.  So we let M be a power of 2 or a power of 3.
For example, we want to prove that there are no solutions with n > 3,
so let's choose some M so that the 3^n term disappears, but not until
n > 3.  So we choose M = 81, and consider

  2^m = 3^n + 5 (mod 81).

Now, we wonder if there are solutions with n > 3.  So we assume that 
n > 3, and that changes our equation to

  2^m = 5 (mod 81).

Well, 2 has order 54 mod 81, and all solutions to this equation have

  m = 23 (mod 54).

The very important thing here is that this is not 3 or 5!

Similarly, we can choose M to be a power of 2, and we want the 2^m
term to disappear, but not until m > 5.  So we let M = 64, and then
consider

  2^m = 3^n + 5 (mod 64).

Again, if we assume that m > 5, then 2^m is zero mod 64, so this
equation is

  3^n = -5 = 59 (mod 64).

We find that all solutions to this equation have

  n = 11 (mod 16).

Again, the important thing is that this number is not 1 or 3!

Now we just have to find a big M like the ones I discussed earlier (so
that the orders of 2 and 3 are small) which contradicts one of these
two statements.

The trouble is that if the order of 3 is not divisible by 27 (half of
54), then the solution

  m = 5  and  n = 3

will fit our requirement for m.  And if the order of 2 is not
divisible by 16, then that same solution will fit the requirement for
n.  So we want the orders of 2 and 3 mod M to be pretty small, so that
there aren't lots and lots of solutions, but at least one of them has
to be big enough to be divisible by 27 or 16 (respectively).

So we look around for such an M.  A computer search helps.  And I
found M = 697.  The order of 2 is 40, and the order of 3 is 16.  I
checked all 40*16 pairs of a power of two and a power of 3, and the
only ones which have

  2^m = 3^n + 5 (mod 697)

are

  m = 3 mod 40  and  n = 1 mod 16, and
  m = 5 mod 40  and  n = 3 mod 16.

Of course, neither of these has

  n = 11 mod 16,

so there can be no other solutions.

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/