0

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 ?

al3ndaleeb
  • 13
  • Do you have Chinese Remainder Theorem available? – paw88789 Jan 09 '18 at 17:00
  • I didn't use it. could you give me a clear example ? thanks – al3ndaleeb Jan 09 '18 at 21:34
  • If I wanted to brute force by the number $N$ with $n$ digit. First, I choose a number with $n+1$ digits and called it $K$. Then I check that if $N$ is divisor of $K-1$ or $K+1$ since $K^2-1=XN$. Maybe useful! – Amin235 Jan 09 '18 at 21:55
  • The brute force is good idea for small numbers ( 2 digit ..to.. 10 digit ) but when you work with big than this it will be very slow to find the result. I hope you read my last update. thanks – al3ndaleeb Jan 10 '18 at 14:55

2 Answers2

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$

asdf
  • 4,587
0

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.

paw88789
  • 40,402
  • Thank you so much for your interesting. The methods you have explained will open my mind to think deeply in this problem. Only one question remain about your methods. In case N was very big and I can't factor it, what can I do in this case ? how can I find (u,v) values ?. Thanks alot – al3ndaleeb Jan 11 '18 at 21:29
  • I have found something strange in this problem. In your example you extracted X values $( 15, 24 )$. when you multiplied them and add one to the result you will get a perfect square value. $15 * 24 + 1 = 19^2$. also in my example above, X values was $( 7560, 33109 )$ and $ 7560 * 33109 + 1 = 15821^2$. LoooL it's a magic. I really loved this problem :) – al3ndaleeb Jan 11 '18 at 21:39
  • @al3ndaleeb: If you can't factor $N$, these methods won't work. And in fact finding a nontrivial solution to $k^2\equiv 1 \pmod{N}$, for odd $N$, leads to a nontrivial factorization of $N$. So there isn't going to be an easy way to solve this problem for a composite odd $N$ that you can't factor. (If there were an easy way, you would be able to have a fast factorization method!) – paw88789 Jan 12 '18 at 01:53
  • I was thinking in the properties I had found inside this problem will guide me to find that. Thank you so much for answer. – al3ndaleeb Jan 12 '18 at 08:22