Pell's Equation
The topic, Pell's Equation is one of the diophantine equation, which is a one branch of the number theory. This article will cover shortly about this Pell's Equation.
Introduction
A Pell's equation is a diophantine equation of the form
\(x^2 - dy^2 = 1, x,y \in \mathbb{Z} \) where \(d\) is a given natural number which is not a square number.
An equation of the form \(x^2 - dy^2 = a \) for a integer \(a\) if usually referred to a Pell-type equation.
An arbitrary quadratic diophantine equation with two unknowns can be reduced to a Pell-type equation. How can such equations can be solved? Recall that the general solution of a linear diophantine equation is a linear function of some parameters. This does not happen with general quadratic diophantine equations. However, as we will see later, in the case of such equations with two unknowns there still is a relatively simple formula describing the general solution.
Why does the definition of Pell's equation assume that \(d\) is not a square? Well, for \(d=c^2, c \in \mathbb{Z}\), the equation \(x^2 - dy^2 = a \) can be factored as \((x-cy)(x+cy) = a\) and therefore solved without using any further theory. So, unless noted otherwise, \(d\) will always be assumed not to be a square.
The equation \(x^2 - dy^2 = a \) can still be factored as
\[(x+y\sqrt{d})(x-y\sqrt{d}) = a\]
In order to be able to make use of this factorization, we must deal with numbers of the form \(x+y\sqrt{d}\), where \(x,y\) are integers. This set is denoted as \(\mathbb{Z}[\sqrt{d}]\). An important property of this set is that the sum and product of two of its elements remain in the set.
The conjugate of a number \(z = x+y\sqrt{d}\) is defined as \(\bar{z} = x- y\sqrt{d}\),
and its norm as \(N(z) = z\bar{z} = x^2 - dy^2 \in \mathbb{Z}\)
The norm and the conjugate are multiplicative in \(z\)
\(N(z_1 z_2) = N(z_1)N(z_2)\) , \(\overline{z_1 z_2} = \overline{z_1} \cdot \overline{z_2}\)
In terms of these concepts, the equation \(x^2 - dy^2 = a \) can be rewritten as
\[N(z) = a, \quad where\; z = x-y\sqrt{d} \in \mathbb{Z}[\sqrt{d}]\]
In particular, the Pell's equation becomes \(N(z) = 1, z \in \mathbb{Z}[\sqrt{d}]\). We continue using these notation.
Since \(z\) is a solution to a Pell-type equation if and only if so is \(-z\), we always assume without loss of generality that \(z > 0\)
Solutions to Pell's Equation
A Pell's equation has one trivial solution, \((x,y) = (1,0)\), corresponding to the solution \(z=1\) of equation \(N(z) = 1\). But if we now the smallest non-trivial solution, then we can derive all the solutions. This is what the following statement claims.
If \(z_0\) is the minimal element of \(\mathbb{Z}[\sqrt{d}]\) with \(z_0 > 1 \) and \(N(z_0) = 1\), then all the elements \(z \in \mathbb{Z}[\sqrt{d}]\) with \(N_z = 1\) are given by \(z = \pm z_0^n, n \in \mathbb{Z}\)
Suppose that \(N(z) = 1\) for some \(z > 0\).
There is a unique integer \(k\) for which \(z_0^k \leq z \leq z_0^{k+1}\).
Then the number \(z_1 = z z_0^{-k} = z {\overline{z_0}}^k\) satisfies \(1 \leq z_1 \leq z_0\) and \(N(z_1) = N(z)N(z_0)^{-k} = N(z) = 1\).
It follows from the minimality of \(z_0\) that \(z_1 = 1\) and hence \(z = z_0^k\).
If \((x_0, y_0)\) is the smallest solution of the Pell's equation with \(d\) given, then all natural solutions \((x,y)\) of the equation are given by \(x+y\sqrt{d} = \pm (x_0 + y_0 \sqrt{d})^n, n \in \mathbb{N}\).
Note that \(z=x+y\sqrt{d}\) determines \(x\) and \(y\) by the formulas \(x = \frac{z+\overline{z}}{2}\) and \(y = \frac{z-\overline{z}}{2\sqrt{d}}\). Thus all the solutions of the Pell's equation are given by the formulas
\[ x = \frac{z_0^n + {\overline{z_0}}^n}{2} \; y = \frac{z_0^n - {\overline{z_0}}^n}{2\sqrt{d}}\]
Now we will show that every Pell's equation indeed has a non-trivial solution.
Let \(\alpha\) to be an irrational number and \(n\) to be a positive integer.
There exist \(p \in \mathbb{Z}\) and \(q \in \set{1,2, \cdots, n}\) such that \(\left|\alpha - \frac{p}{q} \right| < \frac{1}{(n+1)q}\).
The started inequality is equivalent to \(\left|q\alpha - p\right| < \frac{1}{n+1}\).
Let, as usual, \(\set{x}\) denote the fractional part of real \(x\). Among the \(n+2\) numbers \(0, \set{\alpha}, \set{2\alpha}, \cdots \set{n\alpha}\), \(1\) in the segment \([0, 1]\), some two will dffer by less than \(\frac{1}{n+1}\). If such are the numbers \(\set{k\alpha}\) and \(\set{l\alpha}\), it is enough to set \(q = \left|k-l\right|\); and if such are \(\set{k\alpha}\) and 0 or 1, it is enough to set \(q = k \). In either case, \(p\) is the integer closest to \(k\alpha\)
If \(\alpha\) is an arbitrary real number, then there exist infinitely many pairs of positive integers \((p,q)\) satisfying \(|\alpha - \frac{p}{q}| < \frac{1}{q^2}\)
(This lemma 2 immediately follows from Dirichlet's theorem)
A Pell's equation has a solution in the set of positive integers
Applying Lemma 2 to \(\alpha = \sqrt{d}\), we see that there exists an integer \(n\) with \(|n| < 2\sqrt{d} + 1\) such that the equation \(x^2-dy^2=n\) has infinitely many positive integral solutions \((x,y)\). It follows that there are two different ones, say \((x_1,y_1)\) and \((x_2,y_2)\), that satisfy \(x_1 \equiv x_2\) and \(y_1 \equiv y_2\) \(\pmod n\). Denote \(z_1 = x_1 + y_1 \sqrt{d}\) and \(z_2 = x_2 + y_2 \sqrt{d}\) and assume \(z_1 > z_2\). Then \(z_0 = z_1 / z_2 > 1\) is an element of \(\mathbb{Z}[\sqrt{d}]\) of norm 1 and corresponds to a non-trivial solution \((x_0,y_0)\) of the Pell's equation.
Pell-type Equations
A Pell-type equation in general may not have integer solutions (for example, the equation \(x^2 - 3y^2 = 2\)). When it does, it is possible to describe the general solution.
The equation \(x^2-dy^2=-1\) has an integral solution if and only if there exist \(z_1 \in \mathbb{Z}[\sqrt{d}]\) with \(z_1^2 = z_0\)
The 'if' part is trivial. For the other direction we consider the smallest solution \(z = z_1 \in \mathbb{Z}[\sqrt{d}]\) of the equation \(N(z) = -1\) satisfying \(z>1\) and, like in Theorem 2, deduce that \(1 \leq z_1 < z_0\). Since \(z=z_1^2 < z_0^2\) is a solution of \(N(z) = 1\), we must have \(z_1^2 = z_0\).
Consider the general equation \(N(z) = a\). Like in Theorem 1, one can show that its solutions can be obtained from the solutions \(z\) with \(1 \leq z \leq z_0\), where \(z_0\) is the smallest non-trivial solution of Pell's equation \(N(z) = 1\). Thus it is always sufficient to check finitely many values of \(x\). Moreover, there is a simple upper bound for those \(x\).
If \(a\) is an integer such that the equation \(N(z) = x^2 - dy^2 = a\) has an integer solution, then there is a solution with \(|x| \leq \frac{z_0 + 1}{2\sqrt{z_0}} \sqrt{|a|}\) and the corresponding upperbound for \(y = \sqrt{\frac{x^2-a}{d}}\).
If \(z_1\) is a solution of the equation \(N(z) = a\), then there is \(m \in \mathbb{Z}\) for which \(a/\sqrt{z_0} \leq z_0^m z_1 < a\sqrt{z_0}\). Then \(z_2 = z_0^m z_1 = x + y\sqrt{d}\) is a solution of the equation \(N(z) = 1\) and satisfies
\[ 2|x| = \left| z_2 + \frac{a}{z_2} \right| \leq \max\left(\frac{a}{\sqrt{z_0}}, a\sqrt{z_0}\right) \left| t + \frac{a}{t} \right| = \frac{z_0 + 1}{\sqrt{z_0}} \sqrt{|a|}. \]
