Pell equations have infinite solutions

December 22, 2022
Útulek Series, 2 | CF1761D Chapter, 2

Last time, I left off with the following probability problem:

A drawer contains red socks and black socks. When two socks are drawn at random (without replacement), the probably that both are red is $1/2$ . How many socks can the drawer contain?

The first solution is fairly straightforward:

\begin{aligned} &\frac{r}{r+b}\cdot\frac{r-1}{r+b-1}=\frac{1}{2}\\[3ex] \implies&2r^2-2r=r^2+b^2+2rb-r-b\\ \implies&r^2-(2b+1)r-b^2+b=0\\ \implies&r=(2b+1\pm\sqrt{8b^2+1})/2. \end{aligned}\tag{0.1}

It’s easy to see that $b=1$ gives a square determinant and a valid $r=3$ . In fact, since $\sqrt{8b^2+1}$ is necessarily odd and also grows faster than $2b+1$ , the solutions to the original problem form a bijection with the positive integer solutions to $x^2=8b^2+1$ , which is a case of the general Pell equation

x^2-Dy^2=1\tag{0.2}

with $D=8$ . Should $D$ be a square, it is trivial that Pell equations have no solution in the positive integers should $D$ . Otherwise, it is well-known that they exhibit infinite solutions. In this post, I will provide my intuition behind a constructive proof of the latter claim, based loosely on the proof presented in Titu’s An Introduction to Diophantine Equations, before briefly discussing how this relates back to 1761D.

1 Integers are Dense in the Radicals

Equation $(0.2)$ essentially says: “ $x^2$ and $Dy^2$ are very close” (there is a similar variant of the Pell with RHS $\pm1$ ). Knowing that $\sqrt{D}$ is irrational, one might suspect that some $y\sqrt{D}$ might be very very close to an integer $x$ , which would get us close to the claim of the Pell equation. Thus forms our first lemma.

Lemma 1.1: For any integer $E$ , we can find positive integer $x_1,y_1$ satisfying $y_1\leq E$ and

|x_1-y_1\sqrt{D}|<1/E.\tag{1.1}

Proof of Lemma 1.1: I would use $\epsilon$ as the RHS, but it complicates later parts of the proof without first asserting that the rationals are dense in the reals, which I want to avoid here.

This lemma is almost certainly true, should one take an example $D=7$ and enumerate the $\sqrt{D}$ multiples. We thus enumerate the first $E+1$ multiples $0,\sqrt{D},\ldots,E\sqrt{D}$ and their fractional parts $0\leq\{0\},\{\sqrt{D}\},\ldots,\{E\sqrt{D}\}\leq 1$ . By pidgeonhole, then, there must be two multiples $\{i\sqrt{D}\},\{j\sqrt{D}\}$ , $i\leq j$ which fall within $1/E$ of each other. Subtracting their indices, we have $y_1=j-i$ and $x_1$ likewise as the difference between their integer portions. $\blacksquare$

Technically, we will had to have invoked the Archimedean principle, like in the proof of dense real numbers, but I’d like to stay away from group theory for now.

2 $Dy^2$ Can Be Close, But Not Arbitrarily Close to $x^2$

Lemma $(1.1)$ tell us $y_1\sqrt{D}$ can be arbitrarily close to an integer $x_1$ . In fact, an infinite number of pairs $(x_1,y_1)$ may be found with repeated applications of the pidgeonhole principle.

Going from a bound on $x_1-y_1\sqrt{D}$ to a bound on $x_1^2-y_1^2D$ now seems straighforward:

\begin{aligned} &|x_1-y_1\sqrt{D}|<1/E\\ \implies&|x_1+y_1\sqrt{D}|<2y_1\sqrt{D}+1/E\\ \implies&|(x_1-y_1\sqrt{D})(x_1+y_1\sqrt{D})|\\ =\ &|x_1^2-y_1^2D|< 2(y_1/E)\sqrt{D}+1/E^2 \end{aligned}

Recall $y_1\leq E$ :

|x_1^2-y_1^2D|< 2\sqrt{D} + 1.

Thus, should we enumerate the integers $k$ in $(-2\sqrt{D}-1,2\sqrt{D}+1)$ , at least one of them $k_0$ must satisfy $x_1^2-Dy_1^2=k_0$ for infinitely many pairs $(x_i,y_i)$ for $i\geq 1$ .

Lemma 2.1: An infinite number of positive integer pairs $(x_i,y_i)$ satisfy

x_i^2-Dy_i^2=k_0

for some integer $k_0$ .

3 Eyes on the Ball

Lemma $(2.1)$ is remarkably close to the Pell equation $(0.2)$ . Squinting our eyes at $(2.1)$ , one may see

x_i^2-Dy_i^2=k_0^2\tag{3.1}

which will give a solution to the Pell equation should $|k_0|$ divide both $x_i,y_i$ , which seems likely considering we have infinite pairs $(x_i,y_i)$ .

In fact, getting to $(3.1)$ only requires a small amount of algebraic foresight. Take two pairs $(x_i,y_i),(x_j,y_j)$ and multiply them:

\begin{aligned} &(x_i^2-Dy_i^2)(x_j^2-Dy_j^2)=k_0^2\\ \implies&x_i^2x_j^2+D^2y_i^2y_j^2-D(x_i^2y_j^2+x_j^2y_i^2)=k_0^2 \end{aligned}\tag{3.2}

at which point we recognize we want to add something to $x_i^2y_j^2+x_j^2y_i^2$ to make it a square, and to subtract the same thing from $x_i^2x_j^2+D^2y_i^2y_j^2$ to also make it square:

\begin{aligned} D(x_i^2y_j^2+x_j^2y_i^2)&-2Dx_ix_jy_iy_j=D(x_iy_j-x_jy_i)^2\\ x_i^2x_j^2+D^2y_i^2y_j^2&+2Dx_ix_jy_iy_j=(x_ix_j+Dy_iy_j)^2.. \end{aligned}

Thus, let $x=x_ix_j+Dy_iy_j,y=x_iy_j-x_jy_i$ and we have

x^2-Dy^2=k_0^2

as we wished for earlier. As suggested, to ensure $x\equiv y\equiv 0[|k_0|]$ , we may invoke the fact that there are infinite pairs $(x_i,y_i)$ and hence there must be pairs $(x_i,y_i),(x_j,y_j)$ with $x_i\equiv x_j[|k_0|]$ and $y_i\equiv y_j[|k_0|]$ , which will give us the divisibility requirement.

Theorem 3.1: For non-square $D$ , there exist at least one pair of positive integers $x,y$ satisfying

x^2-Dy^2=1.

4 Infinite Solutions via Matrix Exponentiation

With our initial solution $x,y$ (which we will now re-index as $x_1,y_1$ ), we may generate a second solution $x_2,y_2$ with similar algebraic manipulation as in $(3.2)$ :

\begin{aligned} &(x_1^2-Dy_1^2)(x_1^2-Dy_1^2)=1\\ \implies&x_1^4+D^2y_1^4-2Dx_1^2y_1^2=1\\ \implies&(x_1^2+Dy_1^2)^2-D(2x_1y_1)^2=1\\ \implies&x_2^2-Dy_2^2=1 \end{aligned}

with $x_2=x_1^2+Dy_1^2,y_2=2x_1y_1$ . As one may suspect, multiplying the equation by $x_1^2-Dy_1^2=1$ will always give new solutions. For example,

\begin{aligned} &(x_2^2-Dy_2^2)(x_1^2-Dy_1^2)=1\\ \implies&x_2^2x_1^2+D^2y_2^2y_1^2-Dx_2^2y_1^2-Dx_1^2y_2^2=1\\ \implies&(x_2x_1+Dy_2y_1)^2-D(x_1y_2+x_2y_1)^2=1\\ \implies&x_3^2-Dy_3^2=1 \end{aligned}

with

x_i=x_{i-1}x_1+Dy_{i-1}y_1,y_i=x_1y_{i-1}+x_{i-1}y_1.\tag{4.1}

We can, of course, express this more compactly in matrix form:

\begin{bmatrix} x_i\\ y_i \end{bmatrix}=\begin{bmatrix} x_1&Dy_1\\ y_1&x_1 \end{bmatrix}\begin{bmatrix} x_{i-1}\\ y_{i-1} \end{bmatrix}.\tag{4.2}

An interesting corollary which I shall state without proof is that should $x_1,y_1$ be the minimal positive solution, this method generates all solutions. Thus, we must have the following corollary.

Corollary 4.3: All solutions to Pell equation $(0.2)$ may be generated by sequential matrix exponentiation:

\begin{bmatrix} x_i\\ y_i \end{bmatrix}=\begin{bmatrix} x_1&Dy_1\\ y_1&x_1 \end{bmatrix}^{i-1}\begin{bmatrix} x_1\\ y_1 \end{bmatrix}.

5 Tying it Together

Recalling $(0.1)$ for the original probability question, we have $D=8$ and initial solution $(x_1,y_1)=(3,1)$ , and may subsequently generate $(x_2,y_2)=(17,6)$ which is easily verifiable. The proof provided above is reasonably constructive, and may be used to find the initial solution for the general Pell equation $(0.2)$ —however, the better-known method is to use the continued fraction representation of $\sqrt{D}$ . The proof for why that works is tedious and I will not present it presently.

It is also a short derivation to determine that the result in corollary $(4.3)$ may alternatively be expressed as

\begin{aligned} x_i&=\frac{(x_1+y_1\sqrt{D})^i+(x_1-y_1\sqrt{D})^i}{2}\\ y_i&=\frac{(x_1+y_1\sqrt{D})^i-(x_1-y_1\sqrt{D})^i}{2\sqrt{D}}\\ \end{aligned}

with the eigenvalues of matrix $\begin{bmatrix}x_1&Dy_1\\y_1&x_1\end{bmatrix}$ in plain view. I was actually not aware of the general result that matrix exponentiation could always be expressed in terms of exponentiation of the eigenvalues of the matrix, but it certainly puts into context the relationship between Binet’s formula and the Fibonacci matrix solution (follows from equation $(1.3)$ from the previous post):

\begin{bmatrix} S_{i+1}\\ S_i \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^i\begin{bmatrix} 1\\ 0 \end{bmatrix},

S_i=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^i -(\frac{1-\sqrt{5}}{2})^i).

So there is some relationship between one-dimensional recurrences, such as the Fibonacci, and Pell equations—which leads to them both being solved by the general form

S_i=(\text{some radical})(\text{some radical})^i+(\text{some radical})(\text{some radical})^i.

It is then surprising to me that when a recurrence is upgraded from one-dimensional to two-dimensional, such as with 1761D or Pascal’s triangle, we no longer see powers of radicals, but rather summations of $n\choose k$ (solution $(2.5)$ for 1761D from the previous post):

A_{N,K}=\sum_{j=1}^{2K}{3^{N-j}{N-K\choose \lfloor j/2\rfloor}{K-1\choose \lceil j/2\rceil-1}}.

At this point, I believed I didn’t understand well enough the class of functions like corollary $(4.3)$ which exhibit exponential behavior:

f(1)f(i)=f(i+1).\tag{5.1}

In the next post, I investigate multiplicative functions, which I mistakenly thought were functions like $(5.1)$ , but are actually functions of the form

f(i)f(j)=f(ij).\tag{5.2}