Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Solving More Exponential Diophantine Equations with More Modular Arithmetic

Date: 02/02/2011 at 12:49:57
From: Aditya
Subject: Solve the following diophantine equations 

Evaluate or solve, and show your methods:

1. ((2^a) + 1)/(a^2)) for all integers a
2. (a)^b + (b)^a = 2211
3. (a)^a + (b)^b = 1991 
4. 6^a + 8^b = 10^c

I know the answers but I don't know how to attack exponential Diophantine
expressions and equations.

For the first problem, I know that one answer is 1, and another is 3. So I
tried to start upon a proof that might help rule out the even integers.

For the second and the third problems, I tried to form functions, but
these are implict functions, so I couldn't isolate a (or b) on one side.
Taking logarithms was of no use, either.

The fourth one is very typical. I know how to solve in the case a = b = c,
but not otherwise.

Doctor Vogler, please attend to these questions. I am desperately waiting
for answers and methods.



Date: 02/03/2011 at 00:21:29
From: Doctor Vogler
Subject: Re: Solve the following diophantine equations

Hi Aditya,

Thanks for writing to Dr Math. Your second and third problems are pretty
easy, the last one is harder, and the first one is the hardest.

Let's start with the third problem.

First explain why if a is an integer < -1, then a^a is a non-integer
between -1 and +1, but if a is an integer >= -1, then a^a is an 
integer >= -1. Next explain why a and b can't both be less than -1. Then
explain why you can't have one of them less than -1 and the other >= -1.
Conclude that both are >= -1, so a^a and b^b are both >= -1. Explain why
a^a <= 1992. Now list off all integers a (and their corresponding a^a)
that are >= -1 and which also have a^a <= 1992. Now see if there are two
of them that add up to 1991 exactly.

Attacking the second problem follows a very similar line of reasoning.

First explain why you can't have both a and b negative. Show why the
equation makes no sense if one is negative and the other is zero. Continue
by explaining why there are no solutions where one is negative and the
other is one. Then demonstrate why there are no solutions where one is
negative and the other is >= 2. Conclude that both must be >= 0. Explain
why you can't have either variable equal to zero. Conclude that both must
be >= 1. Explain why a^b <= 2211, and why this implies that a <= 2211. Now
you can just try all a and b values less than 2211. 

But with this one, you can even do better. Suppose that a is the larger of
the two numbers a and b. Then explain why b^b <= b^a <= 2211. Now list off
all positive integers b such that b^b <= 2211. There aren't very many. For
each one, you know that a >= 1 and also that a^b and b^a <= 2211, so you
can quickly check all possible a values. What solutions do you find?

For the fourth problem, you should use some modular arithmetic. I hope
that you have used it some in the past, but if not you can get a brief
intro here:

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

Now, if a or b is negative (or both), then 6^a + 8^b will not be an
integer, but rather a rational number with denominator divisible by 2 but
not 5. However, 10^c can't have a denominator unless the denominator is
divisible by 5. Conclude that a, b, and c are all >= 0.

Then 

   10^c = 6^a + 8^b >= 1 + 1

So

   c >= log(2)/log(10) > 0
   
Therefore c >= 1.

Furthermore, the power of 2 in the prime factorization of 10^c is exactly
c, and the power of 2 in the prime factorization of 6^a + 8^b is either a
(if a < 3b) or 3b (if a > 3b) or is greater than a = 3b if they are equal.
So one of the following must hold true:

   c = a < 3b, or
   c = 3b < a, or
   a = 3b < c

But if c > a = 3b, then

   10^c >= 10^(a + 1) > 10^a + 10^a 
                      > 6^a + 2^a   = 6^a + 8^b 
                                    = 10^c

That would be impossible. So we must have one of the other two cases --
namely, c = a or c = 3b.

But if c = 3b, then ...

      6^a = 10^c - 8^b
          = 10^(3b) - 8^b
          = 1000^b - 8^b
   (-1)^a = (-1)^b - 1^b (mod 7),

... which is not possible, since you can only get +1 or -1 on the left,
and only -2 or 0 on the right. Therefore, c = a < 3b.

But then

          8^b = 10^c - 6^a
              = 10^a - 6^a
              = (2^a)(5^a - 3^a)
   2^(3b - a) = 5^a - 3^a

Next I will show that if 5^n - 3^n is a power of 2, and n is a positive
integer, then n = 1 or 2. I will do this by induction on n. The cases 
n = 1 and n = 2 are obvious.

Suppose that n > 1; then

   5^n - 3^n = (3^n)((5/3)^n - 1) > (3)((5/3) - 1) = 2,

Moreover, every power of 2 larger than 2 is divisible by 4. Therefore,

   5^n - 3^n = 0 (mod 4)
         1^n = (-1)^n (mod 4)

This means that n is even. But then

   5^n - 3^n = [5^(n/2) - 3^(n/2)][5^(n/2) + 3^(n/2)]

Since the product is a power of 2, each factor must be a power of 2. But
our inductive hypothesis tells us that if 5^(n/2) - 3^(n/2) is a power of
2, then n/2 = 1 or 2; so n = 2 or 4. 

We already know that n = 2 is possible, but if n = 4, that would mean that
this must be a power of 2:

   5^(n/2) + 3^(n/2) = 25 + 9 = 34

So we have a contradiction.

Now we use our theorem and the equation

   2^(3b - a) = 5^a - 3^a

We already know that 3b - a > 0, so the right side is a power of 2. The
theorem says that a = 1 or a = 2. But that gives

   2^(3b - 1) = 5 - 3 = 2, and 8^b = 4

or

   2^(3b - 2) = 25 - 9 = 16, and 8^b = 64.

Only the second case gives an integer for b, and it gives the only
solution to the problem, which is a = b = 2.

Now we can move on to the *really* hard problem, which you listed first.
Unfortunately, I'm not sure I can solve this one, but I'll say a few
things about it.

You want to find all integers a such that a^2 divides (2^a) + 1, or, in
other words,

   2^a = -1 (mod a^2)

If a is negative, then (2^a) + 1 is not an integer, so neither is this:

   ((2^a) + 1)/a^2

If a = 0, then the quotient makes no sense. Otherwise, a >= 1, so 2^a is
even, which means that (2^a) + 1 is odd. So there are no solutions where a
is even. It only remains to check odd, positive integers. Of course, a = 1
and a = 3 are solutions, but proving that there are no other solutions is
very difficult.

This equation almost looks a bit like Fermat's Little Theorem, but that
requires a prime. So it might be useful to consider a prime factor p of a.

If p is a prime factor of a, then ...

   2^a = -1 (mod p)

... and ...

   2^a = -1 (mod p^2).

Suppose that the order of 2 mod p (or mod p^2) is k. Then a = k/2 mod k,
or (said differently) 2a/k is an odd integer. If we let k1 be the order of
2 mod p and k2 be the order of 2 mod p^2, then for almost all primes p
(and even prime powers), k2 = p*k1. See also ...

   Number Theory and Modular Arithmetic
    http://mathforum.org/library/drmath/view/70472.html 

... and this Wikipedia article:

   Wieferich prime
    http://en.wikipedia.org/wiki/Wieferich_prime 

So I'm thinking that you really want to concentrate on the fact that 2a/k
is odd -- not that 2a/k is an integer. In particular, k must be even for
all p. So that means that a can't be divisible by 7, 23, 31, 47, 71, 73,
79, 89, 103, and many other primes, since the order of 2 modulo each of
those primes is odd (and therefore no power of 2 can be -1 modulo any of
those primes).

Furthermore, since 2a/k must be an integer, and a can't be divisible by 7,
23, and so on, that means that k can never be divisible by 7, 23, and so
on. That rules out a being divisible by 29, 43, 71, 113, and others. And
we can repeat this to get more primes that can't divide a, but iterating
this process won't rule out some of the smallest primes (like 3 and 5) or
a small number of larger primes (such as Fermat primes, for example).

Anyway, I'm running out of insights for that problem. I'll get back to you
if I come up with any more clever ideas that might help us solve it.

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: 02/03/2011 at 22:27:41
From: Doctor Vogler
Subject: Re: Solve the following diophantine equations

Hi Aditya,

After working at it a little longer, I have a solution for your first
problem.

You want to find all integers a such that a^2 divides (2^a) + 1, or, in
other words,

   2^a = -1 (mod a^2).

I already explained why all solutions to this equation are odd, positive
integers. Of course, a = 1 and a = 3 are solutions, and we want to prove
that there are no other solutions.

Now, since a = 3 is a solution, we know that it is possible for a solution
to be divisible by 3. Now I will prove that it can't be divisible by 9,
and then I will prove that it can't be divisible by any prime larger than
3.

Let m be the exponent of 3 in the prime factorization of a. So 3^m divides
a, but 3^(m + 1) does not. The order of 2 mod 3^(2m) is 2*3^(2m - 1). The
link I gave you in my last answer is sufficient to prove this.

Setting k = 2*3^(2m - 1), that means that

   2^k = 1 (mod 3^(2m))

Moreover, if k is even, then

   2^(k/2) = -1 (mod 3^(2m))

But no power of 2 is -1 mod 3^(2m) if k is odd. Since 3^(2m) divides a^2,
if 2^a = -1 (mod a^2), then

   2^a = -1 (mod 3^(2m))

This is equivalent to saying that ...

   a = k/2 (mod k),

... so 2a/k is an odd integer. Well, k = 2*3^(2m-1), and 3^m divides a,
but 3^(m + 1) does not. This means that

  2m - 1 <= m,

This implies that m <= 1. So 3 can divide a, but 9 cannot.

Next I need to show that no primes larger than 3 can divide a. So let's
suppose that some prime could divide a.

Let p be the smallest prime that is larger than 3 and is a factor of a.
Let k be the order of 2 mod k.

Since p divides a and a^2 alike, 2^a = -1 (mod a^2) requires 
2^a = -1 (mod p). As above, this requires that 2a/k is an odd integer. But
k has to be a factor of p - 1. It has to be even, or else 2a/k can't be
odd, but it can't be divisible by 4, since a is odd and therefore 2a is
not divisible by 4. It might be divisible by 3, but it can't be divisible
by 9, because a isn't divisible by 9. Every other prime factor q of k must
be smaller than p, since k itself is smaller than p - 1. But such a q
would then have to be a factor of a as well, and then q would be a prime
factor of a that is larger than 3 but smaller than p, which is impossible
since p is the smallest prime factor of a > 3. So the only primes that
can divide k are 2 and 3, and 2 must divide exactly once while 3 can
divide at most once. That means that either k = 2 or k = 6. So the order
of 2 mod p is either 2 or 6.

In either case, ...

   2^6 = 1 (mod p),

... which means that p must be a factor of 2^6 - 1 = 63.

Since 63 = 3 * 3 * 7, that means that p must be either 3 or 7. But we
assumed that p > 3, so the only option is p = 7. But if p = 7, then the
order of 2 mod p is k = 3 (not 6), which is not even and therefore no
power of 2 can equal -1 mod 7.

So we come to the conclusion that a can't be divisible by any prime larger
than 3. Since we already know that it can't be divisible by 2, and it can
only be divisible by 3 once and not twice (that is, divisible by 3 but not
9), the only options are a = 1 and a = 3. We already know that those two
are solutions, and now we have proven that there are no more solutions.

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



Date: 02/04/2011 at 10:28:59
From: Aditya
Subject: Solve the following diophantine equations

Thank you, Doctor Vogler, for giving your precious time on these
questions.

With your help, I think the answers for the second question are 2210 and 1
only.

For the third one, I think there are no integer solutions.

And your reasoning on the first question is crystal clear, but I want to
ask: is there a method other than modular arithmetic?

Please try again.



Date: 02/04/2011 at 21:16:41
From: Doctor Vogler
Subject: Re: Solve the following diophantine equations

Hi Aditya,

There are often more than one way to solve a math problem. What's the
other method to attack the first question?

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



Date: 02/04/2011 at 23:08:27
From: Aditya
Subject: Solve the following diophantine equations

Thanks once again, Doctor Vogler.

Yes, I want to think about approaching the first question without
resorting to modular arithmetic. Can you suggest a different direction for
me?



Date: 02/04/2011 at 23:40:18
From: Doctor Vogler
Subject: Re: Solve the following diophantine equations

Hm ...

If there's another strategy, I don't know what it is.

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



Date: 02/05/2011 at 00:13:49
From: Aditya
Subject: Solve the following diophantine equations

Okay, sir.

Thank you very much for the kind help and due attention.
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/