| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Newsgroups: net.math
Path: decwrl!decvax!mcnc!unc!ulysses!mhuxl!ihnp4!inuxc!pur-ee!uiucdcs!parsec!smu!kp
Subject: Pell's (Fermat's ?) equations - (nf)
Posted: Fri Apr 20 13:39:00 1984
Nf-ID: #N:smu:14100002:000:321
Nf-From: smu!kp Apr 20 15:39:00 1984
#N:smu:14100002:000:321
smu!kp Apr 20 15:39:00 1984
Consider equations of following type:
x^2 - d*y^2 = 1 where x, y, d are all positive integers.
Can you give me the least positive integral solutions in x and y,
if they exist, for the following equations:
(1) X^2 - 961*Y^2 = 1
(2) X^2 - 991*Y^2 = 1
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 57.1 | ORPHAN::BRETT | Mon Apr 23 1984 22:50 | 7 | ||
My "Recreations in the Theory of Numbers" gives Degen's CANON PELLIANUS 1817 as listing all soln's up to 1000. Unfortunately the table listed in it only goes to D=102 /Bevin | |||||
| 57.2 | HARE::STAN | Tue Apr 24 1984 07:14 | 12 | ||
Newsgroups: net.math
Path: decwrl!decvax!harpo!ulysses!unc!mcnc!ncsu!uvacs!gmf
Subject: Pell's (Fermat's) equations (addition)
Posted: Sun Apr 22 20:45:18 1984
I know the solution to x^2 - 961*y^2 = 1 . It is given on p. 88 of
Sierpinski's *Elementary Theory of Numbers* . I also know the
solution to x^2 - 991*y^2 = 1. It is given on p. 93. Sierpinski
remarks that the solution to one of these illustrates a peril of
induction. Additional question: What peril?
Gordon Fisher
| |||||
| 57.3 | HARE::STAN | Tue Apr 24 1984 07:16 | 6 | ||
What are you people talking about? 961 is a perfect square (31^2), so if 2 2 x - 961 y = 1 then we would have two squares differing by 1. This can't be unless y=0. | |||||
| 57.4 | HARE::STAN | Tue Apr 24 1984 07:55 | 40 | ||
2 2
The equation, x - 991 y = 1 , has solutions because 991 is
not a perfect square. A solution can be found using continued fractions.
Expressing sqrt(991) as a continued fraction, we find (with computer help)
sqrt(991) = [31, 2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8,
4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4,
1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2,
2, 2, 10, 12, 2, 62]
(except for the 31, this repeats thereafter). See Olds [1] for info
on continued fractions.
Anyhow, computing the final convergent in the period, we find that it is
equal to
p 379516400906811930638014896080
- = ------------------------------ (in lowest terms).
q 12055735790331359447442538767
Thus p and q are the desired solutions to the Pell equation. That is
379516400906811930638014896080^2 - 991*12055735790331359447442538767^2 = 1 .
I think the theory of continued fractions says that this is the smallest
solution, but I am not 100% sure of that. All the other solutions can be
generated from the minimal solution via standard theory of Pell equations.
Reference
---------
[1] C. D. Olds, Continued Fractions, The Mathematical Association of
America (New Math Library). 1963.
Stanley Rabinowitz
UUCP: ...{decvax,ucbvax,allegra}!decwrl!rhea!hare!stan
ARPA: stan%hare.DEC@DECWRL.ARPA
ENET: {hare,turtle,algol,kobal}::stan
USPS: 6 Country Club Lane, Merrimack, NH 03054
(603) 424-2616
| |||||
| 57.5 | HARE::STAN | Wed Apr 25 1984 02:10 | 38 | ||
From: ROLL::USENET "USENET Newsgroup Distributor" 24-APR-1984 22:05
To: HARE::STAN
Subj: USENET net.math newsgroup articles
Newsgroups: net.math
Path: decwrl!decvax!mcnc!akgua!psuvax!williams
Subject: Pell's Equation (Solution)
Posted: Mon Apr 23 13:20:48 1984
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
| |||||