Bossy Lobster

A blog by Danny Hermes; musing on tech, mathematics, etc.

Edit on GitHub

Continued fraction expansions of irrational square roots

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 D\sqrt{D} is periodic whenever DD 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.


An irrational root α\alpha of a quadratic equation with integer coefficients is called reduced if α>1\alpha > 1 and its conjugate α~\widetilde{\alpha} satisfies 1<α~<0-1 < \widetilde{\alpha} < 0. \blacksquare

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

α=D+PQ\alpha = \frac{\sqrt{D} + P}{Q}

where D,P,QZD, P, Q \in \mathbf{Z} and D,Q>0D, Q > 0. It is also possible (though not required) to ensure that QQ divides DP2D - 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

α=2+74\alpha = \frac{2 + \sqrt{7}}{4}

is reduced but 44 does not divide 7227 - 2^2. However, if we write this as 8+11216,\frac{8 + \sqrt{112}}{16}, we have our desired condition.


We say a reduced quadratic irrational α\alpha is associated to DD if we can write

α=P+DQ\alpha = \frac{P + \sqrt{D}}{Q}

and QQ divides DP2D - P^2. \blacksquare

Lemma 1:

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

α=α+1α,\alpha = \lfloor \alpha \rfloor + \frac{1}{\alpha'},

the resulting quadratic irrational α\alpha' is reduced and associated to DD as well. (This is what one does during continued fraction expansion, and as I did with 2\sqrt{2} during my last post.)



α=D+PQ\alpha = \frac{\sqrt{D} + P}{Q}

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

1α=D(QXP)Q.\frac{1}{\alpha'} = \frac{\sqrt{D} - (QX - P)}{Q}.
  • Since D\sqrt{D} is irrational, we must have 1α>0\frac{1}{\alpha'} > 0 and since 1α\frac{1}{\alpha'} is the fractional part we know

    0<1α<1α>1.0 < \frac{1}{\alpha'} < 1 \Rightarrow\alpha' > 1.

  • Transforming

    α=QD(QXP)D+(QXP)D+(QXP)=D+(QXP)1Q(D(QXP)2),\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=QXPP' = QX - P and Q=1Q(D(QXP)2)Q' = \frac{1}{Q}\left(D - (QX - P)^2\right) and need to show QZQ' \in \mathbf{Z}. But D(QXP)2DP2modQD - (QX - P)^2 \equiv D - P^2 \bmod{Q} and since α\alpha is associated to D,D, QQ must divide this quantity, hence QQ' is an integer.

  • Since X=D+PQX = \lfloor\frac{\sqrt{D} + P}{Q}\rfloor is an integer and α\alpha is irrational, we know X<D+PQX < \frac{\sqrt{D} + P}{Q} hence P=QXP<DP' = QX - P < \sqrt{D} forcing α~<0\widetilde{\alpha}' < 0.

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

    α~=PDQ<0X1Q<D+(QXP)Q(D(QXP))<D(QXP)2α~=D(QXP)1Q(D(QXP)2)<1\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 α~>1\widetilde{\alpha}' > -1 and α\alpha' is reduced.

  • Since Q=1Q(D(P)2),Q' = \frac{1}{Q}\left(D - (P')^2\right), we know

    D(P)2QQ0modQD - (P')^2 \equiv Q Q' \equiv 0 \bmod{Q'}

    hence α\alpha' is associated to DD.

Thus α\alpha' is both reduced and associated to DD. \blacksquare

Lemma 2:

There are finitely many reduced quadratic irrationals associated to a fixed DD.


As above write an arbitrary reduced irrational as α=D+PQ\alpha = \frac{\sqrt{D} + P}{Q}. Since α>1\alpha > 1 and α~>1,\widetilde{\alpha} > -1, we know α+α~=2PQ>0\alpha + \widetilde{\alpha} = \frac{2P}{Q} > 0 hence with the assumption Q>0Q > 0 we have P>0P > 0. Since α~<0\widetilde{\alpha} < 0 we also have P<DP < \sqrt{D}. Also, since α>1\alpha > 1 by assumption we have Q<P+D<2DQ < P + \sqrt{D} < 2\sqrt{D} thus there are finitely many choices for both PP and Q,Q, forcing finitely many reduced quadratic irrationals associated to a fixed DD; the number of choices is strictly bounded above by 2D2D. \blacksquare


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


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

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

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

Since 1α0\frac{1}{\alpha_0} is the fractional part of the irrational D,\sqrt{D}, we have

0<1α0<1α0>1.0 < \frac{1}{\alpha_0} < 1 \Rightarrow \alpha_0 > 1.

By simple algebra, we have

α0=a0+DDa02,α0~=a0DDa02.\alpha_0 = \frac{a_0 + \sqrt{D}}{D - a_0^2}, \qquad \widetilde{\alpha_0} = \frac{a_0 - \sqrt{D}}{D - a_0^2}.

Since a0a_0 is the floor, we know a0D<0α0~<0a_0 - \sqrt{D} < 0 \Rightarrow\widetilde{\alpha_0} < 0. Since DZD>1D \in \mathbf{Z} \Rightarrow \sqrt{D} > 1 and D>a0,\sqrt{D} > a_0, we have

1<D+a0Da0<Da021 < \sqrt{D} + a_0 \Rightarrow\sqrt{D} - a_0 < D - a_0^2


a0D>(Da02)α0~>1.a_0 - \sqrt{D} > -(D - a_0^2) \Rightarrow \widetilde{\alpha_0} > -1.

Thus α0\alpha_0 is a reduced quadratic irrational. Since P0=a0P_0 = a_0 and Q0=Da02=DP02,Q_0 = D - a_0^2 = D - P_0^2, Q0Q_0 clearly divides DP02D - P_0^2 so α0\alpha_0 is associated to DD as well.

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

D=a0+1a1+1a2+\sqrt{D} = a_0 + \cfrac{1}{a_1 +\cfrac{1}{a_2 +\ddots}}

to be periodic.\blacksquare


I posted this on ProofWiki.