278 5 Number Theory
the numberR=ln(x 1 +y 1
√
D), called the regulator, with a certain accuracy. At the time
of the writing this book no algorithm has been found to solve the problem in polynomial
time on a classical computer. If a computer governed by the laws of quantum physics
could be built, then such an algorithm exists and was discovered by S. Hallgren.
We found the following application of Pell’s equation published by M.N. Deshpande
in theAmerican Mathematical Monthly.
Example.Find infinitely many triples(a,b,c)of positive integers such thata, b, care
in arithmetic progression and such thatab+ 1 ,bc+1, andca+1 are perfect squares.
Solution.A slick solution is based on Pell’s equation
x^2 − 3 y^2 = 1.Pell’s equation, of course, has infinitely many solutions. If(r, s)is a solution, then the
triple(a,b,c)=( 2 s−r, 2 s, 2 s+r)is in arithmetic progression and satisfies( 2 s−
r) 2 s+ 1 =(r−s)^2 ,( 2 s−r)( 2 s+r)+ 1 =s^2 , and 2s( 2 s+r)+ 1 =(r+s)^2.
More examples follow.805.Find a solution to the Diophantine equation
x^2 −(m^2 + 1 )y^2 = 1 ,wheremis a positive integer.806.Prove that there exist infinitely many squares of the form
1 + 2 x
2
+ 2 y
2
,wherexandyare positive integers.807.Prove that there exist infinitely many integersnsuch thatn, n+ 1 ,n+2 are each
the sum of two perfect squares. (Example: 0= 02 + 02 ,1= 02 + 12 ,2= 12 + 12 .)
808.Prove that for no integerncann^2 −2 be a power of 7 with exponent greater than 1.
809.Find the positive solutions to the Diophantine equation
(x+ 1 )^3 −x^3 =y^2.810.Find the positive integer solutions to the equation
(x−y)^5 =x^3 −y^3.