[net.math] Pell's Equation

williams@psuvax.UUCP (Lance Williams) (04/23/84)

  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

kp@smu.UUCP (04/27/84)

#R:psuvax:-102500:smu:14100003:000:339
smu!kp    Apr 27 15:01:00 1984

  
    It is rather surprising that your algorithm did not take care of
special case: if "d" is a perfect square then there are no solutions
in positive integers for the Pell's equation!
                        - KP -
                             Dept of Computer Science
                       (Southern Methodist University, Dallas, TX)