Continued fractions and Diophantine equations · Definition
Pell's equation
Before you start you need to know
Pell's equation arises when studying rational approximations of \(\sqrt{d}\). Its solution relies on continued fractions.
Definition
Pell's equation is the quadratic Diophantine equation in integers \(x\), \(y\) that sets equal to 1 the difference between \(x^2\) and \(d\) times \(y^2\), where \(d\) is a positive integer that is not a perfect square.
If \(d\) is not a square, the equation has infinitely many integer solutions. These are generated from a fundamental solution \((x_1, y_1)\), the one with the smallest positive \(y\), through powers of \(x_1 + y_1\sqrt{d}\).
The continued fraction of \(\sqrt{d}\) is periodic. If the period has length \(s\), the convergents \(p_{s-1}/q_{s-1}\) give the fundamental solution when \(s\) is even, and \(p_{2s-1}/q_{2s-1}\) when \(s\) is odd. For example, for \(d=2\) one obtains \((3,2)\) from the convergent \(3/2\).
A typical mistake is forgetting that \(d\) cannot be a perfect square. If \(d=4\), the equation \(x^2-4y^2=1\) is equivalent to \((x-2y)(x+2y)=1\) and has only trivial solutions.
Think about it
What happens to the equation if \(d=9\)?
It factors as \((x-3y)(x+3y)=1\), which only has trivial solutions.
Exercises 10
- Identify which of these equations is a Pell equation.
- State which of these values of \(d\) is valid for Pell's equation.
- What is the solution with the smallest positive \(y\) of Pell's equation called?
- Identify which property of \(\sqrt{d}\) allows solving Pell's equation with continued fractions.
- Which pair \((x,y)\) is a solution of \(x^2 - 2y^2 = 1\)?
- Find the fundamental solution of \(x^2 - 3y^2 = 1\) with minimal positive \(y\).
- Compute the convergent \(p/q\) of the continued fraction of \(\sqrt{2}\) that gives the solution of \(x^2-2y^2=1\).
- Determine the fundamental solution of \(x^2 - 7y^2 = 1\) knowing that \(8^2 - 7\cdot 3^2 = 1\).
- If \((2,1)\) is the fundamental solution of \(x^2-3y^2=1\), which pair is obtained by computing \((2+\sqrt{3})^2\)?
- Solve \(x^2-5y^2=1\) by finding the fundamental solution from the continued fraction expansion of \(\sqrt{5}\), and check that \((9,4)\) satisfies the equation.
References
- David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 15
- Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 7