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