Pell’s Equation
The Puzzle
Here is a puzzle that I will use to illustrate the use and solution of Pell’s equation.
I am studying a six digit item number in a very long list of consecutively numbered items.
To my surprise I have found that if I add this item number to a certain number of the immediately lower item numbers, the result is the same as the sum of the same number of immediately higher item numbers.
Also, if I add the square of this item number to the squares of a different number of immediately lower item numbers, the result is the same as the sum of the squares of the same number of immediately higher item numbers.
What is the number that I am studying?
Analysis
Let \(i\) be the item number being considered and \(m\) be the number of immediately lower and higher item numbers being added. So we have: \[(i-m) +\cdots +(i-1) + i = (i + 1) +\cdots + (i+m)\]Simplifying this gives \[i=m(m+1)\]Now repeating this for \(n\) squared values: \[(i-n)^2 +\cdots +(i-1)^2 + i^2 = (i + 1)^2 +\cdots + (i+n)^2\] which simplifies to:\[i=2n(n+1)\]Now eliminating the item number \(i\) we obtain: \[m(m+1)= 2n(n+1)\] which can be recast as: \[(2m+1)^2 – 2(2n+1)^2 = -1\]
Quadratic Diophantine Equations
To solve this we now need a diversion to study solutions for equations of the form: \[x^2-Dy^2=N\] for \(D\) a non-square positive integer, \(N\) an integer and both \(x\) and \(y\) integer. This is known as a quadratic diophantine equation but is also known as Pell’s equation when \(N=1\) (it was mistakenly attributed it to Pell by Euler). Before considering a full solution, it is useful to set out how we can develop a whole sequence of solutions once we have a single solution. If we have a solution \((x_k, y_k)\) such that \[x_k^2 – Dy_k^2=N\]and \((r, s)\) values such that:\[r^2-Ds^2=1\]then the identity:\[(x_k^2 – Dy_k^2)(r^2-Ds^2) = (rx_k\pm Dsy_k) ^2- D(sx_k\pm ry_k)^2\]shows that\[(x_{k+1},y_{k+1}) = (rx_k\pm Dsy_k, sx_k\pm ry_k)\]is also a solution.
For our puzzle with \(D=2\) an initial solution for \((x,y)\) is \((1)^2 – 2(1)^2=-1\) and one for \((r,s)\) is \((3)^2 – 2(2)^2=1\). So we can now develop a sequence of solutions as:\[(x_{k+1}, y_{k+1}) = (3x_k+4y_k,2x_k+3y_k)\]These solutions are provided by this Python program
|
1 2 3 4 5 6 7 8 9 |
print(' x y m n i = m(m + 1)') fs = '{:9d} {:9d} {:9d} {:9d} {:18d}' x, y = 1, 1 for i in range(12): m, n = (x - 1) //2, (y - 1) // 2 print(fs.format(x, y, m, n, m * (m + 1))) x, y = 3 * x + 4 * y, 2 * x + 3 * y |
giving:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
x y m n i = m(m + 1) 1 1 0 0 0 7 5 3 2 12 41 29 20 14 420 239 169 119 84 14280 1393 985 696 492 485112 8119 5741 4059 2870 16479540 47321 33461 23660 16730 559819260 275807 195025 137903 97512 19017375312 1607521 1136689 803760 568344 646030941360 9369319 6625109 4684659 3312554 21946034630940 54608393 38613965 27304196 19306982 745519146510612 318281039 225058681 159140519 112529340 25325704946729880 |
where the highlighted line gives the answer as 485,112.