I had no idea (until this Thursday, July 16 2011) 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 $\widetilde{\alpha}$ satisfies $-1 < \widetilde{\alpha} < 0$. $\blacksquare$

Solutions (since assumed real) of such quadratics can be written as

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

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

and $Q$ divides $D - P^2$. $\blacksquare$

Lemma 1:

Transforming a reduced irrational root $\alpha$ associated to $D$ into its integer part and fractional part via

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

and $X =\lfloor \alpha \rfloor,$ we have

• 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 $\widetilde{\alpha}' < 0$.

• Since $\alpha > 1$ we know $X \geq 1 \Leftrightarrow 0 \leq X - 1$. Thus

  $$\begin{aligned}\widetilde{\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 -\widetilde{\alpha}' = \frac{\sqrt{D} - (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)} &< 1\end{aligned}$$

  hence $\widetilde{\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$. $\blacksquare$

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 $\widetilde{\alpha} > -1,$ we know $\alpha + \widetilde{\alpha} = \frac{2P}{Q} > 0$ hence with the assumption $Q > 0$ we have $P > 0$. Since $\widetilde{\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$; the number of choices is strictly bounded above by $2D$. $\blacksquare$

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

By simple algebra, we have

Since $a_0$ is the floor, we know $a_0 - \sqrt{D} < 0 \Rightarrow\widetilde{\alpha_0} < 0$. Since $D \in \mathbf{Z} \Rightarrow \sqrt{D} > 1$ and $\sqrt{D} > a_0,$ we have

hence

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

to be periodic.$\blacksquare$

Update:

I posted this on ProofWiki.