1
$\begingroup$

I am trying to solve the following equation:

n*const1 + const2 = x^2 

Where n, const1, const2 and x are integers > 0. Const1, const2 are known, n and x are variables.

The naive solution to this problem is to iterate all n's and check if the square root of the result is integer. This solution is however too slow:

for n = 0;; n++:      if sqrt(n*const1 + const2) is integer:          end.      else:          continue. 

Would it help, if the const1 was a prime number?

  • 0
    What about dividing `x^2` by `const1` and see if the remainder is equal to `const2`? (You need to reduce `const2` in some way before to guarantee `const2` is between `0` and `const1 - 1`. I think `const2 := const2 mod const1` should work.)2012-08-14
  • 0
    Having const$1$ prime helps in several ways. First there is a relatively cheap computation (keyword: Legendre symbol) for finding out **whether** there is a solution. Then there are many good algorithms for finding an actual solution. Much better than quasi brute force search, for large numbers.2012-08-14
  • 0
    The trick is to first figure out if there is a solution(refer to Andre). For example 3n+2 is never a square number (why?). Once, you know this, you can figure out the maximum number of n's to test (how?). The rest is easy.2012-08-14
  • 0
    Actually, my problem is not knowing whether there is solution. I know there is one. And I want to find it as fast as possible. Knowing "maximum number of n's to test" does not help, because I still need to test them and testing them all is slow. There must be some better way.2012-08-18
  • 0
    Andre: "Then there are many good algorithms" - for instance which one? :-)2012-08-19

3 Answers 3