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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.