Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.08 10/3/83; site psuvax.UUCP
Path: utzoo!watmath!clyde!akgua!psuvax!williams
From: williams@psuvax.UUCP (Lance Williams)
Newsgroups: net.math
Subject: Pell's Equation (Solution)
Message-ID: <1025@psuvax.UUCP>
Date: Mon, 23-Apr-84 16:20:48 EST
Article-I.D.: psuvax.1025
Posted: Mon Apr 23 16:20:48 1984
Date-Received: Tue, 24-Apr-84 08:18:27 EST
Organization: Pennsylvania State Univ.
Lines: 37


  I couldn't find a solution for Pell's equation with d = 961 but for d = 991
the solution is:

  x = 379516400906811930638014896080  and  y = 12055735790331359447442538767

The program I used to solve it generates a sequence from which the solution
can be extracted.  See p. 178 of Shank's "Solved and Unsolved Problems in
Number Theory".  The program follows:

(defun pell (x &aux a1 oc c b op q p oq na nb nc np nq)
  (setq a1 (fix (sqrt x)))
  (setq oc x c 1 b 0 op 0 q 0 p 1 oq 1)
  (do ((n 1 (1+ n)))
      ((and (evenp (1- n)) (= c 1) (not (= n 1))) (list p q))
      (setq na (fix (quotient (+ a1 b) c)))
      (setq nb (difference (times na c) b))
      (setq nc (plus oc (times na (difference b nb))))
      (setq np (plus op (times na p)))
      (setq nq (plus oq (times na q)))
      (setq oc c op p oq q c nc b nb q nq p np)))

Who says lisp isn't useful for number crunching?


Lance Williams

Pennsylvania State University