1
$\begingroup$

I came across the Wiki-proof sites and I wanted to find out a proof that the continued fraction of $\sqrt{N}$, where $N$ is a positive integer, not being a perfect square, has the form $[a,\overline {r_1,r_2,\cdots,r_n,2a}]$

In Wiki-proof, I only found the proof that the continued fraction expansion must eventually become periodic. But two things are missing :

How can I prove that the period starts immediately after the first entry $a=\lfloor\sqrt{N}\rfloor$ ?

How can I prove that the period ends with the entry $2a$ and that the corresponding convergent $\frac{p}{q}$ is the fundamental solution of the Pell-equation $p^2-Nq^2=\pm1$ ?

Please answer with a proof directly written down and not just with a link!

$\endgroup$
2
$\begingroup$

I will answer the first two parts of your question, i.e., $\sqrt N$ has a continued fraction of the form $[\lfloor \sqrt N \rfloor; \overline{a_1, a_2, \ldots, a_n, 2\lfloor \sqrt N \rfloor}]$.

We will assume that we already know that a quadratic irrational number has a periodic continued fraction.

First, we need the following theorem of Galois, the proof of which I take from Theorem 7.20 in I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991:

Theorem of Galois. The continued fraction of the quadratic irrational number $\xi$ is purely periodic if $\xi > 1$ and $-1 < \xi' < 0$, where $\xi'$ is the conjugate of $\xi$.

Proof: Recall the inductive definition for expanding $\xi = \xi_0$ into a continued fraction: $$a_i = \lfloor \xi_i \rfloor, \qquad \xi_{i+1} = \frac{1}{\xi_i - a_i}.$$

Invert and take conjugates of the latter equation to obtain $$\frac{1}{\xi'_{i+1}} = \xi'_i - a_i.$$ Now $a_i \ge 1$. Hence, if $\xi'_i < 0$, then $1/\xi'_{i+1} < -1$, and we have $-1 < \xi'_{i+1} < 0$. Because $-1 < \xi'_0 < 0$ by hypothesis, we see by mathematical induction that $-1 < \xi'_i < 0$ is true for all $i$. Then by the previous equation, $$0 < -\frac{1}{\xi'_{i+1}} - a_i < 1, \qquad a_i= \left\lfloor -\frac{1}{\xi'_{i+1}} \right\rfloor.$$ Because $\xi$ is a quadratic irrational number, it has a periodic continued fraction, so $\xi_j = \xi_k$ for some integers $j$ and $k$ with $0 < j < k$. Then we also have $\xi'_j = \xi'_k$, and

\begin{align} a_{j-1} & = \left\lfloor -\frac{1}{\xi'_j} \right\rfloor = \left\lfloor -\frac{1}{\xi'_k}\right\rfloor = a_{k-1}\\ \xi_{j-1} & = a_{j-1} + \frac{1}{\xi_j} = a_{k-1} + \frac{1}{\xi_k} = \xi_{k-1}. \end{align} Hence, $\xi_j = \xi_k$ implies $\xi_{j-1} = \xi_{k-1}$. A $j$-fold iteration of that implication gives $\xi_0 = \xi_{k-j}$, and we have $\xi = \xi_0 = [\overline{a_0; a_1, \ldots, a_{k-j-1}}]$, which completes the proof of the theorem of Galois.

The rest of the answer comes from Proposition 32 of "Continued Fractions, Pell's Equation, and Transcendental Numbers" by Jeremy Booher:

Because $$\frac{1}{\sqrt N - \lfloor \sqrt N \rfloor} > 1 \qquad \text{and} \qquad -1 < \frac{1}{-\sqrt N - \lfloor \sqrt N \rfloor} < 0,$$ the continued fraction of $\upsilon_1 = 1/(\sqrt N - \lfloor \sqrt N \rfloor)$ is purely periodic by the theorem of Galois, so $\upsilon_0 = \sqrt N$ has the form $[\lfloor \sqrt N \rfloor; \overline{a_1, a_2, \ldots, a_n, a_{n+1}}]$ where $n+1$ denotes the length of the shortest period in that expansion. (I am using the notation $\upsilon_0$ and $\upsilon_1$ because $\upsilon_0 = \sqrt N$ and $\upsilon_1 = 1/(\sqrt N - \lfloor \sqrt N \rfloor)$ are related by the inductive definition above for expanding $\upsilon_0$ into a continued fraction.) Also, $\sqrt N + \lfloor \sqrt N \rfloor = [2\lfloor \sqrt N \rfloor; \overline{a_1, a_2, \ldots, a_n, a_{n+1}}]$. Moreover, $$\sqrt N + \lfloor \sqrt N \rfloor > 1, \qquad \text{and} \qquad -1 < \lfloor \sqrt N \rfloor - \sqrt N < 0,$$ so the continued fraction of $\sqrt N + \lfloor \sqrt N \rfloor$ is purely periodic by the theorem of Galois, which means that the period (of length $n + 1$) starts at the beginning of the expansion. We therefore have more ways to express the continued fraction for $\sqrt N + \lfloor \sqrt N \rfloor$: \begin{align} \sqrt N + \lfloor \sqrt N \rfloor & = [2\lfloor \sqrt N \rfloor; \overline{a_1, a_2, \ldots, a_n, a_{n+1}}]\\ & = [\overline{2\lfloor \sqrt N \rfloor; a_1, a_2, \ldots, a_n}, a_{n+1}, \ldots]\\ & = [\overline{2\lfloor \sqrt N \rfloor; a_1, a_2, \ldots, a_n}]. \end{align} We see from the last two continued fractions that $a_{n+1}$ begins the second period, so $a_{n+1}$ has the same value as the first integer of the first period, i.e., $a_{n+1} = 2\lfloor \sqrt N \rfloor$. Substituting for $a_{n+1}$ in the continued fraction for $\sqrt N$ concludes the proof: $$\sqrt N = [\lfloor \sqrt N \rfloor; \overline{a_1, a_2, \ldots, a_n, 2\lfloor \sqrt N \rfloor}].$$

$\endgroup$
  • $\begingroup$ Nice answer (+1) $\endgroup$ – Peter May 30 '17 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.