A quick how-to, by special request of @nathanday314.

Pell’s equation is anything of the form $x^2 - ny^2 = 1$, as long as $n$ is an integer but not a square number. There is also a general Pell’s equation, which looks like $x^2 - ny^2 = N$, where $n$ is still not square and $N$ is a non-zero integer.

The Sock Puzzle, Revisited

Remember The Sock Puzzle? Of course you do. We had three equations:

  • $2r(r-1) = n(n-1)$
  • $12b(b-1) = n(n-1)$
  • $24rb = 5n(n-1)$

Completing the square on the first pair gives:

  • $2\br{\br{r - \frac{1}{2}}^2 - \frac{1}{4}} = n(n-1)$
  • $12\br{br{b - \frac{1}{2}}^2 - \frac{1}{4}} = n(n-1)$

The right hand sides are equal, so the left-hand sides must be, too:

  • $2\br{\br{r - \frac{1}{2}}^2 - \frac{1}{4}} = 12\br{\br{b - \frac{1}{2}}^2 - \frac{1}{4}}$

Let’s multiply everything by 4:

  • $2\br{\br{2r-1}^2 - 1} = 12\br{\br{2b-1}^2 - 1}$

or:

  • $2\br{2r-1}^2 - 2 = 12\br{2b-1}^2 - 12$

Or even:

  • $\br{2r-1}^2 - 6\br{2b-1}^2 = -5$

… which is a general Pell’s equation with $x = 2r-1$ and $y = 2b-1$. (Obviously, we will need to make sure our answers are odd!)

An aside into continued fractions

For reasons I don’t fully understand, you can generate a solution to (the non-general) Pell’s equation using the continued fraction of $\sqrt{n}$.

In particular, if you work out the convergents $\frac{p_i}{q_i}$ of $\sqrt{n}$ – the fractions in the continued fraction that are the closest approximations with that denominator or smaller – you will eventually find that $x=p_k$ and $y=q_k$ is a solution to the equation for some $k$. This is the fundamental solution.

Let’s try it with $n = 6$. The convergents – which I’ll circle back to presently – are $\frac{2}{1}, \frac{5}{2}, \frac{22}{9}, \frac{49}{20}\dots$.

The first one doesn’t work ($4-6$ is not 1), but the second does: $25 - 24$ is indeed 1. So $x=5$, $y=2$ is the fundamental solution to $x^2 - 6y^2 = 1$. Let’s call this solution $(x_0,y_0)$.

This is not the only solution: others can be found using the recurrence relation:

  • $x_{k+1} = x_0 x_{k} + n y_0 y_k$
  • $y_{k+1} = x_0 y_{k} + y_0 x_k$

So a second solution to our equation $x^2 - 6x = 1$ would be $x_1 = (5)(5) + 6(2)(2) = 49$ any $y_1 = (5)(2) + (2)(5) = 20$ – in fact, another of the convergents!

But where do these convergents come from?

I thought you’d never ask.

The square root of 6 is “two and a bit”, which we can write down as $\sqrt{6} = 2 + x$.

Alternatively, $6 = 4 + 4x + x^2$, or $2 = x(4+x)$.

Or even alternativelier, $x = \frac{2}{4+x}$ or $\frac{1}{2 + x/2}$. (I’ll use both of these presently).

This means that $\sqrt{6} = 2 + \frac{1}{2+x/2}$, for whatever this value of $x$ is. But we know what this value of $x$ is – and in particular that $x/2 = \frac{1}{4+x}$.

So $\sqrt{6} = 2 + \frac{1}{2 + \frac{1}{4+x}}$, for whatever this value of $x$ is.

But again, we know what this value of $x$ is! It’s $\frac{1}{2+x/2}$!

So $\sqrt{6} = 2 + \frac{1}{2+\frac{1}{4+\frac{1}{2+x/2}}}$. The pattern repeats forever, as I’m sure you can prove if you’re interested.

Unsurprisingly, the first continued fractionologists looked at that and thought something that ended with “game of soldiers” and came up with the alternative notation $[2; 2,4,2,4,\dots]$, or better, $[2; \overline{2,4}]$.

So where do the convergents come from? They’re the approximations you get from letting $x=0$ at any given stage in the expansion.

The original estimate was $\sqrt{6} = 2 + x$, which gives the first convergent of 2.

The next guess was $\sqrt{6} = 2 + \frac{1}{2+x}$, which gives $\frac{5}{2}$.

Then $\sqrt{6} = 2 + \frac{1}{2 + \frac{1}{4+x}}$, or $2 + \frac{1}{9/4}$, or $\frac{22}{9}$.

(There is a quicker and dirtier way to generate these, rather than work the whole fraction through each time – but that’s for another article.)

But what about the general Pell’s equation?

I thought you’d never ask that, either!

It turns out that the work we’ve just done to find a solution to $x^2 - 6y^2 = 1$ is part of the solution here, as well – this is the Pell’s resolvent.

As long as we have an answer to $x^2 - ny^2 = N$, we can figure out infinitely many ((I’m not certain this method generates all of them.)).

In our case, we do: $x^2 - 6y^2 = -5$ has the obvious solution $(x_0, y_0) = (1,1)$.

If we call the solutions to the resolvent $(u_i, v_i)$, then we can generate new solutions using the recurrence relation:

  • $x_i = x_0 u_i + n y_0 v_i$
  • $y_i = y_0 u_i + x_0 v_i$

In our case, $(x_0, y_0) = (1,1)$ and the $(u_i,v_i)$s start $(5,2), (49,20), \dots$.

So:

  • $x_1 = (1)(5) + 6(1)(2) = 17$
  • $y_1 = (1)(2) + (1)(5) = 7$

So $17^2 - 6 \times 7^2 = 289 - 294$, which is indeed -5!

The next solution is

  • $x_2 = (1)(49) + 6(1)(20) = 169$
  • $y_2 = (1)(20) + (1)(49) = 69$

This is the one we’re interested in.

Back to the original problem

Remember way back several pages ago, we were trying to solve $(2r-1)^2 - 6(2b-1)^2 = -5$?

We’ve come up with two answers here (and could generate infinitely many). The first pair is: $(2r-1, 2b-1) = (17,7)$, or $r=9$ and $b=4$ (and, implicitly, $n=13$). Unfortunately, this doesn’t quite work with the original equations: $2r(r-1) = 144$, which is not $13\times 12$.

The second pair gives $r=85$, $b=35$ and $n=120$, and $2r(r-1) = 170 \times 84$; this turns out to be the same as $120 \times 119$ because $17 \times 10 \times 7 \times 12 = 12 \times 10 \times 7 \times 17$ (obviously).

Conclusion

This is clearly a completely impractical way to solve a problem that drops out in a few lines of algebra. However, it is also a tremendous introduction to continued fractions and the Pell’s equation. I hope you found it valuable.