Integer Solutions to a^2 - b^2 = k for a Given Integer kDate: 05/07/2005 at 03:35:52 From: Davin Subject: Find integers a and b such that a^2 - b^2 = k, for a known k I'm trying to find a way, given a (potentially very large) integer k, to determine two integers such that the difference of the squares is equal to k. For instance, if k = 21, then an answer would be a = 5 and b = 2 since 5^2 - 2^2 = 21. Firstly, it's clear that a must be >= sqrt(k). Secondly, an alternative way of stating the problem is this: find an integer b such that k + b^2 is a perfect square. I believe that there will only be one possible a, b for a particular k (excluding negative values and zero), and that some values of k will have no answer for a and b. Date: 05/07/2005 at 16:02:30 From: Doctor Vogler Subject: Re: Find integers a and b such that a^2 - b^2 = k, for a known k Hi Davin, Thanks for writing to Dr. Math. You can also write your equation as (a + b)(a - b) = k. Then a + b has to be one (integer) factor of k, and a - b is the corresponding factor. That is, if a + b = f is a factor of k, and a - b = g = k/f is the corresponding factor, then a = (f + g)/2 b = (f - g)/2. In other words, finding a and b is essentially equivalent to factoring k. So if you want to find ALL integer solutions, then you must factor k. Of course, this might be difficult if k is terribly large, but there is no way around it, since finding all integer solutions really does factor k. (In other words, if you could do it in some other way, then you would have found a new way to factor k.) For some good methods for factoring large numbers, see Factoring Algorithms http://mathforum.org/library/drmath/view/65455.html Now, there is one other issue, which is that f and g have to have the same parity; that is, they must either both be even or both be odd, so that a and b will be integers. Therefore, if k is divisible by 2 but not by 4, then there are no solutions, because one of f and g would have to be even, and the other would have to be odd. If k is odd, then any factor f will be odd and will give g = k/f odd, and therefore a and b will be integers. If k is divisible by 4, then f and g must both be even. In other words, f/2 can be any factor of k/4, and each such factor will give a solution for a and b. So that's the idea: If you want all integer solutions, then you have these cases: Case 1: k is odd. Then you factor k and list off all of its factors (and don't forget that every factor will appear once as a positive and once as a negative). Let f be each one in turn, and for each one compute g = k/f a = (f + g)/2 b = (f - g)/2, and those will give you all solutions. Case 2: k is even, but not divisible by 4. Then there are no solutions, for the reasons I gave above. Case 3: k is divisible by 4. Then you factor k/4 and list off all of its factors (see note in case 1). Let f be TWICE each factor in turn, and for each one compute g = k/f a = (f + g)/2 b = (f - g)/2, and those will give you all solutions. Finally, if you just want one solution, and you don't want to factor k, then you can use the obvious factorization (1, k) for odd k, or (2, k/2) for even k. These give you the solutions a = (k + 1)/2, b = (k - 1)/2, and a = (k/4) + 1, b = (k/4) - 1, respectively. 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-2015 The Math Forum
http://mathforum.org/dr.math/