5
$\begingroup$

$$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.

$\endgroup$
16
  • 1
    $\begingroup$ Don't you mean $\equiv$ instead of $=$? $\endgroup$ – Some Guy Feb 1 at 20:42
  • 1
    $\begingroup$ 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$. $\endgroup$ – jlammy Feb 1 at 21:00
  • 1
    $\begingroup$ 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$ $\endgroup$ – poetasis Feb 1 at 22:22
  • 1
    $\begingroup$ 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 $\endgroup$ – Some Guy Feb 2 at 4:48
  • 1
    $\begingroup$ @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. $\endgroup$ – poetasis Feb 2 at 5:16
3
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ @DanielSchepler Yes, I forgot about that case. $\endgroup$ – radekzak Feb 1 at 21:44
  • $\begingroup$ So, the only way to know the number of integer solutions is to factorize n first? Is that correct? $\endgroup$ – rohitanshu Feb 2 at 4:43
  • $\begingroup$ 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? $\endgroup$ – rohitanshu Feb 2 at 4:51
  • 1
    $\begingroup$ @rohitanshu Yes, you need to factorize n. For 32767, I guess that WolframAlpha just doesn't show some solutions. $\endgroup$ – radekzak Feb 2 at 11:10
  • $\begingroup$ Then that answers my original question about number of solutions. I'm accepting your answer. Thank you so much. :) $\endgroup$ – rohitanshu Feb 2 at 11:24

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.