0
$\begingroup$

Let $f(x,y)= ax^2+bxy+cy^2$, or similarly denote it by $(a,b,c)$. This question is about the case $(1,0,p)$ where $p$ is prime. Suppose I have one solution $\bar{x}_1=(x_0,y_0)$ for $f(x,y)=m$ for some odd integer $m$ with at least two prime factors.

Is there an algorithm to find a second solution $\bar{x}_1 \not=(\pm x_0,\pm y_0)$ that is better than $\mathcal{O}(m^2)$ ? Preferably, something much better than that... even something better than $\mathcal{O}(x_0y_0)$ if possible. Of course, brute force works...but is there something better? Specially when $p,m$ start to get bigger trial and error trough $(x,y) \in \mathbb{N}^2$ is not practical.

Edit 1: The solutions are over the integers. The algorithm need not be deterministic, just good in practice with better big-O notation work to find a solution than described above.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Draw a line between $(x_0,y_0)$ and an arbitrary second point, and compute the intersection between this line and the ellipse $x^2+py^2=m$? You should be able to parameterize all solutions using this approach, I think. $\endgroup$
    – Mastrem
    Oct 17 at 20:52
  • $\begingroup$ are you looking for integer or rational solutions? Must the algorithm be determinstic? $\endgroup$
    – Noam D. Elkies
    Oct 17 at 21:09
  • $\begingroup$ @NoamD.Elkies Integer solutions. The algorithm need to be deterministic, but better than $\mathcal{O}(m^2)$ or even $\mathcal{O}(x_0y_0)$ would be very nice. $\endgroup$
    – ReverseFlowControl
    Oct 17 at 22:44
  • $\begingroup$ In certain cases there is no a second solution. Let's take $x^2+3y^2=63$. The only solution is $(x,y)=(\pm6,\pm3)$. So possibly the algorithm, if it exists, is supposed to find a second solution OR to find that there are no other solutions. $\endgroup$
    – G. Melfi
    Oct 18 at 12:35
  • $\begingroup$ @NoamD.Elkies Sorry, it need NOT be deterministic. G.Melfi the number of "unique" solutions is roughly proportional to the number of factors of $m$, something like that, that is why the condition that $m$ have at least two prime factors. Of course, two odd prime factors....we don't care for $2$ as a factor. $\endgroup$
    – ReverseFlowControl
    Oct 18 at 13:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.