(12C) Pell's Equation
07-07-2018, 05:16 AM (This post was last modified: 07-07-2018 05:21 AM by Gamo.)
Post: #1
 Gamo Senior Member Posts: 507 Joined: Dec 2016
(12C) Pell's Equation
Pell's equation (also called the Pell–Fermat equation) is the equation of the form of

X^2 - nY^2 = 1

Where n is a given positive none square integer and integer solutions are sought for X and Y.

https://en.wikipedia.org/wiki/Pell%27s_equation

I personally make a note on this subject found on this MoHPC old forum and don't remember who posted this in the forum.
I found this very interesting and would like to share his clever program to solve this special equation.

Example: X^2 - (3)Y^2 = 1

3 R/S --> 2 X<>Y 1

Remark: The list of the possible n is shown in the Wikipedia link.

Program: Pell's Equation
Code:
 f 0 STO 0 SQRT STO 1 INTG STO 2 LSTx FRAC STO 3 1/x INTG STO 4 1 STO 5 STO 7 RCL 2 STO 6 RCL4 RCL 2 x RCL 5 + STO 2 RCL 1 / RND STO 7 RCL 3 1/x FRAC STO 3 1/x INTG STO 4 RCL 6 STO 5 RCL 2 ENTER x RCL 7 ENTER x RCL 0 x - 1 - X=0 GTO 51 GTO 16 RCL 7 RCL 2 GTO 00

Gamo
07-07-2018, 09:29 AM
Post: #2
 Thomas Klemm Senior Member Posts: 1,448 Joined: Dec 2013
RE: (12C) Pell's Equation
(07-07-2018 05:16 AM)Gamo Wrote:  I personally make a note on this subject found on this MoHPC old forum and don't remember who posted this in the forum.

Cf. Re: x^2 - N*y^2 = 1 (12C) and 12-digit cut-off

Other threads related to that topic are:
07-07-2018, 11:24 AM (This post was last modified: 07-07-2018 11:35 AM by Dieter.)
Post: #3
 Dieter Senior Member Posts: 2,398 Joined: Dec 2013
RE: (12C) Pell's Equation
(07-07-2018 05:16 AM)Gamo Wrote:  I personally make a note on this subject found on this MoHPC old forum and don't remember who posted this in the forum.
I found this very interesting and would like to share his clever program to solve this special equation.

The program you posted was written by Gerson W. Barbosa, it can be found in the old forum as linked in Thomas' post.

The limitations of a 10-digit calculator have already been mentioned. This means that results with 6 digits or more may and will produce roundoff errors when x² or y² is calculated. And checking whether Pell's equation evaluates to 1 or not will fail. Which doesn't mean there is no way – consider the posts by Egan Ford in the mentioned old forum thread.

Having said that, here's my attempt. A bit shorter and with less registers. ;-)

Code:
01  STO 0 02  √x 03  STO 3 04  CLX 05  STO 2 06  1 07  STO 5 08  RCL 5 09  RCL 3 10  INTG 11  RCL 2 12  STO 5 13  × 14  + 15  STO 2 16  RCL 0 17  √x 18  × 19  FIX 0 20  RND 21  STO 1 22  ENTER 23  × 24  RCL 2 25  ENTER 26  × 27  RCL 0 28  × 29  - 30  1 31  - 32  x=0? 33  GTO 39 34  RCL 3 35  FRAC 36  1/x 37  STO 3 38  GTO 08 39  RCL 2 40  RCL 1 41  GTO 00

This returns the first solution of the equation (at least if the trivial solution x=1 and y=0 is ingored).

Example: n=92

Code:
f PRGM 92 [R/S]    =>   1151    [X<>Y]   =>   120

But there are infinitely many more solutions. These can be obtained with the recurrence formula as shown in the Wikipedia article.

Replace the last three steps in the program above with this:

Code:
... 39  RCL 2 40  STO 4 41  RCL 1 42  STO 3 43  R/S 44  RCL 4 45  RCL 1 46  RCL 4 47  × 48  RCL 2 49  RCL 3 50  × 51  + 52  STO 4 53  X<>Y 54  RCL 2 55  × 56  RCL 0 57  × 58  RCL 1 59  RCL 3 60  × 61  + 62  GTO 42

Example: n=7

Code:
f PRGM 7 [R/S]     =>   8   [X<>Y]    =>   3   [R/S]     =>   127   [X<>Y]    =>   48   [R/S]     =>   2024   [X<>Y]    =>   765

Please note that there is no solution if n is the square of an integer. In this case the program will throw an error: 25 [R/S] => Error 0.

Dieter
07-08-2018, 10:51 AM
Post: #4
 Gamo Senior Member Posts: 507 Joined: Dec 2016
RE: (12C) Pell's Equation
Ah...that from Gerson W. Barbosa

So my post is credit to Gerson who make this clever program....Thanks Gerson

Gamo
07-11-2018, 02:49 PM
Post: #5
 SlideRule Senior Member Posts: 830 Joined: Dec 2013
RE: (12C) Pell's Equation
For those with an interest
[attachment=6114]