2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of How to solve inhomogeneous quadratic forms in integers? $\endgroup$ – Dietrich Burde May 24 '16 at 18:57
  • $\begingroup$ @DietrichBurde thank you, I think that does indeed solve this problem. $\endgroup$ – user2520938 May 24 '16 at 18:59
  • $\begingroup$ There is an online "Pell's equation solver", which gives you the recursion how to obtain all integer solutions. See also here. $\endgroup$ – Dietrich Burde May 24 '16 at 19:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Dietrich Burde May 24 '16 at 19:13
  • 1
    $\begingroup$ @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. $\endgroup$ – Will Jagy May 24 '16 at 19:30
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user2520938 May 24 '16 at 19:37
  • $\begingroup$ @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. $\endgroup$ – Will Jagy May 24 '16 at 19:42

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.