Pell’s equation

Let {D} be a positive non-square integer.
Consider the Pell equation {\displaystyle X^2-DY^2=1.}

Let \displaystyle z=x+y \sqrt{D} , \bar{z}=x-y \sqrt{D}, N(z) = z\bar z = X^2-DY^2.

If {z} solves the equation {N(z)=1}, so does {\pm z^n.} In fact, we see that there is a single {z} which generates all the possible solutions this way.

Theorem: (Minimal solution generates all the solutions)
If {z_{0}=x_0+y_0\sqrt{D}} is the minimal element of {\mathbb{Z}[\sqrt{D}]} with {z_{0}>1} and {N\left(z_{0}\right)=1,} then every element {z} with {N(z)=x^2-Dy^2=1} if of the form {z=\pm z_{0}^{n}, n \in \mathbb{Z}.} That is {x+y \sqrt{D} = \pm (x_0+y_0 \sqrt{D})^n.}

Proof: Suppose that {N(z)=1} for some {z>0}. We have {z_{0}^{k} \leq z<z_{0}^{k+1}} for a unique integer {k}. Then the number {z_{1}=z z_{0}^{-k}=z \bar{z}_{0}^{k}} satisfies {1 \leq z_{1}<z_{0}} and {N\left(z_{1}\right)=N(z) N\left(z_{0}\right)^{-k}=N(z)=1 .} The minimality of {z_{0}} forces {z_{1}=1} and therefore {z=z_{0}^{k}}.

Theorem (Existence of a solution)
Pell’s equation has a solution in positive integers.

Proof: Dirichlet’s approximation gives infinitely many positive integers {(p, q)} satisfying {\left|\alpha-\frac{p}{q}\right|<\frac{1}{q^{2}}} for any irrational {\alpha.} Use the {\alpha =\sqrt{D}}, we get infinitely many solutions to {X^2-DY^2=k} for some {|k| < 2\sqrt{D}.} Take two solutions {z_1=(x_1, y_1), z_2=(x_2, y_2)} such that {x_1=x_2, y_1=y_2 \mod k.} Now if {z_1> z_2}, the congruence conditions makes {\frac{z_1}{z_2}} to be in {\mathbb{Z}[\sqrt{D}]} even though a priori the ratio is just rational. The solution is then given by {\frac{z_1}{z_2}.}

So good approximation to {\sqrt{D}} provide solutions to Pell’s equations. In fact, we see that {\sqrt{D} =[a_0, \overline{a_1,a_2,\cdots,a_{n-2} ,a_{n-1}, a_n]}=[a_0, \overline{a_1,a_2,\cdots,a_2, a_1, 2a_0}]} is the continued fraction expansion of {\sqrt D,} then the convergent {\frac{p_k}{q_k}} satisfy {p_{tn-1}^2-Dq_{tn-1}^2=(-1)^{tn}.} Therefore {t=n-1} for {n} even and {t=2n-1} for {n} odd, give you a solution to Pell’s equation.

\displaystyle \displaystyle X^2-DY^2=-1.

What about this equation? As we saw above if the period of the continued fraction of {\sqrt{D}} is odd, then we have a solution to {X^2-DY^2} given by the {n-1}-th convergent. On the other hand, we see that if there is solution, it has to give good approximations to {\sqrt{D}} and hence appears in the convergents. Therefore this negative Pell’s equation has solutions precisely when the period of continued fraction of {\sqrt{D}} is odd. Looking at the congruences, we see that this can have solution only if all the odd prime factors of {D} are {1 \mod 4} and {4\not | D.} And these conditions are just necessary, they don’t guarantee that {\sqrt D} has odd period.

\displaystyle \displaystyle X^2-DY^2=\pm 4.

If {T+U\sqrt{D}} is the minimal solution to this equation, with any of the signs, then {\epsilon_0 =\frac{T+U\sqrt{D}}{2}} is called the fundamental solution.
Any solution to {\displaystyle X^2-DY^2=\pm 4} is given by {z= \pm \epsilon_0^n.}

If the fundamental solution {(T,U)} is such that {2|T,2|S, N(\epsilon_0)=\frac{T^2-DU^2}{4}=1,} then {\epsilon_0} is the same as the minimal solution to Pell’s equation {\displaystyle X^2-DY^2=1}
If {2| T, 2\not|S, \frac{T^2-DU^2}{4}=1}, then {4|D} and {\epsilon_0^2} is the solution for Pell’s equation.
{2|T, N(\epsilon_0)=\frac{T^2-DU^2}{4}=-1,} then {z_0 = \epsilon_0^2}
{2\not| T, N(\epsilon_0)=\frac{T^2-DU^2}{4}=1,} then {z_0 = \epsilon_0^3} {2\not| T, N(\epsilon_0)=\frac{T^2-DU^2}{4}=-1,} then {z_0 = \epsilon_0^6}

\displaystyle \begin{array}{|c|c|c||c|} \hline T(\bmod ~~2) & U(\bmod ~~2) & sign & z_0 \\ \hline \hline 0 & 0 & 1 & \epsilon_0\\ 0 & 1 & 1 & \epsilon_0^2 \\ 0 & - & -1 & \epsilon_0^2 \\ 1 & - & 1 & \epsilon_0^3 \\ 1 & - & -1 & \epsilon_0^6 \\ \hline \end{array}

Examples:

\displaystyle X^2-2Y^2=\pm1

\displaystyle \sqrt 2 = 1+ (\sqrt {2} -1) = [1; \frac{1}{\sqrt {2} -1}]
\displaystyle =[1; \sqrt{2}+1] =[1, 1+1, 1+\sqrt{2}] = [1; 2, 1+ 1, 2, \sqrt{2}+1] = [1, 2, 2, 2,...] = [1, \bar 2]
{[1;]} gives the solution to negative Pell equation, that is {(1,1)} is the solution to {X^2-2Y^2=-1}
{[1;2]= \frac{3}{2}} is the convergent giving fundamental solution. That is {(3,2)} is the least solution to {X^2-2Y^2=1.}

\displaystyle X^2-2Y^2=\pm4

We observe that {2} has to divide {X, Y} and hence every solution reduces to twice corresponding solution for {X^2-DY^2=\pm1.}
Therefore {\epsilon_0 = {1+\sqrt{2}}.}

\displaystyle X^2-3Y^2=\pm1

\displaystyle \sqrt 3 = 1+ (\sqrt {3} -1) = [1; \frac{1}{\sqrt {3} -1}]
\displaystyle = [1; \frac{\sqrt {3} +1}{2}] =[1; 1+ \frac{\sqrt {3} -1}{2}]= [1; 1, \frac{2}{\sqrt {3} -1}]
\displaystyle =[1; 1, \sqrt{3}+1] = [1; 1, 2, 1, \sqrt{3}+1] = 1; 1, 2, 1, 2, 1, \sqrt{3}+1] = [1; \overline {1,2}]

Even period. So no solution to the negative Pell’s equation. And for the least solution for Pell’s equation we have {(2,1)} because {\frac{2}{1} = [1; 1].}

\displaystyle X^2-3Y^2=\pm4

No solution with negative sign. And the solution with positive sign is just { \epsilon_0 = z_0 =2+\sqrt{3}}

\displaystyle X^2-5Y^2=\pm1

\displaystyle \sqrt{5} = [2, \bar 4]
{[2;]} gives solution for negative Pell’s equation which is {(2,1).}
{\frac{9}{4}=[2;4]} gives the solution for Pell’s equation which is {(9,4)}
{(9+4\sqrt{5}) = (2+\sqrt 5)^2}

\displaystyle X^2-5Y^2=\pm4

{(1,1)} satisfies {X^2-5Y^2=-4} and hence {\epsilon_0 = \frac{1+\sqrt{5}}{2}.}
\displaystyle 2+\sqrt{5} =\left(\frac{1+\sqrt{5}}{2}\right)^3 = \epsilon_0^3
\displaystyle 9+4\sqrt{5}= \left(\frac{1+\sqrt{5}}{2}\right)^6 = \epsilon_0^6

\displaystyle X^2-6Y^2=\pm1

\displaystyle \sqrt 6 = [2;\overline{2,4}]
No solution with negative sign. For positive sign the solution is given by {[2;2]=\frac{5}{2},} that {(5,2) =5+2\sqrt{6}.}

\displaystyle X^2-6Y^2=\pm4

{2} has to divide the solutions again. Hence {\epsilon_0 =5+2\sqrt{6}.}
\displaystyle X^2-13Y^2=\pm1
\displaystyle \sqrt{13}=[3, \overline{1,1,1,1,6}]
{[3, 1,1,1,1]=\frac{18}{5}} is the solution for negative Pell.
{[3, 1,1,1,1,1,6,1,1,1,1] =\frac{649}{180}} is the least solution for Pell.
Notice that {(18+5\sqrt{13})^2=649+180\sqrt{13}.}

\displaystyle X^2-13Y^2=\pm4

The convergent {[3;]} gives a solution {(3,1)} to {X^2-13Y^2=-4}
Therefore fundamental unit {\epsilon_0 = \frac{3+\sqrt{13}}{2}.}
\displaystyle 18+5\sqrt{13} = \left(\frac{3+\sqrt{13}}{2}\right)^3=\epsilon_0^3
\displaystyle 649+180\sqrt{13}= \left(\frac{3+\sqrt{13}}{2}\right)^6=\epsilon_0^6

\displaystyle X^2-DY^2=1

\displaystyle \begin{array}{r|r|r} D & X & Y \\ \hline 2 & 3 & 2 \\ 3 & 2 & 1 \\ 5 & 9 & 4 \\ 6 & 5 & 2 \\ 7 & 8 & 3 \\ 8 & 3 & 1 \\ 10 & 19 & 6 \\ 11 & 10 & 3 \\ 12 & 7 & 2 \\ 13 & 649 & 180 \\ 14 & 15 & 4 \\ 15 & 4 & 1 \\ 17 & 33 & 8 \\ 18 & 17 & 4 \\ 19 & 170 & 39 \\ 20 & 9 & 2 \\ 21 & 55 & 12 \\ 22 & 197 & 42 \\ 23 & 24 & 5 \\ 24 & 5 & 1 \\ 26 & 51 & 10 \\ 27 & 26 & 5 \\ 28 & 127 & 24 \\ 29 & 9801 & 1820 \\ 30 & 11 & 2 \\ 31 & 1520 & 273 \\ 32 & 17 & 3 \\ 33 & 23 & 4 \\ 34 & 35 & 6 \\ 35 & 6 & 1\\ 37 & 73 & 12 \\ 38 & 37 & 6 \\ 39 & 25 & 4 \\ 40 & 19 & 3 \\ 41 & 2049 & 320 \\ 42 & 13 & 2 \\ 43 & 3482 & 531 \\ 44 & 199 & 30 \\ 45 & 161 & 24 \\ 46 & 24335 & 3588 \\ 47 & 48 & 7 \\ 48 & 7 & 1 \\ 50 & 99 & 14 \\ 51 & 50 & 7 \\ 52 & 649 & 90 \\ 53 & 66249 & 9100 \\ 54 & 485 & 66 \\ 55 & 89 & 12 \\ 56 & 15 & 2 \\ 57 & 151 & 20 \\ 58 & 19603 & 2574 \\ 59 & 530 & 69 \\ 60 & 31 & 4 \\ 61 & 1766319049 & 226153980 \\ 62 & 63 & 8 \\ 63 & 8 & 1 \\ 65 & 129 & 16 \\ 66 & 65 & 8 \\ 67 & 48842 & 5967 \\ 68 & 33 & 4\\ 69 & 7775 & 936 \\ 70 & 251 & 30 \\ 71 & 3480 & 413 \\ 72 & 17 & 2 \\ 73 & 2281249 & 267000 \\ 74 & 3699 & 430 \\ 75 & 26 & 3 \\ 76 & 57799 & 6630 \\ 77 & 351 & 40 \\ 78 & 53 & 6 \\ 79 & 80 & 9 \\ 80 & 9 & 1 \\ 82 & 163 & 18 \\ 83 & 82 & 9 \\ 84 & 55 & 6 \\ 85 & 285769 & 30996 \\ 86 & 10405 & 1122 \\ 87 & 28 & 3 \\ 88 & 197 & 21 \\ 89 & 500001 & 53000 \\ 90 & 19 & 2 \\ 91 & 1574 & 165 \\ 92 & 1151 & 120 \\ 93 & 12151 & 1260 \\ 94 & 2143295 & 221064 \\ 95 & 39 & 4 \\ 96 & 49 & 5 \\ 97 & 62809633 & 6377352 \\ 98 & 99 & 10 \\ 99 & 10 & 1 \end{array}

Posted in $.

Leave a comment