0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Do you have Chinese Remainder Theorem available? $\endgroup$ – paw88789 Jan 9 '18 at 17:00
  • $\begingroup$ I didn't use it. could you give me a clear example ? thanks $\endgroup$ – al3ndaleeb Jan 9 '18 at 21:34
  • $\begingroup$ 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! $\endgroup$ – Amin235 Jan 9 '18 at 21:55
  • $\begingroup$ 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 $\endgroup$ – al3ndaleeb Jan 10 '18 at 14:55
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – al3ndaleeb Jan 11 '18 at 21:29
  • $\begingroup$ 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 :) $\endgroup$ – al3ndaleeb Jan 11 '18 at 21:39
  • $\begingroup$ @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!) $\endgroup$ – paw88789 Jan 12 '18 at 1:53
  • $\begingroup$ I was thinking in the properties I had found inside this problem will guide me to find that. Thank you so much for answer. $\endgroup$ – al3ndaleeb Jan 12 '18 at 8:22
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I reached to this answer but I need all values under N. I will edit my question $\endgroup$ – al3ndaleeb Jan 9 '18 at 16:34
  • $\begingroup$ I hope you read my last update. thanks $\endgroup$ – al3ndaleeb Jan 10 '18 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.