An example of a problem involving the resolution of Pell’s 2nd order diophantine equation
Joseph is planning to tile his square court yard with square tiles. He has requested an offer from his two friends Frank and Peter. Frank proposes to use tiles with an area 17 times bigger than Peter. Knowing that Peter’s tiles cover exactly the whole floor of the court and that Frank’s on the other hand fall short for the area a one of Peter’s tiles, how many tiles are the minimum that Peter and Frank, each have proposed in their respective offers?
Let x² and y² be the number of tiles used by Peter and Frank respectively (we know they must be perfect squares).
Let A be the area of Peter’s tiles and 17A the area of Frank’s, then:
- The total area of Peter’s tiles is Ax².
- The total area of Frank’s tiles is on the other hand 17Ay².
Since the difference in Frank’s and Peter’s total tiles’ areas is the area of one of Peter’s tiles, we have:
Ax² – 17Ay² = A
, which when dividing each side of the equation by A, yields:
x² – 17y² = 1 (1)
The problem then consists is finding the positive integer roots of equation (1).
This is a particular case of Pell’s equation: x² – Dy² = 1 where D is a positive integer. It is a particular type of 2nd order diophantine equation. In particular it has infinite solutions over the integers for any value of D. The proof of this amazing fact can be found here
With modern computing, an equation like this is easily solved by brute force, just by trying all possible integers starting from 1. None the less if D was some big number it would still be of interest to implement some better algorithm. So I am going to solve the problem by hand to illustrate the procedure.
First we rearrange equation (1):
where we notice that on the left side of the equation as y increases even slightly 1 /y² << 17, meaning x² / y² is roughly 17 or x / y is roughly the square root of 17. This insight suggests that we could try and find rational approximations to the irrational quantity and search for the solution among the numerator and denumerators of such fractions.
To find rational approximations we use the continued fractions technique. It has been proven that the solution is always within the set of continued fractions, or convergents of the in the general Pell’s equation (also in the previous link)
To calculate the continuous fractions of we proceed:
- 17 = (4 + z)² = 16 + 8z +z²
- 1 = 8z + z² = z (8 + z)
- z=1 / (8 + z)
This last expression can be used recursively to calculate the value of z, replacing z once and again by . These are the continued fractions, so:
as we continue expanding the terms we get closer and closer to , each of the approximations is called a convergent. So the first convergent would be 4, the second , …
Lets try these convergents as a solution of (1)
- first convergent: so x = 4, y = 1 which gives x² – 17y² = -1
- second convergent: so x = 33, y = 8 and x² – 17y² = 1
Eureka!! we have found the solution and we only had to try to numbers. Petter will use 33² = 1069 tiles and Frank 8² = 64.
I hope it was interesting for you, it surely was for me. It is almost magic how the integer solutions of the equation form a rational approximation of an irrational number… who would have thought.