Existence of Solution to Pell’s Equation

The equation ${X^2-dY^2=1}$ is called the Pell’s equation. There are trivial integer solutions ${(X, Y)= (\pm 1, 0)}$ for every ${d}$ . For ${d\le 0}$ and ${d>0}$ , a square, these are the only solutions. But for any non-square ${d}$ , there are infinitely many solutions and all the solution are generated by a fundamental solution. That is there exists a least solution ${(X_0, Y_0)}$ , with ${X_0, Y_0>0}$ such that every solution ${(X,Y)}$ satisfies

$\displaystyle (X+Y\sqrt d) =\pm (X_0+Y_0 \sqrt d)^n, n \in \mathbb Z.$

The solutions can seen as units in ${\mathbb Z[\sqrt d]}$ and the Pell’s equation is the norm equation ${N(z)=1}$ . That is we basically write ${X^2-dY^2}$ as ${(X+Y\sqrt d)(X-Y\sqrt d)}$ as a product of conjugate elements in ${\mathbb Z[\sqrt d]}$ . We have mutliplicativity of the norm ${N(z_1)N(z_2)=N(z_1z_2)}$ because

$\displaystyle N(z_1z_2) = z_1\sigma(z_1) z_2 \sigma(z_2) = z_1z_2 \sigma(z_1z_2)= N(z_1z_2).$

This concretely corresponds to the following Bhramagupta identity. If we write ${z_1= X_1+Y_1\sqrt d, z_2= X_2+Y_2\sqrt d}$ , we have

$\displaystyle \left(X_1^2-dY_1^2\right) \left(X_2^2-dY_2^2\right) =\left(X_1Y_1+dY_1Y_2\right)^2-d\left(X_1Y_2+X_2Y_1\right)^2.$

So the solutions to the Pell’s equation form a group where the above identity gives the mutliplication law to create a third solution from two solutions. (This is almost equal to the group of units except that the units also include solutions to the negative Pell’s equation ${N(z)=X^2-dY^2=-1.}$ )

Structure of solutions:

If we know that there exists at least one non-trivial solution, we can easily argue that all the solution should be generated by the minimum “fundamental” solution ${X_0+Y_0\sqrt d}$ .

Consider the map ${z \rightarrow \log |z|}$ on the units which defines an additive subgroup of the real numbers. If the group is non-trivial, either i) there is a least element in which case the least element generates the group and we are done, or ii) the image is dense in the reals. In the dense case, there are infinitely many solutions with ${-\epsilon \le \log|z| \le \epsilon }$ , so then we get many elements ${|X+Y\sqrt d |, |X-Y\sqrt d| <e^{\epsilon}}$ , and hence with ${|X|}$ bounded, which cannot be true because ${X}$ ‘s are integers.

But how do we argue that there exists at least one non-trivial solution?

We show several arguments to prove the existence of a non-trivial solution.

a) Argument with Dirichlet Approximation:

Using Dirichlet approximation we can find approximations to ${\sqrt d}$ satisfying

$\displaystyle |\sqrt d -\frac{p_n}{q_n}| \le \frac{1}{Qq_n}$

for any ${Q}$ with ${q_n \le Q}$ .

Thus we have larger and larger approximations satisfying

$\displaystyle |p_n -q_n\sqrt d| \le \frac{1}{Q} \le \frac{1}{q_n}.$ .

Thus

$\displaystyle |p_n^2-dq_n^2| \le |p_n + \sqrt {d} q_n| |p_n - \sqrt {d} q_n| \le (2\sqrt d q_n+ 1) \frac{1}{q_n} =2\sqrt d + 1.$

We have infinitely elements ${p_n + q_n \sqrt d}$ all of whose norms lie in a bounded set. Thus we can assume that there are infinitely many of them with the same norm

${p_n^2-dq_n^2 =m}$ . Further we can assume that there are infinitely many elements with ${p_n = p_0 \bmod m}$ and ${q_n =q_0 \bmod m}$ lying in the same residue classes modulo ${m}$ .

Now take any two such elements and compute the ratio. The norm is ${1}$ by multiplicativity. So we need to show that the ratio turns out to be integral.

$\displaystyle \frac{z_n}{z_{n'}} =\frac{p_n +q_n \sqrt d}{p_{n'} +q_{n'} \sqrt d} =\frac{(p_n +q_n \sqrt d)(p_{n'} -q_{n'} \sqrt d)}{p_{n'}^2-dq_{n'}^2} .$

$\displaystyle =\frac{(p_n +q_n \sqrt d)(p_{n'} -q_{n'} \sqrt d)}{m} =\frac{p_np_{n'}-dq_nq_{n'} + (q_np_{n'} -p_nq_{n'})\sqrt d }{m}.$

But from the fact that we choose them to be from the same residue classes, we have

$\displaystyle p_np_{n'}-dq_n q_{n'} =p_n^2-d{q_n}^2 =0 \bmod m$ and

$\displaystyle q_np_{n'} -p_nq_{n'} =q_np_n -q_np_n =0 \bmod m.$

Hence the ratio is a norm one element with integral coefficients, and gives us our solution!

b) Argument with Continued fractions:

The continued fraction of ${\sqrt d}$ looks like

$\displaystyle =\left[a_{0} ; \overline{a_{1}, a_{2}, a_{3}, \ldots, a_{2}, a_{1}, 2 a_{0}}\right]$

Here the terms are of size atmost ${2\sqrt d}$

and the partial convergents ${\frac{p_k}{q_k}}$ for ${k}$ dividing the period of the continued fraction satisfy the equation

$\displaystyle p_k^2-dq_k^2= (-1)^k.$

Hence the partial quotients give you the solution to Pell’s equation. (In fact also for the negative Pell’s equation of the period is odd.)

If we denote ${x_{i}=\left[b_{i} ; b_{i+1}, \ldots\right] }$ for where ${ \sqrt d =\left[b_1; b_2, b_3 \cdots \right]}$ , we have

$\displaystyle \sqrt{d}=\frac{x_{k+2} p_{k+1}+p_{k}}{x_{k+2} q_{k+1}+q_{k}}=\frac{x_{2} p_{k+1}+p_{k}}{x_{2} q_{k+1}+q_{k}} = \frac{p_{k+1}+p_{k}\left(\sqrt{d}-a_{0}\right)}{q_{k+1}+q_{k}\left(\sqrt{d}-a_{0}\right)}.$

This equation implies

$\displaystyle p_{k}^{2}-d q_{k}^{2}=p_kq_{k+1} -q_kp_{k+1}.$

But we have for any ${l}$ ,

$\displaystyle p_{l} q_{l-1}-q_{l} p_{l-1}=(-1)^{l}.$

which implies

$\displaystyle p_k^2-dq_k^2 =(-1)^k.$

c) Argument with Minkowski theorem:

Any symmetric convex set of volume greater than ${2^n |\det \Lambda|}$ contains a non-zero lattice point from ${\Lambda \subset \mathbb R^n}$ . Look at the units embedded in ${\mathbb R^2}$ by ${(X+Y\sqrt d, X-Y\sqrt d).}$ Pick a large enough compact region say a ball ${S}$ in the the plane containing a non-trivial lattice point. We show that the translates of ${S}$ by the units exhausts the entire plane. For any ${g=x+y\sqrt d }$ lying ${x^2-dy^2=1}$ , ${gS}$ is also a central symmetric convex set with the same volume as ${S}$ , and hence contains a lattice point. The norm of this lattice point is bounded in term of ${S}$ , that is varying over ${g}$ , we get non-zero lattice point with norms bounded uniformly in terms of ${S}$ . But there can be only be finite many principal ideals with this bounded norm. So ${gS}$ contains an element of the form ${\alpha_i u}$ where ${(\alpha_i)}$ are the finite number of ideals with norms bounded as above. Thus ${g^{-1}}$ is contained in ${\alpha_i^{-1}S u^{-1}}$ . Hence ${x^2-dy^2=1}$ can be represented by a compact set upto the action of the units. Now the argument like above with the embedding ${ u \rightarrow (\log|X+Y\sqrt d |, \log |X-Y\sqrt d|) }$ show that units are generated by a fundamental unit.

The main idea in the argument is that all ${gS}$ contain integral elements with with the norm ${X^2-dY^2}$ uniformly bounded. To achieve this we used the fact ${gS}$ and ${S}$ are convex symmetric set of the same volume and apply Minkowski’s theorem (which is essential to find lattice points). Argument is in some ways similar to the proof by Dirichlet approximation, both (Dirichlet approximation theorem, and Minkowski’s theorem) use pigeonholing to find lattice points.

d) Argument with Lattices and Arithmetic quotients:

Let ${G(\mathbb R)}$ be the set of solutions ${x^2-dy^2=1}$ over reals. And denote the integer solutions by ${G(\mathbb Z)}$ . We are interested in understanding ${G(\mathbb Z)}$ and showing that it is infinite, so we consider the quotient ${G(\mathbb R)/G(\mathbb Z).}$ Even in the last argument, we basically showed that this quotient is compact, but the tool to achieve it was Minkowski’s theorem.

We think of ${G}$ as

$\displaystyle G= \left\{ \left(\begin{array}{cc} x &dy \\ y & x \end{array} \right) \mid x^2-dy^2=1\right \} .$

Now consider the action of ${G}$ on a lattice, say the integer lattice and look at all the lattices of the orbit. The action preserves the values of ${x^2-dy^2}$ on the vectors. All the lattices are contained in a compact region in the space of lattice ${SL_2(\mathbb R)/SL_2(\mathbb Z)}$ because the shortest vector in the lattices is bounded below uniformly. To see it just draw a small disk in the plane that doesn’t intersect any of the hyperbolas ${x^2-dy^2 =n}$ , so that none of the vectors in the lattices, all satisfying ${|x^2-dy^2|\ge 1}$ lie inside that disk. Now because of the compactness if we take an sequence of large ${g_i \in G}$ , the lattices ${g\mathbb Z^2}$ converge to another lattice. Thus we get primitive integer vectors ${v_i}$ such that ${g_iv_i}$ converges to a vector ${v}$ . But because ${\det g =1}$ all of these lattice ${g\mathbb Z^2}$ have determinant ${1}$ and all approximately contain ${v}$ as a primitive vector. After changing ${g}$ a little bit so that all the ${g_i \mathbb Z^2}$ exactly contain ${v}$ , we can think of ${v}$ as a basis vector for all these lattices. But since they all have determinant one, the second basis vectors have to lie on a line parallel to ${v}$ . But since ${g}$ ‘s preserve the quadratic form ${x^2-dy^2}$ , all of these vector should will be contained in the same level set ${x^2-dy^2=c}$ . Thus there can only be finitely many such lattices, we have ${g_i\mathbb Z^2 =g_j \mathbb Z^2}$ for infinitely many pairs ${i \neq j}$ . This produces infinitely many element ${g_{i} g_j^{-1} \in SL_2(\mathbb Z) \cap G = G(\mathbb Z)}$ , and we are done.