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 is periodic whenever 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 of a quadratic equation with integer coefficients is called reduced if and its conjugate satisfies .
Solutions (since assumed real) of such quadratics can be written as
where and . It is also possible (though not required) to ensure that divides . 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 does not divide . However, if we write this as we have our desired condition.
We say a reduced quadratic irrational is associated to if we can write
and divides .
Transforming a reduced irrational root associated to into its integer part and fractional part via
the resulting quadratic irrational is reduced and associated to as well. (This is what one does during continued fraction expansion, and as I did with during my last post.)
and we have
Since is irrational, we must have and since is the fractional part we know
we have and and need to show . But and since is associated to must divide this quantity, hence is an integer.
Since is an integer and is irrational, we know hence forcing .
Since we know . Thus
hence and is reduced.
Since we know
hence is associated to .
Thus is both reduced and associated to .
There are finitely many reduced quadratic irrationals associated to a fixed .
As above write an arbitrary reduced irrational as . Since and we know hence with the assumption we have . Since we also have . Also, since by assumption we have thus there are finitely many choices for both and forcing finitely many reduced quadratic irrationals associated to a fixed ; the number of choices is strictly bounded above by .
The continued fraction expansion of is periodic whenever is not a perfect square.
We'll use Lemma 1 to establish a series of reduced quadratic irrationals associated to and then use Lemma 2 to assert this series must repeat (hence be periodic) due to the finite number of such irrationals.
Write and . From here, we will prove
- is a reduced quadratic irrational associated to .
- By defining and is also a reduced quadratic irrational associated to (assuming all up until are as well).
Since is the fractional part of the irrational we have
By simple algebra, we have
Since is the floor, we know . Since and we have
Thus is a reduced quadratic irrational. Since and clearly divides so is associated to as well.
Following the recurrence defined, since each is a reduced quadratic irrational, each . Also, by Lemma 1, each is reduced and associated to since is. By Lemma 2, we only have finitely many choices for these, hence there must be some smallest for which . Since is determined completely by we will then have for all hence the are periodic. Similarly, as the for are determined completely by the must be periodic as well, forcing the continued fraction expansion
to be periodic.
I posted this on ProofWiki.