recently I had to solve some diophantine equations in the form $x^2 + n y^2 = b $ in the variables $x$ and $y$, for various fixed values of $n$, and $b$.

Other than "bruteforcing" it, are there some ways to know if, given $n$ and $b$, this equation has at least a solution?

Edit: $n$ and $b$ are both positive integers

  • $\begingroup$ Brute forcing is quick enough conditional if you use continuous fractions. $\endgroup$ – Stan Tendijck Sep 8 '19 at 14:36
  • $\begingroup$ Are $n$ and $b$ necessarily integers as well? $\endgroup$ – XYZT Sep 8 '19 at 14:36
  • $\begingroup$ @StanTendijck Thank you for your comment! Can you give me some more details/reference? $\endgroup$ – dade Sep 8 '19 at 14:39
  • $\begingroup$ @XYZT Yes, they must be positive integers... I will edit my question $\endgroup$ – dade Sep 8 '19 at 14:39
  • $\begingroup$ I would write it out for you but I'm actually on holiday :p Michel Waldschmidt "Diophantine approximations and continued fractions" $\endgroup$ – Stan Tendijck Sep 8 '19 at 14:41

Because of the Brahmagupta–Fibonacci identity, it is enough to answer the question for $b$ prime. But then the answer depends on the arithmetic of quadratic fields. The answer is not simple but it is fascinating. See the book Primes of the Form $x^2+ny^2$, by David Cox.

A good introduction is the case $n=1$, which is solved by Fermat's theorem on sums of two squares .

  • 3
    $\begingroup$ Of course, the role of the Brahmagupta-Fibonacci identity should not be misunderstood as saying that $b$ is represented by $x^2+ny^2$ iff its prime divisors are. $\endgroup$ – Bart Michels Sep 9 '19 at 9:39
  • $\begingroup$ Yes, thank you for the Brahmagupta identity, it will be surely useful in the future... Unfortunately it does not solve my question as @punctureddusk pointed out. $\endgroup$ – dade Sep 9 '19 at 10:02
  • $\begingroup$ @punctureddusk, good point! $\endgroup$ – lhf Sep 9 '19 at 10:10
  • $\begingroup$ @lhf I think this answer would benefit from correcting (or just qualifying) the claim in the first line that the problem reduces to the case of prime $b$. $\endgroup$ – Erick Wong Sep 20 '19 at 4:45

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.