Integer Solutions to a^2 - b^2 = k for a Given Integer k

Date: 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/