I first encountered Pell's equation when I was in 10th grade so I thought it was quite common. But alas, I cannot find a blog on Codeforces that talks about it, which makes me quite sad. So here, I will talk about it for a bit.

First, let me introduce the equation, since it would be hard to talk about it otherwise. It is the diophantine equation

where $$$n$$$ is a positive integer. Usually, we are given a positive integer $$$n$$$ and then we would be asked to find the smallest positive integer $$$x$$$ such that there exists a positive integer $$$y$$$ that satisfies the equation (or vice versa, but it doesn't matter). Usually, this minimal solution is called the fundamental solution.

It is easy to see that no fundamental solution exists whenever $$$n$$$ is a perfect square. However, it is not as easy to see that there is always a solution whenever $$$n$$$ is not a perfect square. This is true, but I will omit the proof since I haven't bothered myself to learn it. After learning this fact, you try to see if it really is true since you are quite stubborn. You probably code up some inefficient program that tries to naively find the fundamental solution for non-square $$$n$$$, only to get stymied by $$$n=61$$$ where the fundamental solution is $$$(1766319049, 226153980)$$$. So next, you would ask yourself: how do I calculate the fundamental solution efficiently?

Well, of course, you would notice that if $$$(x, y)$$$ is a solution to the Pell's equation, then $$$\frac{x}{y}$$$ would be a good approximation for $$$\sqrt{n}$$$. And you also know another way to find a good approximation for $$$\sqrt{n}$$$: continued fractions! You try to use this discovery to optimize your code and suddenly, $$$n=61$$$ is a piece of cake! However, as you rejoice, Erdos laughs at you from his grave since your code is still not good enough to find the answer for Erdos Problem 3 in a reasonable amount of time.

Since you can't travel all the way to Erdos' grave just to spit on it, you instead resolve to solve this problem without using OEIS. And so, you try to find some more patterns. After some experimentation, you discover that the fundamental solution is found only if you truncate the continued fraction at the step before the last in a period (yes, continued fractions of square roots are periodic and you already knew that). Afterwards, it doesn't take you long to find that it always occurs either at the first period or at the second period. Armed with these, you again optimize your code and it finally gives you the answer... after a couple of minutes. But you decide that this ia a reasonable enough amount of time and decide to consider the problem solved.

After all this, you might find yourself asking yourself: now that I can find the fundamental solution somewhat efficiently whenever it exists, how do I find more solutions? You might think that since finding the fundamental solution was quite a pain, finding more will be even more pain. However, after some emperimentation again, you find out that the solutions are always the continued fractions truncated a step before the end of either every period or every second period.

However, let me give you a much more efficient way if you already have the fundamental solution or any other solution. Given $$$n$$$ and a solution $$$(x, y)$$$, a new solution $$$(x', y')$$$ can be found using the equation

and then substituting any integer $$$k \geq 2$$$. In fact, if we denote by $$$(x_i, y_i)$$$ the $$$i^{th}$$$ smallest solution, then it is true that

which is quite magical (at least to me it is since I haven't bothered to learn the proof).