# Find all solutions to the Diophantine equation $x^2-7y^2=-3$

I want to find all integer solutions of the equation $$x^2-7y^2=-3$$ I don't really know where to start... I tried the one trick I know which is to factor in some quadratic ring: $$(x+\sqrt{-3})(x-\sqrt{-3})=7y^2$$ But I don't think that this tells us much since $\mathbb{Z}[\sqrt{-3}]$ is not a UFD. Any help would be appreciated.

I will add that I'll have to solve this type of problem on an exam, hence I want a solution that it quick and suited for use on exams.

• Possible duplicate of How to solve inhomogeneous quadratic forms in integers? – Dietrich Burde May 24 '16 at 18:57
• @DietrichBurde thank you, I think that does indeed solve this problem. – user2520938 May 24 '16 at 18:59
• There is an online "Pell's equation solver", which gives you the recursion how to obtain all integer solutions. See also here. – Dietrich Burde May 24 '16 at 19:00
• Yes, it solves your problem, giving you a very easy recursion for all solutions. See also this question. Pell's equation is the standard here, also for your exam. – Dietrich Burde May 24 '16 at 19:13
• @almagest there is a trick in the style of an infinite descent: for each solution $(x,y),$ both positive, we may find an earlier solution by inverting the action Dietrich gives. That is, we back up with $$(x,y) \mapsto (8x - 21 y, -3x + 8y).$$ A "seed" solution is when either $8x - 21 y \leq 0$ or $-3x + 8y \leq 0.$ These conditions give one representative for each orbit of solutions under Dietrich's action. – Will Jagy May 24 '16 at 19:30

As Dietrich is saying:

there is a trick in the style of an infinite descent: for each "non-seed" solution $(x,y),$ both positive, we may find an earlier positive solution by inverting the action Dietrich gives. That is, we back up with $$(x,y) \mapsto (8x - 21 y, -3x + 8y).$$ A "seed" solution is when either $8x - 21 y \leq 0$ or $-3x + 8y \leq 0.$

I should add that, as $|-3|$ is prime, we get at most two "seed" solutions. I wrote this program to emphasize positive $x,y,$ however, note $(5,2) \mapsto (-2, 1).$ There is a 2016 article by Brillhart that gives detail on why more than two such seed points would cause the target number to be composite. So, being able to guess the solutions $(\pm 2,1),$ we know we have found all the orbits of solutions.

jagy@phobeusjunior:~$./Pell_Target_Fundamental 8^2 - 7 3^2 = 1 x^2 - 7 y^2 = -3 Tue May 24 12:20:40 PDT 2016 Pell automorph 8 21 3 8 x: 2 y: 1 ratio: 2 SEED x: 5 y: 2 ratio: 2.5 SEED x: 37 y: 14 ratio: 2.642857142857143 x: 82 y: 31 ratio: 2.645161290322581 x: 590 y: 223 ratio: 2.645739910313901 x: 1307 y: 494 ratio: 2.645748987854251 x: 9403 y: 3554 ratio: 2.645751266178953 x: 20830 y: 7873 ratio: 2.645751301917947 x: 149858 y: 56641 ratio: 2.645751310887873 x: 331973 y: 125474 ratio: 2.64575131102858 x: 2388325 y: 902702 ratio: 2.645751311063895 x: 5290738 y: 1999711 ratio: 2.645751311064449 Tue May 24 12:21:00 PDT 2016 x^2 - 7 y^2 = -3 jagy@phobeusjunior:~$


In addition, since the trace of the "Automorph" matrix is $16,$ but there are two seeds so we alternate,

$$x_{n+4} = 16 x_{n+2} - x_n,$$ $$y_{n+4} = 16 y_{n+2} - y_n.$$

• Thank you for your answer. I'm a bit disappointed that I'll have to do this on an exam, but it is what it is I guess. – user2520938 May 24 '16 at 19:37
• @user2520938 note that with $|-3|$ prime, we get at most two seed values. Furthermore we can use Dietrich's pairs $(\pm 2,1)$ as the descent gives $(5,2) \mapsto (-2,1).$ I wrote the program this way for a certain type of convenience. Put it together, you can use the obvious solution and be done. – Will Jagy May 24 '16 at 19:42