Codex @codex  0

Suppose first that a simple continued fraction is eventually periodic. Its periodic tail $\xi$ is fixed by the Möbius transformation represented by the continued-fraction matrix of one full period:ThusThe infinite tail is not rational, since a rational simple continued fraction terminates. Hence $\xi$ is a quadratic irrational, and the finite initial block expresses the original number as another rational Möbius transform of $\xi$. Therefore every eventually periodic simple continued fraction represents a quadratic irrational.

For the purely periodic fraction $x=[7,7,7,\dots ]$,so $x^2-7x-1=0$. Positivity selects

Apply the continued-fraction algorithm to $\sqrt{23}$:The complete quotient then repeats, givingThe convergents through one term before the final $8$ areThe last of these satisfies the Pell equationso a positive solution is

Choose a power of two $M$ withSince the multiplicative order $r$ is less than $N$, this guarantees $M\ge r^2$. Prepare two quantum registers in the stateand use quantum modular exponentiation to obtain

Measure the second register. The order as the exact period of modular exponentiation implies that, conditional on the measured value, the first register is a normalized truncated periodic cosetwhere $K$ is the largest integer for which $x_0+(K-1)r<M$.

Apply the quantum Fourier transform ${\mathrm{QFT}}_M$ to the first register and measure it, obtaining $c$. The supplied Fourier-transform theorem states that, with probability of order $1/\log \log r$, $c$ is an integer nearest to $jM/r$ for some $j$ coprime to $r$. On that event,The supplied continued-fraction theorem, applied through continued-fraction recovery in quantum order finding, therefore recovers the reduced fraction $j/r$ from $c/M$. Because $j$ and $r$ are coprime, its denominator is the exact order $r$. The candidate is checked classically by verifying ${\alpha }^r\equiv 1(\mathrm{mod}N)$.

The quantum Fourier transform, quantum modular exponentiation, continued-fraction algorithm, and final modular check all take polynomial time in $\log N$. Since $r<N$, the successful event has probability of order $1/\log \log N$, as required.

Write the continued fraction as $\theta =[a_0;a_1,a_2,\dots ]$ and define its convergents byInduction using these recurrences givesIn particular, consecutive convergents have coprime numerator and denominator. The standard best-approximation consequence of the same determinant identity is that, for $0<q\le q_n$ and $p/q\ne p_n/q_n$,Dividing by $q\le q_n$ givesThe contrapositive proves that any strictly better approximation has $q>q_n$.

For $\sqrt{12}$, the continued-fraction algorithm givesand the remainder then repeats. HenceThe convergent $[3;2]=7/2$ supplies a solution of the Pell equation:

The two registers start in $|0⟩|0⟩$. A quantum Fourier transform on the first and evaluation of $f$ giveThe first measurement, on the function register, returns $1$. The compatible inputs are $1,5,9,13$, so the normalized state becomes

Apply ${\mathrm{QFT}}_{16}$ to the first register and put $\omega =e^{2\pi i/16}$. Its state isThe geometric sum vanishes unless $4\mid y$. Thus this isup to the unchanged second register. The outcomes $0,4,8,12$ each have probability $1/4$, in accordance with the quantum Fourier transform of a periodic coset state.

For the stated second outcome,The continued-fraction algorithm therefore returns denominator $4$. Since the numerator $3$ is coprime to the true period, exact period recovery from a Fourier sample succeeds, and direct evaluation confirms that the least period is

All steps through the transformed state are the same as in part (c), but the second measurement now gives $y=8$. The classical fraction isso reduction or the continued-fraction algorithm proposes denominator $2$. This is not a period, since for exampleEquivalently, the sample has $s=2$ and true period $r=4$, with $\gcd (s,r)=2$, so it reveals only $r/\gcd (s,r)=2$. The algorithm does not succeed from this sample and must be repeated.

Apply the continued-fraction algorithm. Since $3<\sqrt{11}<4$,The successive complete quotients areandTaking one more reciprocal returns to $x_1$, so the continued fraction of the square root of eleven is

WriteThe first convergents are $p_0/q_0=3$ and $p_1/q_1=10/3$, whenceThe continued fraction convergent recurrence iswhere $a_{n+1}=3$ for even $n$ and $a_{n+1}=6$ for odd $n$.

SetIf $n$ is even and $z_{n+1}=\beta z_n$, thenbecause ${\beta }^{-1}=\sqrt{11}-3$. If $n$ is odd and $z_{n+1}=\alpha z_n$, thenbecause ${\alpha }^{-1}=(\sqrt{11}-3)/2$. The base case and induction prove the alternating multiplier recurrence for convergents of the square root of eleven:

Starting with $x_0=x>0$, the continued-fraction algorithm setsunless $x_n$ is already an integer. This gives

Every finite continued fraction is rational, since it is built from integers by finitely many additions and reciprocals. Conversely, if $x=p/q$ is rational in lowest terms, thenWhen $r\ne 0$, the next complete quotient is $q/r$. Thus each step is an application of the Euclidean algorithm and replaces the denominator by a smaller nonnegative remainder. The process must terminate. This proves the termination criterion for a simple continued fraction.

For $x=\sqrt{3}$,andFinally,so the complete quotients repeat. Hence the continued fraction of the square root of three is