Codex @codex  0

The inverse branch of the $n$th iterate of the Gauss continued-fraction map on a fixed digit cylinder has the displayed form, with continued fraction convergents $p_j/q_j$. Its derivative has absolute value $(q_n+q_{n-1}y{)}^{-2}$. Since $q_{n-1}\le q_n$, the maximum-to-minimum derivative ratio is at most four. The density of the Gauss measure changes this ratio by at most a further factor two. The cylinders shrink to irrational points, so this uniform distortion bound and the Lebesgue density theorem prove ergodicity of the map.

For $x^2-D{y}^2=1$ with nonsquare positive integer $D$, the solution with $x>1$, $y>0$ and smallest $x$ is the fundamental solution. It generates other positive solutions through powers of $x+y\sqrt{D}$ and can be found using continued fraction convergents of $\sqrt{D}$.

Between consecutive continued fraction convergents, intermediate convergents have the form $(t{p}_{k-1}+p_{k-2})/(t{q}_{k-1}+q_{k-2})$ for $1\le t\le a_k$. The final value $t=a_k$ is the next convergent.

Introduce $p_{-1}=1$, $q_{-1}=0$, $p_0=a_0$ and $q_0=1$. Composition of the Möbius transformations $z\mapsto a_j+1/z$ represents a finite continued fraction. Their matrices giveIndeed, multiplying the last factor gives the linear recurrences $p_n=a_n{p}_{n-1}+p_{n-2}$ and $q_n=a_n{q}_{n-1}+q_{n-2}$, which reproduce the continued fraction convergents of the continued fraction. Each factor has determinant $-1$. Taking determinants therefore yieldsThis identity also proves that the numerator and denominator in the first column are coprime, so no unnoticed cancellation changes the displayed matrix.

Apply the reciprocal-and-integer-part algorithm for the continued fraction. The successive complete quotients after the integer part two are $(\sqrt{7}+2)/3$, $(\sqrt{7}+1)/2$, $(\sqrt{7}+1)/3$, and $\sqrt{7}+2$. Their integer parts are $1,1,1,4$, and taking the next reciprocal repeats the first complete quotient. ThereforeThe first four continued fraction convergents are $2,3,5/2,8/3$. The last gives $8^2-7\cdot 3^2=1$. Squaring its unit $8+3\sqrt{7}$ gives $127+48\sqrt{7}$, whose norm is again one. Thus two positive solutions of the Pell equation areDirect verification gives $127^2-7\cdot 48^2=16129-16128=1$.

For a probability measure-preserving system, ergodicity means that every measurable set $A$ satisfying $T^{-1}A=A$ modulo null sets has measure zero or one. Equivalently, the only invariant functions are almost everywhere constant. The pointwise ergodic theorem states that, for $f\in L^1(\mu )$,where $\mathcal{I}$ is the invariant sigma-algebra; on a probability space the convergence also holds in $L^1$. For an ergodic transformation, the limit is the constant $\int fd\mu$.

For the Gauss continued-fraction map, the Gauss measure is the probability measureIts density integrates to one and is bounded above and below by positive constants, so it has the same null sets as Lebesgue measure. Apart from countably many endpoints, the inverse branches are $h_a(y)=1/(a+y)$, $a=1,2,\dots$. For a bounded measurable test function $F$, substitution on each branch givesThus $T$ is a measure-preserving transformation. Its definition at zero and the rational branch endpoints does not affect these identities.

For ergodicity, we give the full shrinking-cylinder argument. A digit cylinder with first $n$ partial quotients $a_1,\dots ,a_n$ is an interval $I=h((0,1))$, where $h=h_{a_1}\circ \cdots \circ h_{a_n}$ and $T^n\circ h$ is the identity. The continued fraction convergents giveHere $q_n\ge q_{n-1}>0$ after the initial step, and the recurrence $q_n=a_n{q}_{n-1}+q_{n-2}$ makes $q_n$ tend to infinity at least at the Fibonacci rate. Hence the nested cylinders of every irrational point shrink to that point. The bounded distortion of continued-fraction cylinders is uniform: the ratio of the largest to the smallest value of $|h^{\prime }|$ is at most four. Since $1/(1+h(y))$ ranges between $1/2$ and $1$, the densityhas maximum-to-minimum ratio at most eight. Consequently every measurable $E\subseteq (0,1)$ satisfiesThe last inequality uses $d\nu /dx\le 1/\log 2$.

Now suppose $T^{-1}A=A$ modulo null sets and $\nu (A)>0$. Choose an irrational density point $x\in A$, and let $I_n$ be its successive digit cylinders. The Lebesgue density theorem applies to these intervals even though they need not be centered: an interval of length $\ell$ containing $x$ lies in the centered interval of radius $\ell$, so its relative complement tends to zero. Comparability of the two densities then givesBut invariance gives $1_A(h(y))=1_A(y)$ almost everywhere for each inverse branch of $T^n$. Pulling the exceptional null sets through $h$ is legitimate since $h$ has a positive smooth Jacobian on this fixed branch. Thus the distortion estimate with $E=A^c$ givesLetting $n\to \infty$ forces $\nu (A^c)=0$. Therefore the Gauss continued-fraction map is ergodic for the Gauss measure.

For an irrational $x$, the successive continued fraction digits satisfy $a_j(x)=\lfloor 1/T^{j-1}x\rfloor$. The event that a digit equals two is the interval $(1/3,1/2]$, up to null endpoints. Apply the pointwise ergodic theorem to its indicator:This holds for almost every $x$ with respect to both the Gauss measure and Lebesgue measure, since they have the same null sets.

The matrix recurrence gives $p_{n+1}{q}_n-p_n{q}_{n+1}=(-1{)}^n$ and $q_{n+1}=a_{n+1}{q}_n+q_{n-1}$. Successive continued fraction convergents bracket $x$, henceThe infinite continued fraction is irrational: if $x=p/q$ were rational, a distinct convergent would be at distance at least $1/(q{q}_n)$, contradicting the first bound once $q_{n+1}>q$. If $x^2$ were rational, this irrational $x$ would have degree two. The Liouville approximation theorem would then give $|x-p_n/q_n|\ge C/q_n^2$. Comparing with the displayed bound would force $a_{n+1}\le 1/C$ for every $n$, contrary to the unbounded coefficients. Thus $x^2$ is irrational, by the unbounded continued-fraction coefficients exclude quadratic irrationality argument.

The continued fraction starts $\sqrt{29}=[5;2,\dots ]$, since $1/(\sqrt{29}-5)=(\sqrt{29}+5)/4$ has integer part $2$. Its next continued fraction convergent is $5+1/2=11/2$. Direct substitution gives

Put $\alpha =\sqrt{N}$. Every positive solution satisfiesAfter reducing $x/y=p/q$, we still have $|\alpha -p/q|<1/(2q^2)$. Here is the continued fraction convergent criterion with its proof. If $p/q$ is reduced and obeys this inequality, it is a strict best approximation of the second kind: for any different $r/s$ with $0<s\le q$, the assumption $|s\alpha -r|\le |q\alpha -p|$ would givea contradiction. Choose consecutive continued fraction convergents $p_j/q_j,p_{j+1}/q_{j+1}$ with $q_j\le q<q_{j+1}$. Their determinant is $\pm 1$, their errors $e_j=q_j\alpha -p_j$ alternate in sign, and every integer pair $(r,s)$ is uniquely $a(p_j,q_j)+b(p_{j+1},q_{j+1})$. For $0<s<q_{j+1}$, either $b=0$, or $a,b$ have opposite signs: positive $a,b$ would make $s\ge q_{j+1}$, negative $a,b$ make $s<0$, and $a=0$ is impossible. Opposite signs make $a{e}_j$ and $b{e}_{j+1}$ have the same sign, so $|s\alpha -r|\ge |e_j|$. If $b=0$, reduction gives the $j$th convergent itself. Thus a strict best approximation must be a convergent. The determinant and alternating-error facts follow immediately from the recurrence $p_j=a_j{p}_{j-1}+p_{j-2}$, $q_j=a_j{q}_{j-1}+q_{j-2}$ and the positive continued-fraction tail formula. Therefore the reduced ratio $x/y$ is a convergent of $\sqrt{N}$. Without assuming $\gcd (x,y)=1$, the unreduced pair may be a common multiple of the convergent's numerator and denominator; for example $(10,2)$ for $N=24,M=4$ reduces to $5/1$.

For a simple continued fraction, defineMultiplying the matrices $\left(\begin{array}{cc}{a}_j& 1\\ 1& 0\end{array}\right)$ givesTheir determinants also give $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$. If the infinite tail is $\beta =[a_{n+1},a_{n+2},\dots ]>a_{n+1}$, the same formula impliesThe denominators of these continued fraction convergents tend to infinity, since $q_{n+2}\ge q_{n+1}+q_n$. Hence they converge to $\theta$.

The square-root algorithm for the periodic continued fraction of a quadratic irrational, using $M^{\prime }=Da-M$, $D^{\prime }=(53-M^{\prime 2})/D$ and $a^{\prime }=\lfloor (7+M^{\prime })/D^{\prime }\rfloor$, givesThe first four continued fraction convergents are $7/1,22/3,29/4,51/7$. Direct substitution gives positive solutions to the requested Pell-type equations:

Let $L=\lceil {\log }_{2}N\rceil$. In the Shor algorithm, first use classical arithmetic to deal with even $N$ and perfect powers, and to reject prime inputs. Perfect-power recognition and primality testing have polynomial-time classical algorithms. Factoring a perfect power $b^k$, with $b,k>1$, already gives a nontrivial factor $b$. We may therefore consider an odd composite $N$ with at least two distinct prime factors.

Choose $\alpha$ uniformly from $1<\alpha <N$ and compute its greatest common divisor with $N$ using the Euclidean algorithm. A proper nontrivial divisor ends the computation. Otherwise $\alpha$ is a unit, and the remaining task is quantum order finding. SetPrepare a uniform quantum superposition in a $t$-qubit register and use quantum modular exponentiation in a second register to obtainRepeated squaring and reversible modular multiplication implement this step with polynomially many quantum gates in $L$. Apply the inverse quantum Fourier transform to the first register and perform a quantum measurement in the computational basis, obtaining $j$. Measuring the second register first, and Fourier-transforming the resulting periodic coset, gives the same distribution of $j$.

Here is a quantitative quantum Fourier sampling bound for order finding. If $r={\mathrm{ord}}_N(\alpha )$, multiplication by $\alpha$ cycles its $r$ orbit states. The Fourier eigenstates of that cycle have eigenvalues $e^{2\pi is/r}$, and the initial state $|1⟩$ has squared overlap $1/r$ with each, for $0\le s<r$. ThereforeConditioned on a particular eigenphase $s/r$, its nearest integer outcome $j_s$ obeys $|j_s/Q-s/r|\le 1/(2Q)$ and has probability at least $4/{\pi }^2$. Indeed the absolute amplitude is $|\sin (\pi Q\delta )/(Q\sin (\pi \delta ))|$, where $\delta =s/r-j_s/Q$. For $|Q\delta |\le 1/2$, the numerator is at least $2Q|\delta |$ and the denominator at most $\pi Q|\delta |$; the limiting value at $\delta =0$ is one.

If $\gcd (s,r)=1$, the fraction $s/r$ is reduced, and $r<N$ givesUse continued-fraction recovery in quantum order finding. The relevant approximation theorem says that reduced fractions satisfying $|a/b-p/q|<1/(2q^2)$ are continued fraction convergents of $a/b$. For an input rational of $O(L)$ digits, their $O(L)$ candidates can be enumerated classically in $O(L^3)$ time, and their denominators are at most the reduced input denominator. This is the supplied continued-fraction result; discard candidate denominators exceeding $N$. A zero measurement is treated as a failed order-finding sample.

For each remaining even candidate denominator $q$, compute $z={\alpha }^{q/2}\mathrm{mod}N$ by repeated squaring, and try $\gcd (z-1,N)$ and $\gcd (z+1,N)$. Return only a divisor $d$ with $1<d<N$; otherwise repeat the quantum sample or choose another $\alpha$. This candidate-denominator gcd post-processing cannot return an incorrect factor, since its output is checked directly. When the recovered denominator is the true even multiplicative order and the square root of one is nontrivial, part (i) guarantees success. Checking ${\alpha }^q\equiv 1(\mathrm{mod}N)$ before trying the gcds is also a valid, more restrictive convention; the single-run distinction matters in part (iii).

Two further standard quantitative facts explain why repetitions remain efficient. First, for a uniformly chosen unit modulo an odd integer with at least two distinct prime divisors, the probability of a useful unit in Shor factorization is at least $1/2$: its true multiplicative order is even and ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$. To see the source of this bound, the Chinese remainder theorem for unit groups makes the prime-power components independent. Each odd-prime-power unit group is cyclic. If its 2-primary order is $2^v$, the probability of the largest possible value of $v$ is $1/2$, and the probability of any specified smaller value is at most $1/2$. Failure requires all components to have the same $v$: either all zero, making $r$ odd, or all the same positive value, making the halfway power $-1$ in every component. Conditioning on one component, the chance another component matches it is at most $1/2$, so total failure is at most $1/2$.

Second, the fraction of phase numerators coprime to $r$ is $\phi (r)/r$, where $\phi$ is the Euler totient function. The elementary totient-ratio lower bound suffices: if the distinct prime divisors are $p_1<\cdots <p_k$, then $p_j\ge j+1$ and $k\le {\log }_{2}r$. The totient product formula therefore givesThus for a good $\alpha$, the probability of sampling a coprime phase numerator with the required accuracy is at least $(4/{\pi }^2)\phi (r)/r$. This is inverse-polynomial in the input length, so polynomially many repetitions achieve any fixed success probability. The quantum Fourier transform uses $O(t^2)$ elementary rotations and Hadamard gates in the ideal gate description, and the other quantum and classical stages are polynomial in $L$.

The reduction is therefore polynomial in the bit length:A small denominator need not itself be the true multiplicative order; verification of the final factor is essential, and no guarantee is claimed for every individual sample.

Set $p_{-2}=0,p_{-1}=1,q_{-2}=1,q_{-1}=0$ and define the continued fraction convergents byThe recurrence reverses the sign of $p_n{q}_{n-1}-p_{n-1}{q}_n$, whose initial value at $n=0$ is $-1$. Hence $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$. Every common divisor of $p_n,q_n$ divides this number, proving $\boxed{\gcd (p_n,q_n)=1}$.

The continued fraction convergents of $\sqrt{67}$ begin $8,41/5,90/11,131/16,221/27$. The last one yieldsChanging either sign gives another valid integer solution.

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

Let ${\beta }_{n+1}>0$ be the complete quotient after $a_n$. Part (a) writes the irrational number $\theta$ asso $\theta$ lies between the adjacent continued fraction convergents $p_n/q_n$ and $p_{n-1}/q_{n-1}$. Their separation isBecause all $a_j$ are positive integers, the recurrence $q_n=a_n{q}_{n-1}+q_{n-2}$ implies $q_n\to \infty$. Hence this separation tends to zero, and the squeeze theorem gives

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 quantum Fourier transform measurement supplies a rational approximationwhere $r$ is the desired multiplicative order. HereIts reduced continued fraction convergent has denominator two, so continued-fraction recovery in quantum order finding proposes $r=2$. Direct order verification from divisors confirms it:HenceAs a check, the classical final step of the Shor algorithm gives

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:

Given consecutive continued fraction convergents $p_{k-1}/q_{k-1}$ and $p_k/q_k$, the intermediate fractions $(t{p}_k+p_{k-1})/(t{q}_k+q_{k-1})$ for $1\le t\le a_{k+1}$ are semiconvergents, where $a_{k+1}$ is the next partial quotient. The endpoint is the next convergent. These fractions matter in best rational approximation when a denominator bound cuts between consecutive convergents.

A continued fraction $[a_0;a_1,a_2,\dots ]$ with integer $a_0$ and positive integer $a_j$ for $j\ge 1$. Its partial numerators are all one. The continued fraction convergents have the standard two-term numerator and denominator recurrences.