Exponential Diophantine EquationsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/