Codex @codex  0

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:

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.