While doing my math/CS undergraduate degree at the University of Alberta, I presented at the Seminar in Number Theory for Alberta Students on solving Pell equations using continued fractions. I also presented an O(n) method for finding the fundamental solution to the Pell equation \(x^2-dy^2=1\) during my talk. In this blog post, I’m going to present the essential parts of my talk on how this O(n) method works, show the results of it for up to \(d=99\), and also analyze the negative Pell equation \(x^2-dy^2=-1\).
As a note, the first several definitions are all rewritten from David Burton’s Elementary Number Theory, which greatly inspired this post. Burton’s text is one of the most well-written and comprehensive number theory books I know, and I strongly recommend it.
Definition: A finite continued fraction is of the form $$a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{\ddots+\frac{1}{a_{n-1}+\frac{1}{a_n}}}}}},$$ where the \(a_i\)’s are positive real numbers, except possibly \(a_0\) which may be \(0\). The fraction is called simple if all the \(a_i\) are integers. We often denote such a fraction as \([a_0; a_1, \cdots, a_n]\)
For instance, $$[1; 2, 3, 4]=1+\frac{1}{2+\frac{1}{3+\frac{1}{4}}}=1+\frac{1}{2+\frac{1}{\frac{13}{4}}}=1+\frac{1}{2+\frac{4}{13}}=\cdots=\frac{43}{30}.$$
Definition: Given a continued fraction \([a_0; a_1, \cdots, a_n]\), we define the convergent \(C_k\) that is obtained by cutting off the fraction after \(a_k\) to be \(C_k=[a_0; a_1, \cdots, a_k], 1\le k\le n.\) By definition, \(C_0=a_0\).
Example: We can see that the continued fraction for \(\phi=\frac{1+\sqrt{5}}{2}\) is given by \(\phi=[1; 1, 1, \cdots]\). To see this, observe that \(\phi\) satisfies the equation \(\phi=1+\frac{1}{\phi}=1+\frac{1}{1+\frac{1}{\phi}}=\cdots\).
If we compute the \( k^{\mbox{th}}\) convergent of the continued fraction for \( \phi\), we get the Fibonacci numbers! Observe that \( C_0=\frac{1}{1}, C_1=\frac{2}{1}, C_2=1+\frac{1}{1+\frac{1}{1}}=\frac{3}{2}, C_3=1+\frac{2}{3}=\frac53\), and so forth. In general, we claim that \(C_k=\frac{F_{k+2}}{F_{k+1}}\), where \(F_1=F_2=1\) and \(F_n=F_{n-1}+F_{n-2}\) for \(n\ge 2\). To prove this, the base cases are given above. If it holds for \(k\ge 1\), then $$C_{k+1}=1+\frac{1}{C_k}=1+\frac{F_{k+1}}{F_{k+2}}=\frac{F_{k+2}+F_{k+1}}{F_{k+2}}=\frac{F_{k+3}}{F_{k+2}},$$ hence the pattern continues by induction.
This is related to the result \(\phi=\lim_{n\to \infty}\frac{F_{n+1}}{F_n}\).
Theorem: Given a continued fraction \([a_0; a_1, \cdots, a_n]\), we define the recurrence relationships given by \(p_0=a_0, q_0=1, p_1=a_1a_0+1, q_1=a_1\), and in general for \(2\le k\le n, p_k=a_kp_{k-1}+p_{k-2}, q_k=a_kq_{k-1}+q_{k-2}.\) Then the \(latex k^{\mbox{th}}\) convergent is given by \(C_k=\frac{p_k}{q_k}\).
Example: Consider \(\phi=[1; 1, 1, \cdots]\). Since \(a_i=1\) for every \(i\), we have \(p_0=1, q_0=1, p_1=2, q_1=1\), and in general \(p_k=p_{k-1}+p_{k-2}\) and \(q_k=q_{k-1}+q_{k-2}\). Thus \(p_k=F_{k+2}\) and \(q_k=F_{k+1}\) and we see \(C_k=\frac{p_k}{q_k}=\frac{F_{k+2}}{F_{k+1}}\) as before.
Proof: We see that \(C_0=a_0=\frac{p_0}{q_0}, C_1=a_0+\frac{1}{a_1}=\frac{a_1a_0+1}{a_1}=\frac{p_1}{q_1}\), and \(C_2=a_0+\frac{1}{a_1+\frac{1}{a_2}}=a_0+\frac{a_2}{a_1a_2+1}=\frac{a_0a_1a_2+a_0+a_2}{a_1a_2+1}=\frac{a_2(a_0a_1+1)+a_0}{a_1a_2+1}=\frac{p_2}{q_2}.\)
In general, assume the statement holds for every value \(2\le k\le m\), and we show it holds for \(k=m+1\). Observe that since \( p_{m-1}, q_{m-1}, p_{m-2}, q_{m-2}\) are independent of \(a_m\), we can write
Therefore \(p_{m+1}=a_{m+1}p_m+p_{m-1}\) and \(q_{m+1}=a_{m+1}q_m+q_{m-1}\) as desired.
Definition: In an infinite convergent sequence, if we have a block that repeats over and over, we then write \([a_0; a_1, \cdots, a_m, b_1, \cdots, b_n, b_1, \cdots, b_n, \cdots]=[a_0; a_1, \cdots, a_m, \overline{b_1, b_2, \cdots, b_n}]\).
Example: Convert \(\sqrt{3}\) to a continued fraction.
Solution: Let 
Taking the reciprocal of the equation gives us 
![\sqrt{3}=[1;\overline{1,2}]](https://s0.wp.com/latex.php?latex=%5Csqrt%7B3%7D%3D%5B1%3B%5Coverline%7B1%2C2%7D%5D&bg=ffffff&fg=000000&s=0&c=20201002)
Observe that the first convergent of 
Theorem: If the period length, 
Exercise: Compute the continued fraction for 
Now, we’ll examine the case where the period length of the continued fraction is odd. In particular, continue the continued fraction for 
Simplifying the left-hand side by conjugating the denominator, we get 
![\sqrt{5}=[2;\overline{4}]](https://s0.wp.com/latex.php?latex=%5Csqrt%7B5%7D%3D%5B2%3B%5Coverline%7B4%7D%5D&bg=ffffff&fg=000000&s=0&c=20201002)
The zeroth convergent of this continued fraction is 
This result also generalizes as follows:
Theorem: If the period length, 
We can now write a computer program that solves Pell equations by combining these two theorems. Assume that we have a dictionary of continued fractions for each integer
for d in continued_fracs.keys():
a = continued_fracs[d]
n = len(a)-1
p = [a[0], a[0]*a[1]+1]
q = [1, a[1]]
if(n%2 == 0):
for k in range(2, n):
p.append(a[k]*p[k-1]+p[k-2])
q.append(a[k]*q[k-1]+q[k-2])
print("Fundamental solution to x^2-dy^2=1 for d=%d is x=%d, %d" %(d, p[n-1], q[n-1]))
print("No solution to negative Pell equation x^2-dy^2=-1 for d=%d" %(d))
else:
end_a = a[1:]
a += end_a
for k in range(2, 2*n):
p.append(a[k]*p[k-1]+p[k-2])
q.append(a[k]*q[k-1]+q[k-2])
print("Fundamental solution to x^2-dy^2=1 for d=%d is x=%d, y=%d:"%(d, p[2*n-1], q[2*n-1]))
print("Fundamental solution to x^2-dy^2=-1 for d=%d is x=%d, y=%d"%(d, p[n-1], q[n-1]))In lines 2 through 5, we compute the length of the continued fraction’s period length and the initial values of the recursive sequences 
In lines 13 through 19, if the period length is odd, we have to compute up to 
The full Python file can be found on GitHub, and the output of the code can also be found here. The output for up to d=10 is also printed below in the table:
Value of  | Solution to Pell Equation | Solution to Negative Pell Equation |
 |  |  |
| |  | None |
 |  | |
 |  | None |
 |  | None |
 |  | None |
 |  | |
Large Language Model Exploration:
If you’ve made it this far, you may wonder how large language models would do in solving the negative Pell equation
The one on the left is a complete fabrication, while Grok-2 impressively solves it correctly. If you experiment with other large language models, I’d be curious to see which ones can and can’t solve questions on negative Pell equations correctly.
References:
- David Burton, “Elementary Number Theory”, 7th Edition, 2012.
- W. Sierpinski, “Elementary Theory of Numbers”, 1988
and 
such that: 
and 
.
is odd or even. In the first case, we know that the primitive Pythagorean triple can be generated by 
where 
and 
. The only coprime positive integers that satisfy this are 
and 
. These generate the solution triplet 
and 
. However, this gives a non-primitive solution since 
. Since my 
to you all.
, then since 
, the digits in the thousands place are 
. We see that 
therefore, 
. 
. We begin by looking at the units digit of our cube, which is 
, therefore, the tens digit of the cube must be 
. 
.
.
.
. 
. 
. 
. 
. 
are the same. 
and 
, you only need to memorize that 
. For larger 5th roots, you’ll need to use a table to establish bounds. 
. For now, we’ll tackle the same case as in Dr. Ali’s video and assume that 
. 
, we see every term is a multiple of 
, except for the last two. Therefore, when we consider the last three digits of 
, we get 
. Since 
which has the last three digits 
. We therefore see that the fifth root of this number was 
, where we assume for now that 
, therefore we can further reduce to get 
. 
, then 
, and we can use the same trick again: 
, then the last three digits of our number will be 
, so we have to add 
, since 
we know it’s the first case and we get the fifth root as 
.
, we see that 
, therefore, we have the second case and get the fifth root as 
. 
where 
, this further reduces as 
, the last three digits of 
will be 
, so we perform the calculation 
, we take the last three digits, 
, and using the formula above get 
, which is indeed the fifth root. 
, then 
, and therefore the last three digits will be 
. In this case, we subtract 
, since 
, we use the calculation from the second case to get a fifth root of 
, then it can be represented in the form 
, where 
. 
, we take the last three digits, 
, and perform the calculation above to get a fifth root of 
.
.
.
. 
.
. 
.
or 
. If we start with a number between 
, then the range for the fifth power is between 
and 
. In this case, we can use the same trick as above, to get a number between 
, we see this number is approximately 
, therefore the fifth root must be between 
, and adding 
(you can verify this is the fifth root of the original number using WolframAlpha). 
. Using the table above, you know this number is approximately 
, which is in the bottom-most row, therefore the number which was cubed was between 
, and since the number ends in 
to determine the mod 
.
.
.
.
. 
.
has the largest dots.
people effectively. Can we always obtain this bound for a bar with 
. It’s interesting to note the outliers here are when 
.
, the best possible scenario would be:
gives the following values that are optimal:
and 
are non-negative integers. This leads me to conjecture that these forms contain all the initial values of 
, we vary the gap size, 
to produce the following seating configurations:
. In this case, not only is length 25 optimal for a gap size of 2, but it’s optimal for every gap!
:
. We see the initial part is a step function in threes, similar to 
.
. Determine their sum.
, where 
and 
are primes.
and 
, 
. We now add 
, the quotient in the divisibility above to both sides of the equation to produce:
Therefore 
, however, 
. Similarly 
. This time, 
, therefore 
. 
.
by 
, however, this gives the equation 
, and we don’t have any better ideas for how to factorize 
. Therefore, instead, we’ll use the prime factorizations of some other numbers close to 
:
, we would take the original equation and subtract 
to produce 
Then, we know 
, however, clearly 
.
or 
, we simply add 
. Therefore, again 
, however, clearly 
, hence the same is true for 
or 
, we add 
to our original equation (or more simply, 
to the equation in the last paragraph) to get
, we see 
, however, clearly 
. Similarly, 
. Now since 
, we see 
, hence 
, and 
. 
.
. One way to quickly compute this in our heads would be to notice
. We notice 
, while 
, therefore, 
. Â We then subtract 
from both sides of our equation:
, we know it must be a single numerical digit! We therefore just consider the unit digit of the numerator which is 
must be 
. Therefore 
.
.
using the prime factorization of next year, 2021. I’ll leave this as an exercise for anyone interested.
such that 
(Source: 1997 IMO Shortlist N6)
is known to have no nontrivial solutions for 
due to Fermat’s Last Theorem (if you’ve not read 
.
giving the equation 
Assume we multiply the equation by a number of the form 
. Â We then will have: 
Since we want the first part to be a perfect square, we should have 
 and 
. Since the second part should be a perfect cube, we should have 
 and 
. Finally, since the last part should be a perfect fourth power, 
 and 
. Solving these system of linear congruences gives 
 and 
! We get back the equation 
, from which we read off the solution 
. 
again to obtain 
We then want the exponents on the leftmost term to be divisible by 
, and on the rightmost term to be divisible by 
. This is equivalent to:
  and  
. Since 
, we can use the Chinese Remainder Theorem to know that 
has a unique solution mod 
. 
, in the case that 
, therefore, we have to use an extended version of the Chinese Remainder Theorem. Thankfully, since 
, we are still guaranteed a unique solution for 
to the original equation. Once we have the congruences for 
. If we in general write 
and 
, we then find
. Notice for 
, this gives the solution triple 
found above.Â