How to get a perfect square with this condition?

Question

I'm looking for a mathematical method to find an integer X if I multiplied by N and add one on the result will get a perfect square value. $$X * N + 1 = (Perfect Square)$$ I need all X values under N

---

Example:

$N = 72311$

I found X can be:

$7650 , 33109, 72309$

$7560 * 72311 + 1 = 23381^2$

$33109 * 72311 + 1 = 48930^2$

$72309 * 72311 + 1 = 72310^2$

---

I programmed a small application in PHP as brute force application to find all X values less than N, but if N was very big more than 15 digit, it takes a long long time to give me the answer.

<?php
$n = 72311;
$N = gmp_init($n);
for($i = 2; $i < $n; $i++)
{
 $x= gmp_add(gmp_mul($N, $i), 1);

    if(gmp_perfect_square($x))
  echo $i."\n";
}
?>

So could you help me in a mathematical method to give me the answer without using a brute force method ?

Thanks in advanced

---

Update :

I have found something may be useful to find a solution to this problem.

I have used multiplicative modular inverse with the square roots and it equals itself!

$$\sqrt{PerfectSquare}^{-1}\mod N = \sqrt{PerfectSquare}$$

Apply on previous example:

$23381^{-1}\mod 72311 = 23381$

$48930^{-1}\mod 72311 = 48930$

$72310^{-1}\mod 72311 = 72310$

So I will add another question to my first question.

How can I find these values instead of searching about X values ?

Answer 1

Here are two ways I can see of approaching the problem:

Method 1:

I am assuming $N$ is positive.

If you can factor $N$ into $N=ab$ where $a, b> 0$ and $\gcd(a,b) \le 2$, then you can find positive integers $u$ and $v$ for which $au-bv=2$. (Such $u$ and $v$ can be found by means of the extended Euclidean algorithm in general.)

Let $X=uv$.

Then $N\cdot X+1=abuv+1=au(au-2)+1=(au-1)^2$.

Example:

Let $N=77=7\cdot 11$. Note that $7\cdot 5-11\cdot 3=2$.

So $X=5\cdot 3=15$ should be a solution.

And indeed, $77\cdot 15+1=1156=34^2=(7\cdot 5-1)^2$.

Also for this example, we have $11\cdot 4-7\cdot 6=2$.

So $X=4\cdot 6=24$ should be a solution. (I leave it for you to check.)

Method 2:

Note that $N\cdot X+1=k^2$ is equivalent to $k^2\equiv 1\pmod{N}$. If $N$ can be decomposed into nontrivial relatively prime factors, the above congruence can be solved (nontrivially) using the Chinese Remainder Theorem.

Answer 2

A trivial thing you can do is take $X=N-2$ or $X=N+2$.

Then we have that $X\cdot N+1=N^2-2N+1=(N-1)^2$ or $X\cdot N+1=N^2+2N+1=(N+1)^2$