1
$\begingroup$

How can I solve Pell's equation? $x^2 - Dy^2 = 1$ In fact I need some sort of a systematic way that I can translate into a C++ code..

Of course by solving I mean : "smallest positive integer set". I tried the continued fraction method, but didn't get it completely. And I am not so sure that I can convert that to a proper code.

  • 0
    This could be from Project Euler, which would be regrettable. If it is problem 66, one can get much bigger numbers than with $D=139.$2012-08-29

1 Answers 1

4

There is a potential problem that happens when the continued fraction gets a bit too long. The trouble is that finite accuracy, as in C++ float or double types, will eventually start to give incorrect continued fractions. The cure, really the only cure, is to switch to the closely related Lagrange method of neighboring indefinite quadratic forms. Everything is integer arithmetic; the only thing that requires care is the correct calculation of of $\lfloor \sqrt {139} \rfloor$ and then $\lfloor \sqrt {556} \rfloor.$ As you can see, the first nontrivial solution of $x^2 - 139 y^2 = 1$ involves quite large numbers, even though 139 is not large. It is easy for those numbers to exceed $2^{31} -1$ and therefore give false answers. Again, all that is required is to add in GMP big_int types and use them. The other point is that i do not bother looking for the 22 here. I switch from the original form $\langle 1,0,-139\rangle$ to the "reduced" form seen as line numbered $0,$ namely $\langle 1,22,-18\rangle.$ The calculation stops at line numbered $18$ when i once again find the triple $\langle 1,22,-18\rangle.$ The calculation of the automorph, the Pell automorph, and the fundamental solution to the Pell equation is just the result of multiplying a certain two by two matrix each time by a matrix involving the number I call "delta." If you prefer, you can just take the absolute values of these "delta" numbers, precede them by an $11$ and treat that as a continued fraction, because that is exactly what is there. The cycles of "reduced" indefinite forms correspond to the "purely periodic" continued fractions.

I have written this up a number of times here on MSE. The most detail I give is at https://mathoverflow.net/questions/22811/upper-bound-of-period-length-of-continued-fraction-representation-of-very-composi

=-=-=-=-=-=-=-=-=-= jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$  jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell Input n for Pell  139  0  form   1 22 -18   delta  -1 1  form   -18 14 5   delta  3 2  form   5 16 -15   delta  -1 3  form   -15 14 6   delta  3 4  form   6 22 -3   delta  -7 5  form   -3 20 13   delta  1 6  form   13 6 -10   delta  -1 7  form   -10 14 9   delta  2 8  form   9 22 -2   delta  -11 9  form   -2 22 9   delta  2 10  form   9 14 -10   delta  -1 11  form   -10 6 13   delta  1 12  form   13 20 -3   delta  -7 13  form   -3 22 6   delta  3 14  form   6 14 -15   delta  -1 15  form   -15 16 5   delta  3 16  form   5 14 -18   delta  -1 17  form   -18 22 1   delta  22 18  form   1 22 -18   disc   556 Automorph, written on right of Gram matrix:   -5196131  -118418922 -6578829  -149930369    Pell automorph  -77563250  -914457231 -6578829  -77563250  Pell unit  -77563250^2 - 139 * -6578829^2 = 1   ========================================= jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$  jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$  =-=-=-=-=-=-=-=-=-=