Pell Equations and Generalized Pell Orbits

Fact [F1] gives the coordinate product formula immediately: $\alpha \beta =(xu+Dyv)+(xv+yu)\sqrt{D}\mathrm{.}$

Applying the norm formula from [F1] to step 1.1 and expanding gives $N_D(\alpha \beta )=(xu+Dyv{)}^2-D(xv+yu{)}^2=(x^2-D{y}^2)(u^2-D{v}^2)=N_D(\alpha )N_D(\beta )\mathrm{.}$

The element $1=1+0\sqrt{D}$ satisfies $N_D(1)=1$, so it lies in $G_D$. If $\alpha ,\beta \in G_D$, then [F2] gives $N_D(\alpha \beta )=N_D(\alpha )N_D(\beta )=1,$ so $\alpha \beta \in G_D$.

If $\alpha =x+y\sqrt{D}\in G_D$, then [F1] gives $x^2-D{y}^2=1$, hence $\alpha (x-y\sqrt{D})=x^2-D{y}^2=1.$ Therefore ${\alpha }^{-1}=x-y\sqrt{D}\in G_D$, since $N_D(x-y\sqrt{D})=1$ by [F1].

Associativity is inherited from multiplication of real numbers, and [F3] is symmetric in $(x,y)$ and $(u,v)$, so multiplication on $G_D$ is commutative. Together with steps 1.1 and 1.2, this proves that $G_D$ is an abelian group.

At $n=0$ one has ${\alpha }_0=\sqrt{D}=\frac{\sqrt{D}+0}{1},$ so the claimed form holds with $P_0=0$ and $Q_0=1$, and certainly $Q_0>0$ and $Q_0\mid D-P_0^2=D$.

Assume ${\alpha }_n=\frac{\sqrt{D}+P_n}{Q_n},Q_n>0,Q_n\mid D-P_n^2\mathrm{.}$ Let $a_n$ be the integer from [F1], and set $P_{n+1}:=a_n{Q}_n-P_n\mathrm{.}$ Since ${\alpha }_n-a_n>0$, one has $\sqrt{D}-P_{n+1}=\sqrt{D}+P_n-a_n{Q}_n>0,$ so $D-P_{n+1}^2>0$. Also $P_{n+1}\equiv -P_n(\mathrm{m}\mathrm{o}\mathrm{d}{Q}_n)$, hence $P_{n+1}^2\equiv P_n^2(\mathrm{m}\mathrm{o}\mathrm{d}{Q}_n)$ and therefore $Q_n\mid D-P_{n+1}^2$. Thus $Q_{n+1}:=\frac{D-P_{n+1}^2}{Q_n}$ is a positive integer. Rationalizing the denominator now gives ${\alpha }_{n+1}=\frac{1}{{\alpha }_n-a_n}=\frac{Q_n}{\sqrt{D}-P_{n+1}}=\frac{\sqrt{D}+P_{n+1}}{Q_{n+1}}\mathrm{.}$

If also $\frac{\sqrt{D}+P}{Q}=\frac{\sqrt{D}+P^{\mathrm{\prime }}}{Q^{\mathrm{\prime }}}$ with $Q,Q^{\mathrm{\prime }}>0$, then cross-multiplication gives $(Q^{\mathrm{\prime }}-Q)\sqrt{D}=Q{P}^{\mathrm{\prime }}-Q^{\mathrm{\prime }}P\mathrm{.}$ If $Q^{\mathrm{\prime }}\mathrm{\ne }Q$, this would make $\sqrt{D}$ rational, impossible because $D$ is a positive nonsquare integer. Hence $Q^{\mathrm{\prime }}=Q$, and then $P^{\mathrm{\prime }}=P$. So the normalized pair $(P_n,Q_n)$ is unique at each stage. Steps 1.1 and 1.2 therefore prove the statement for all $n\ge 0$.

Substitute the expression from [F3] into [F1] and clear denominators. One gets $\sqrt{D}((\sqrt{D}+P_{n+1})q_n+Q_{n+1}{q}_{n-1})=(\sqrt{D}+P_{n+1})p_n+Q_{n+1}{p}_{n-1}\mathrm{.}$ Comparing the rational and irrational coefficients of $1$ and $\sqrt{D}$ yields $D{q}_n=P_{n+1}{p}_n+Q_{n+1}{p}_{n-1},p_n=P_{n+1}{q}_n+Q_{n+1}{q}_{n-1}\mathrm{.}$

Multiply the second identity of step 1.1 by $p_n$, the first by $q_n$, and subtract. Then $p_n^2-D{q}_n^2=Q_{n+1}(p_n{q}_{n-1}-p_{n-1}{q}_n)=(-1{)}^{n+1}{Q}_{n+1}$ by [F2].

For every $n\ge 0$, [F1] and the floor inequality $a_n\le {\alpha }_n<a_n+1$ give $P_{n+1}=a_n{Q}_n-P_n<\sqrt{D}\mathrm{.}$ Also ${\alpha }_n>1$ for $n\ge 1$, so $Q_n<\sqrt{D}+P_n<2\sqrt{D}\mathrm{.}$ Since $P_n<\sqrt{D}$ for $n\ge 1$, the recurrence in [F1] gives $Q_n\le P_{n+1}+P_n<\sqrt{D}+P_{n+1},$ and therefore $Q_{n+1}=\frac{(\sqrt{D}-P_{n+1})(\sqrt{D}+P_{n+1})}{Q_n}>\sqrt{D}-P_{n+1}\mathrm{.}$ Hence $P_n<\sqrt{D}<P_n+Q_n(n\ge 1)\mathrm{.}$ So for $n\ge 1$ the pair $(P_n,Q_n)$ lies in the finite set of integer pairs with $-\sqrt{D}<P<\sqrt{D}$ and $0<Q<2\sqrt{D}$.

Let $S$ be the finite set of integer pairs $(P,Q)$ satisfying $Q>0,Q\mid D-P^2,P<\sqrt{D}<P+Q\mathrm{.}$ Step 1.1 shows that every $(P_n,Q_n)$ with $n\ge 1$ lies in $S$, and [F1] defines a successor map $T:S\to S$. This map is bijective: given $(P^{\mathrm{\prime }},Q^{\mathrm{\prime }})\in S$, put $Q:=\frac{D-(P^{\mathrm{\prime }}{)}^2}{Q^{\mathrm{\prime }}}\mathrm{.}$ The interval $(\sqrt{D}-Q,\sqrt{D})$ has irrational endpoints and length $Q$, so it contains exactly one integer $P$ in the residue class $-P^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}Q)$. Then $a:=\frac{P+P^{\mathrm{\prime }}}{Q}\in \mathbb{Z},P^{\mathrm{\prime }}=aQ-P,Q^{\mathrm{\prime }}=\frac{D-(P^{\mathrm{\prime }}{)}^2}{Q},$ so $T(P,Q)=(P^{\mathrm{\prime }},Q^{\mathrm{\prime }})$. Since the orbit of $(P_1,Q_1)$ stays in the finite set $S$, there is a least $\mathrm{\ell }\ge 1$ with $T^{\mathrm{\ell }}(P_1,Q_1)=(P_1,Q_1)$, that is, $(P_{\mathrm{\ell }+1},Q_{\mathrm{\ell }+1})=(P_1,Q_1)$.

The recurrence at $n=0$ gives $P_1=a_0,Q_1=D-a_0^2\mathrm{.}$ Apply the inverse construction of step 2.1 to $(P_1,Q_1)$. Then $Q=\frac{D-a_0^2}{Q_1}=1,$ and the interval $(\sqrt{D}-1,\sqrt{D})$ contains the unique integer $a_0$. So the unique predecessor of $(P_1,Q_1)$ in $S$ is $(a_0,1)$. Since $(P_{\mathrm{\ell }},Q_{\mathrm{\ell }})$ is the predecessor of $(P_1,Q_1)$ along the cycle from step 2.1, one has $P_{\mathrm{\ell }}=a_0,Q_{\mathrm{\ell }}=1.$ The recurrence formula $P_{\mathrm{\ell }+1}=a_{\mathrm{\ell }}{Q}_{\mathrm{\ell }}-P_{\mathrm{\ell }}$ now gives $a_{\mathrm{\ell }}=P_{\mathrm{\ell }}+P_{\mathrm{\ell }+1}=a_0+a_0=2a_0\mathrm{.}$

We prove by induction on $j$ that $P_j=P_{\mathrm{\ell }-j+1}(1\le j\le \mathrm{\ell }),Q_{j-1}=Q_{\mathrm{\ell }-j+1}(1\le j\le \mathrm{\ell })\mathrm{.}$ The case $j=1$ is step 3.1 together with $Q_0=Q_{\mathrm{\ell }}=1$. Assume it for some $j<\mathrm{\ell }$. Then [F1] gives $Q_j=\frac{D-P_j^2}{Q_{j-1}}=\frac{D-P_{\mathrm{\ell }-j+1}^2}{Q_{\mathrm{\ell }-j+1}}=Q_{\mathrm{\ell }-j}\mathrm{.}$ Also $P_{j+1}$ and $P_{\mathrm{\ell }-j}$ are both integers congruent to $-P_j$ modulo $Q_j$, and both lie in the interval $(\sqrt{D}-Q_j,\sqrt{D})$ by step 1.1; by the uniqueness from step 2.1 they are equal. Thus $P_{j+1}=P_{\mathrm{\ell }-j},Q_j=Q_{\mathrm{\ell }-j},$ completing the induction. Therefore, for $1\le j<\mathrm{\ell }$, $a_j=\frac{P_j+P_{j+1}}{Q_j}=\frac{P_{\mathrm{\ell }-j+1}+P_{\mathrm{\ell }-j}}{Q_{\mathrm{\ell }-j}}=a_{\mathrm{\ell }-j}\mathrm{.}$

Steps 2.1, 3.1, and 4.1 show that the continued-fraction digits from $a_1$ onward repeat with period $\mathrm{\ell }$, that the last digit in one period is $2a_0$, and that the interior digits are palindromic. Hence $\sqrt{D}=[a_0;\overline{a_1,\dots ,a_{\mathrm{\ell }-1},2a_0}],a_j=a_{\mathrm{\ell }-j}(1\le j<\mathrm{\ell }),$ with first returned reduced state $(P_{\mathrm{\ell }},Q_{\mathrm{\ell }})=(a_0,1)$.

Let $\mathrm{\ell }$ be the period length from [F1]. Applying [F2] at $n=\mathrm{\ell }-1$ and using $Q_{\mathrm{\ell }}=1$ gives $p_{\mathrm{\ell }-1}^2-D{q}_{\mathrm{\ell }-1}^2=(-1{)}^{\mathrm{\ell }}\mathrm{.}$

If $\mathrm{\ell }$ is even, step 1.1 already gives a norm-one solution. Since $q_{\mathrm{\ell }-1}>0$ for every convergent denominator and $p_{\mathrm{\ell }-1}^2=D{q}_{\mathrm{\ell }-1}^2+1$, one has $p_{\mathrm{\ell }-1}>0$ and $q_{\mathrm{\ell }-1}>0$, so $(p_{\mathrm{\ell }-1},q_{\mathrm{\ell }-1})$ is a positive nontrivial solution.

If $\mathrm{\ell }$ is odd, step 1.1 gives $p_{\mathrm{\ell }-1}^2-D{q}_{\mathrm{\ell }-1}^2=-1.$ Put $\alpha :=p_{\mathrm{\ell }-1}+q_{\mathrm{\ell }-1}\sqrt{D}\mathrm{.}$ Then $p_{\mathrm{\ell }-1}>0$ and $q_{\mathrm{\ell }-1}>0$ as in step 2.1, and [F3] gives $N_D({\alpha }^2)=N_D(\alpha {)}^2=(-1{)}^2=1.$ Explicitly, ${\alpha }^2=(p_{\mathrm{\ell }-1}^2+D{q}_{\mathrm{\ell }-1}^2)+2p_{\mathrm{\ell }-1}{q}_{\mathrm{\ell }-1}\sqrt{D},$ so ${\alpha }^2$ gives a positive nontrivial integral solution of Pell's equation.

Either step 2.1 or step 3.1 supplies the required positive nontrivial solution.

Applying [F4] at $n=\mathrm{\ell }-1$ and using $Q_{\mathrm{\ell }}=1$ from [F1] gives $p_{\mathrm{\ell }-1}^2-D{q}_{\mathrm{\ell }-1}^2=(-1{)}^{\mathrm{\ell }}\mathrm{.}$ Hence $\mathrm{\ell }$ odd yields a negative-Pell solution at $p_{\mathrm{\ell }-1}\mathrm{/}{q}_{\mathrm{\ell }-1}$, while $\mathrm{\ell }$ even yields a positive norm-one solution there.

Conversely, suppose $x,y>0$ satisfy $x^2-D{y}^2=-1$. Then $0<\sqrt{D}-\frac{x}{y}=\frac{1}{y(x+y\sqrt{D})}\mathrm{.}$ Because $D\ge 2$, one has $x^2=D{y}^2-1\ge y^2$, so $x\ge y$, and therefore $x+y\sqrt{D}>2y\mathrm{.}$ Hence $\mid \sqrt{D}-\frac{x}{y}\mid <\frac{1}{2y^2}\mathrm{.}$ Since $\gcd (x,y)=1$ follows from $x^2-D{y}^2=-1$, fact [F5] shows that $x\mathrm{/}y=p_n\mathrm{/}{q}_n$ for some convergent.

By [F1] and [F3], the returned state at one full period is ${\alpha }_{\mathrm{\ell }}=\frac{\sqrt{D}+P_{\mathrm{\ell }}}{Q_{\mathrm{\ell }}}=\sqrt{D}+a_0\mathrm{.}$ Since $\lfloor {\alpha }_{\mathrm{\ell }}\rfloor =2a_0$, fact [F2] gives ${\alpha }_{\mathrm{\ell }+1}=\frac{1}{{\alpha }_{\mathrm{\ell }}-\lfloor {\alpha }_{\mathrm{\ell }}\rfloor }=\frac{1}{\sqrt{D}-a_0}={\alpha }_1\mathrm{.}$ Thus one full period returns the complete-quotient algorithm to ${\alpha }_1$; because the digits from $a_1$ onward repeat with period $\mathrm{\ell }$, the same computation one period later gives ${\alpha }_{2\mathrm{\ell }}=\sqrt{D}+a_0$, hence $Q_{2\mathrm{\ell }}=1$. Applying [F4] at $n=2\mathrm{\ell }-1$ yields $p_{2\mathrm{\ell }-1}^2-D{q}_{2\mathrm{\ell }-1}^2=(-1{)}^{2\mathrm{\ell }}{Q}_{2\mathrm{\ell }}=1.$ Thus $p_{2\mathrm{\ell }-1}\mathrm{/}{q}_{2\mathrm{\ell }-1}$ is a positive norm-one solution.

For that index $n$, [F4] gives $-1=x^2-D{y}^2=p_n^2-D{q}_n^2=(-1{)}^{n+1}{Q}_{n+1}\mathrm{.}$ Since $Q_{n+1}$ is a positive integer, it follows that $Q_{n+1}=1\text{and}n\text{ is even}\mathrm{.}$ Facts [F2] and [F3] then give ${\alpha }_{n+1}=\sqrt{D}+P_{n+1},{\alpha }_{n+2}=\frac{1}{{\alpha }_{n+1}-\lfloor {\alpha }_{n+1}\rfloor }=\frac{1}{\sqrt{D}-a_0}={\alpha }_1\mathrm{.}$ So the digit block from $a_1$ onward repeats with period $n+1$. Because $\mathrm{\ell }$ is the period length, $\mathrm{\ell }$ divides $n+1$. Since $n+1$ is odd, $\mathrm{\ell }$ must be odd.

Step 2.1 shows that every positive negative-Pell solution comes from a convergent index $n$ with $n$ even and $\mathrm{\ell }\mid (n+1)$, so the first such index is $\mathrm{\ell }-1$. Now let $u,v>0$ satisfy $u^2-D{v}^2=1$. Then $0<\frac{u}{v}-\sqrt{D}=\frac{1}{v(u+v\sqrt{D})}\mathrm{.}$ Because $D\ge 2$, one has $u^2=D{v}^2+1>v^2$, so $u>v$, and therefore $u+v\sqrt{D}>2v\mathrm{.}$ Hence $\mid \sqrt{D}-\frac{u}{v}\mid <\frac{1}{2v^2}\mathrm{.}$ Since $\gcd (u,v)=1$, [F5] shows that $u\mathrm{/}v=p_n\mathrm{/}{q}_n$ for some convergent. Applying [F4] gives $1=u^2-D{v}^2=p_n^2-D{q}_n^2=(-1{)}^{n+1}{Q}_{n+1},$ so $Q_{n+1}=1\text{and}n\text{ is odd}\mathrm{.}$ As in step 2.1, facts [F2] and [F3] then give ${\alpha }_{n+2}={\alpha }_1$, so $\mathrm{\ell }$ divides $n+1$. Therefore the first possible norm-one index is $\mathrm{\ell }-1$ when $\mathrm{\ell }$ is even and $2\mathrm{\ell }-1$ when $\mathrm{\ell }$ is odd. Convergent denominators strictly increase, and for positive solutions of $x^2-D{y}^2=\pm 1$ the value of $x$ is determined by $x^2=D{y}^2\pm 1$, so the first convergent of each type gives the least positive solution. Therefore, when $\mathrm{\ell }$ is odd, $p_{\mathrm{\ell }-1}\mathrm{/}{q}_{\mathrm{\ell }-1}$ is the least positive negative-Pell solution and $p_{2\mathrm{\ell }-1}\mathrm{/}{q}_{2\mathrm{\ell }-1}$ is the least positive norm-one solution, while when $\mathrm{\ell }$ is even, $p_{\mathrm{\ell }-1}\mathrm{/}{q}_{\mathrm{\ell }-1}$ is the least positive norm-one solution.

Because ${\epsilon }_D>1$, the positive powers $\alpha ,\alpha {\epsilon }_D^{-1},\alpha {\epsilon }_D^{-2},\dots$ form a strictly decreasing sequence. By [F2], each term is again an integral norm-one element. If $\beta =u+v\sqrt{D}$ is any integral norm-one element with $\beta >1$, then $0<{\beta }^{-1}=u-v\sqrt{D}<1,$ so $u=\frac{\beta +{\beta }^{-1}}{2},v=\frac{\beta -{\beta }^{-1}}{2\sqrt{D}}>0.$ Thus every term $>1$ in the displayed sequence is again a positive Pell solution. Their $x$-coordinates are positive integers and strictly decrease, because $1<\gamma <\delta$ with $N_D(\gamma )=N_D(\delta )=1$ implies ${\gamma }^{-1}>{\delta }^{-1}>0,\gamma +{\gamma }^{-1}<\delta +{\delta }^{-1},$ hence the corresponding $x$-coordinates satisfy $x(\gamma )<x(\delta )$. Therefore only finitely many indices $j\ge 0$ satisfy $\alpha {\epsilon }_D^{-j}>1$. The set $K:=\{j\in {\mathbb{Z}}_{\ge 0}:\alpha {\epsilon }_D^{-j}\ge 1\}$ is nonempty because $0\in K$, so it has a greatest element $k$. Then $1\le \alpha {\epsilon }_D^{-k},$ and maximality of $k$ gives $\alpha {\epsilon }_D^{-(k+1)}<1.$ Multiplying the last inequality by ${\epsilon }_D$ yields $\alpha {\epsilon }_D^{-k}<{\epsilon }_D,$ so $1\le \alpha {\epsilon }_D^{-k}<{\epsilon }_D\mathrm{.}$

Put $\beta :=\alpha {\epsilon }_D^{-k}\mathrm{.}$ Step 1.1 and [F2] show that $\beta$ is an integral norm-one element with $1\le \beta <{\epsilon }_D$. If $\beta >1$, then step 1.1 shows that $\beta$ is a positive Pell solution with $x$-coordinate smaller than $x_1$, contradicting [F1]. Hence $\beta =1$, so $\alpha ={\epsilon }_D^k\mathrm{.}$ Because $\alpha >1$, the exponent cannot be $0$, so $k\ge 1$.

If also $\alpha ={\epsilon }_D^m={\epsilon }_D^n$ with $m<n$, then multiplying by ${\epsilon }_D^{-m}$ inside the group from [F2] gives $1={\epsilon }_D^{n-m},$ impossible because ${\epsilon }_D>1$. So the exponent of a positive solution is unique.

The element $\alpha$ is nonzero because $N_D(\alpha )=1$. If $\alpha =1$ or $\alpha =-1$, then already $\alpha =\pm {\epsilon }_D^0\mathrm{.}$ Assume now that $\alpha \mathrm{\ne }\pm 1$. If $\alpha >1$, then ${\alpha }^{-1}=1\mathrm{/}\alpha$ satisfies $0<{\alpha }^{-1}<1$. Writing $\alpha =x+y\sqrt{D}$, one gets $x=\frac{\alpha +{\alpha }^{-1}}{2}>0,y=\frac{\alpha -{\alpha }^{-1}}{2\sqrt{D}}>0,$ so $\alpha$ is a positive Pell solution. Hence [F2] gives $\alpha ={\epsilon }_D^k$ for a unique $k\ge 1$. If $0<\alpha <1$, then ${\alpha }^{-1}>1$, so the previous argument shows that ${\alpha }^{-1}$ is a positive Pell solution; [F1] and [F2] therefore give ${\alpha }^{-1}={\epsilon }_D^k$ for a unique $k\ge 1$, hence $\alpha ={\epsilon }_D^{-k}$. If $\alpha <0$, apply the previous positive cases to $-\alpha$, whose norm is still $1$. Therefore $\alpha =\pm {\epsilon }_D^m$ for some integer $m$.

The representation is unique. Indeed, if $\sigma {\epsilon }_D^m=\tau {\epsilon }_D^n,\sigma ,\tau \in \{\pm 1\},$ then the powers ${\epsilon }_D^m$ and ${\epsilon }_D^n$ are positive real numbers, so equality forces $\sigma =\tau$. After cancelling the common sign, suppose for contradiction that $m<n$. Then [F1] gives $1={\epsilon }_D^{n-m}\mathrm{.}$ Multiplying by ${\epsilon }_D$ yields ${\epsilon }_D={\epsilon }_D^{n-m+1}\mathrm{.}$ Both sides are representations of the positive Pell solution ${\epsilon }_D$, so [F2] forces $n-m+1=1$, impossible because $m<n$. The case $n<m$ is symmetric. Hence $m=n$.