Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.1 6/24/83; site decwrl.UUCP Path: utzoo!watmath!clyde!burl!ulysses!harpo!decvax!decwrl!rhea!hare!stan From: stan@hare.DEC (Stanley Rabinowitz) Newsgroups: net.math Subject: Pell equation Message-ID: <7326@decwrl.UUCP> Date: Tue, 24-Apr-84 03:54:54 EST Article-I.D.: decwrl.7326 Posted: Tue Apr 24 03:54:54 1984 Date-Received: Thu, 26-Apr-84 01:10:36 EST Organization: DEC Engineering Network Lines: 49 About the Pell equation problem: 2 2 The equation x - 961 y = 1 can't have any positive integral solutions because 961 is a perfect square (31^2). If there were a solution, we would have two squares that differed by 1 and thus would have y=0. 2 2 The other 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