# How to solve $x^2 - ny - 2 = 0$ for integer solutions, with different coefficients of $y$?

$$x^2 - ny - 2 = 0, n \in Z$$

I put this equation in wolframalpha, and got integer solutions for random n = 7, 23, 31, 47, 49, 71, 73, 343.

for n = 7 it gave the integer solutions as $$x = 7 n + 3, y = 7 n^2 + 6 n + 1, n \in Z$$ $$x = 7 n + 4, y = 7 n^2 + 8 n + 2, n \in Z$$

and for n = 23 it gave the integer solutions as $$x = 23 n + 5, y = 23 n^2 + 10 n + 1, n \in Z$$ $$x = 23 n + 18, y = 23 n^2 + 36 n + 14, n \in Z$$

It was noteworthy that the sum of free numbers in x is always equal to n (i.e. coefficient of y). 7 had 3 and 4 as free-x-values, 23 had 5 and 18 as free-x-values, and so on. So, as we can see, those free-x-values are always smaller than n.

For some values (like even numbers) there weren't any solutions shown, So I guess there weren't any. But as most of these have only 2 integer solutions, some had 4 integer solutions, like 511 for an example, which had 2 pairs of free-x-values, adding to 511.

My question is, how do I determine if the equation has only exactly 2 solutions, or more than 2 solutions, for a given value of n (i.e. coefficient of y)?

I'm not particularly concerned with the solutions themselves, just that the number of solutions is just 2 or more than that. I can't try values one by one, as the coefficient of y can get large. Wolfram isn't (understandably) handling that big numbers, so I'm trying to write code to solve these equations, but as I don't know what is going on behind the scenes, I can't do anything.

Also, let's say if I find the 1st (smallest) solution, and the 4th (as their sum is predetermined). Can I use them to find the other two (2nd and 3rd) solutions, if they exist?

I looked into Diophantine equations of degree two, but the examples I found had all variables of second degree in them. So, I'm not sure if it qualifies for that. If if still does, please let me know. I tried to solve the equation as a quadratic equation, but got stumped as the coefficient of $$y^2$$ is 0.

My mathematical background is only upto basic highschool level. So, if I need to study some field(s), to be able to solve this, please guide me, as I'm willing to study to solve this problem.

• Don't you mean $\equiv$ instead of $=$? – Some Guy Feb 1 at 20:42
• You would want to become familiar with modular arithmetic and quadratic residues. Your question is basically asking "when is $2$ a quadratic residue modulo $n$?". This has a very exact answer when $n$ is prime (the law of quadratic reciprocity), and from primes we can find a result for all $n$. – jlammy Feb 1 at 21:00
• As radekzak said, a set of integer solutions is available when $\space n=p^q\space$, a prime number to any positive power $\space q\space$ where $\space p\equiv \pm1\mod 8\qquad$ Under $100,\space p\in\{7, 17, 23, 31, 41, 47, 49, 71, 73, 79, 89, 97\}$ The number of solutions is twice the number of prime factors of $\space n.\quad$ Aside, there are also solutions for $n=1$ and $n=2$ – poetasis Feb 1 at 22:22
• That sign means modular congruence. It basically means two numbers have the same remainder. Example, 2 $\equiv$ 6 in modulus 2. I assumed you meant modular congruence instead of equal, because otherwise your equation would be finding what quadratics have integer roots @rohitanshu – Some Guy Feb 2 at 4:48
• @rohitanshu Forget the $1$ and $n$ factors. Each $n$ has $\space 2(2^{k-1})\space$ solutions where $k$ is the number of distinct prime factors of $n.\quad$ For example, $2737=7*17*23\space$ has $2(2^{3-1})=8\space$ solutions. Oddly, if we have $2$ as a factor, the numbers are sometimes different. e.g. $2$ has $1,\;2p$ has $2,\;2p_1p_2\space$ has $4,\;$ and $2p_1p_2p_3 \;$ has $5,\;2p_1p_2p_3p_4 \;$ has $10$ but $p_1p_2p_3p_4$ has $16$ solutions. If we confine ourselves to the primes listed earlier, the formula above works every time. – poetasis Feb 2 at 5:16

## 1 Answer

Well, if you would have $$n|x^2-2$$, then putting $$y = \frac{x^2-2}{2}$$ gives us a legitimate solution. So we only need to be worried about solutions to that divisibility.

You can easily see, that if $$x$$ is a solution, then $$n-x$$ and $$n+x$$ are also solutions. That yields your observation with summing up to $$n$$.

Now we will focus on the set $$S$$ of such $$n$$, that some solution exists.

If $$k$$ and $$l$$ are coprime numbers in $$S$$, then using Chinese Remainder Theorem we can find solution for $$kl$$. Moreover, the number of solutions for $$kl$$ will be equal to the product of these numbers for $$k$$ and $$l$$. We also see quite obviously that if $$n \in S$$, then all divisors of $$n$$ are in $$S$$.

From these two facts, we only need to be worried about $$n$$ equal to prime powers. It is not very easy to prove that $$n=p^k$$ works iff $$n=2$$ or $$p \equiv 1,7 \pmod 8$$, but you should be able to find proof of this fact in any materials about quadratic residues (here, for example, $$2$$ is a quadratic residue mod $$n$$, since $$x^2 \equiv 2 \pmod n$$).

So, solutions exist for $$n$$ iff all of its prime divisors are $$2$$ or primes $$\equiv 1$$ or $$7 \pmod 8$$, where $$2$$ can show up only once (so $$n$$ can't be divisible by $$4$$, but it can be even). Number of these solutions (or, to be exact, number of different families of sulutions modulo $$n$$) is equal to $$2^k$$, where $$k$$ is number of distinct odd prime divisors of $$n$$.

• @DanielSchepler Yes, I forgot about that case. – radekzak Feb 1 at 21:44
• So, the only way to know the number of integer solutions is to factorize n first? Is that correct? – rohitanshu Feb 2 at 4:43
• Also, 32767 has 4 prime factors, 7, 31 and 151, so it should have $2^3 = 8$ solutions, but wolframalpha is showing only 5 to me? Is it not calculating all of them? – rohitanshu Feb 2 at 4:51
• @rohitanshu Yes, you need to factorize n. For 32767, I guess that WolframAlpha just doesn't show some solutions. – radekzak Feb 2 at 11:10
• Then that answers my original question about number of solutions. I'm accepting your answer. Thank you so much. :) – rohitanshu Feb 2 at 11:24