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-2616gmf@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