stan@hare.DEC (Stanley Rabinowitz) (04/24/84)
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
gmf@uvacs.UUCP (04/28/84)
As to the least positive solution for Pell equation for 991 (viz.,x = 30 digit number, y = 29 digit number): Suppose someone formulates the theorem x^2 - 991*y^ = 1 has no positive solution. If he/she tries to verify this by selecting y=1,2,... and showing there is no corresponding x, success would occur for something more than 10^28 trials. This is a good example for showing that non-mathematical induction is a perilous technique. Gordon Fisher