Continued fraction expansions of irrational square roots

I had no idea (until this Thursday, July 16) that I had never seen a proof of the fact that the continued fraction expansion of $\sqrt{D}$ is periodic whenever $D$ is not a perfect square. But have no fear, I found out about something called a reduced quadratic irrational and now have a proof. Here we go.

Definition: An irrational root $\alpha$ of a quadratic equation with integer coefficients is called reduced if $\alpha > 1$ and its conjugate $\tilde{\alpha}$ satisfies $-1 < \tilde{\alpha} < 0$. $\Box$

Solutions (since assumed real) of such quadratics can be written as  $$\alpha = \frac{\sqrt{D} + P}{Q}$$ where $D, P, Q \in \mathbf{Z}$ and $D, Q > 0$. It is also possible (though not required) to ensure that $Q$ divides $D - P^2$. This is actually a necessary assumption for some of the stuff I do, is mentioned here and generally frustrated the heck out of me, so that. As an example for some enlightenment, notice $$\alpha = \frac{2 + \sqrt{7}}{4}$$ is reduced but $4$ does not divide $7 - 2^2$. However, if we write this as $\frac{8 + \sqrt{112}}{16}$, we have our desired condition.

Definition: We say a reduced quadratic irrational $\alpha$ is associated to $D$ if we can write $$\alpha = \frac{P + \sqrt{D}}{Q}$$ and $Q$ divides $D - P^2$. $\Box$


Lemma 1: Transforming a reduced irrational root $\alpha$ associated to $D$ into its integer part and fractional part via $$\alpha = \lfloor \alpha \rfloor + \frac{1}{\alpha'},$$ the resulting quadratic irrational $\alpha'$ is reduced and associated to $D$ as well. (This is what one does during continued fraction expansion, and as I did with $\sqrt{2}$ during my last post.)

Proof: Letting $$\alpha = \frac{\sqrt{D} + P}{Q}$$ and $X = \lfloor \alpha \rfloor$, we have $$\frac{1}{\alpha'} = \frac{\sqrt{D} - (QX - P)}{Q}.$$

• Since $\sqrt{D}$ is irrational, we must have $\frac{1}{\alpha'} > 0$ and since $\frac{1}{\alpha'}$ is the fractional part we know $$0 < \frac{1}{\alpha'} < 1 \Rightarrow \alpha' > 1.$$  
• Transforming $$\alpha' = \frac{Q}{\sqrt{D} - (QX - P)} \cdot \frac{\sqrt{D} + (QX - P)}{\sqrt{D} + (QX - P)} = \frac{\sqrt{D} + (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)},$$ we have $P' = QX - P$ and $Q' = \frac{1}{Q}\left(D - (QX - P)^2\right)$ and need to show $Q' \in \mathbf{Z}$. But $D - (QX - P)^2 \equiv D - P^2 \bmod{Q}$ and since $\alpha$ is associated to $D$, $Q$ must divide this quantity, hence $Q'$ is an integer.
• Since $X = \lfloor\frac{\sqrt{D} + P}{Q}\rfloor$ is an integer and $\alpha$ is irrational, we know $X < \frac{\sqrt{D} + P}{Q}$ hence $P' = QX - P < \sqrt{D}$ forcing $\tilde{\alpha}' < 0$.
• Since $\alpha > 1$ we know $X \geq 1 \Leftrightarrow 0 \leq X - 1$. Thus $$\begin{align*}\tilde{\alpha} = \frac{P - \sqrt{D}}{Q} &< 0 \leq X - 1 \\ \Rightarrow Q &< \sqrt{D} + (QX - P) \\ \Rightarrow Q(\sqrt{D} - (QX - P)) &< D - (QX - P)^2 \\ \Rightarrow -\tilde{\alpha}' = \frac{\sqrt{D} - (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)} &< 1 \end{align*}$$ hence $\tilde{\alpha}' > -1$ and $\alpha'$ is reduced.
• Since $Q' = \frac{1}{Q}\left(D - (P')^2\right)$, we know $$D - (P')^2 \equiv Q Q' \equiv 0 \bmod{Q'}$$ hence $\alpha'$ is associated to $D$.

Thus $\alpha'$ is both reduced and associated to $D$. $\Box$


Lemma 2: There are finitely many reduced quadratic irrationals associated to a fixed $D$.

Proof: As above write an arbitrary reduced irrational as $\alpha = \frac{\sqrt{D} + P}{Q}$.  Since $\alpha > 1$ and $\tilde{\alpha} > -1$, we know $\alpha + \tilde{\alpha} = \frac{2P}{Q} > 0$ hence with the assumption $Q > 0$ we have $P > 0$. Since $\tilde{\alpha} < 0$ we also have $P < \sqrt{D}$. Also, since $\alpha > 1$ by assumption we have $Q < P + \sqrt{D} < 2\sqrt{D}$ thus there are finitely many choices for both $P$ and $Q$, forcing finitely many reduced quadratic irrationals associated to a fixed $D$ (this amount is strictly bounded above by $2D$). $\Box$

Claim: The continued fraction expansion of $\sqrt{D}$ is periodic whenever $D$ is not a perfect square.

Proof: We'll use Lemma 1 to establish a series of reduced quadratic irrationals associated to $D$ and then use Lemma 2 to assert this series must repeat (hence be periodic) due to the finite number of such irrationals.

Write $a_0 = \lfloor \sqrt{D} \rfloor$ and $\sqrt{D} = a_0 + \frac{1}{\alpha_0}$. From here, we will prove

• $\alpha_0$ is a reduced quadratic irrational associated to $D$.
• By defining $a_{i+1} = \lfloor \alpha_i \rfloor$ and $\alpha_i = a_{i + 1} + \frac{1}{\alpha_{i + 1}}$, $\alpha_{i + 1}$ is also a reduced quadratic irrational associated to $D$ (assuming all $\alpha$ up until $i$ are as well).

Since $\frac{1}{\alpha_0}$ is the fractional part of the irrational $\sqrt{D}$, we have  $$0 < \frac{1}{\alpha_0} < 1 \Rightarrow \alpha_0 > 1.$$  By simple algebra, we have $$\alpha_0 = \frac{a_0 + \sqrt{D}}{D - a_0^2}, \qquad \tilde{\alpha_0} = \frac{a_0 - \sqrt{D}}{D - a_0^2}.$$ Since $a_0$ is the floor, we know $a_0 - \sqrt{D} < 0 \Rightarrow \tilde{\alpha_0} < 0$. Since $D \in \mathbf{Z} \Rightarrow \sqrt{D} > 1$ and $\sqrt{D} > a_0$, we have $$1 < \sqrt{D} + a_0 \Rightarrow \sqrt{D} - a_0 < D - a_0^2 \Rightarrow a_0 - \sqrt{D} > -(D - a_0^2) \Rightarrow \tilde{\alpha_0} > -1.$$ Thus $\alpha_0$ is a reduced quadratic irrational. Since $P_0 = a_0$ and $Q_0 = D - a_0^2 = D - P_0^2$, $Q_0$ clearly divides $D - P_0^2$ so $\alpha_0$ is associated to $D$ as well.

Following the recurrence defined, since each $\alpha_i$ is a reduced quadratic irrational, each $a_i \geq 1$. Also, by Lemma 1, each $\alpha_{i + 1}$ is reduced and associated to $D$ since $\alpha_0$ is. By Lemma 2, we only have finitely many choices for these, hence there must be some smallest $k$ for which $\alpha_k = \alpha_0$. Since $\alpha_{i + 1}$ is determined completely by $\alpha_i$ we will then have $\alpha_{k + j} = \alpha_j$ for all $j > 0$, hence the $\alpha_i$ are periodic. Similarly, as the $a_i$ for $i > 0$ are determined completely by $\alpha_{i - 1}$, the $a_i$ must be periodic as well, forcing the continued fraction expansion $$\sqrt{D} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}$$ to be periodic.$\Box$

Update: I posted this on
About Bossy Lobster