In short

Continued fractions are an algorithm for writing any real number x as a tower

x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}} = [a_0; a_1, a_2, a_3, \ldots],

where each a_i is a positive integer (except a_0, which can be any integer). For a rational p/q the expansion terminates in O(\log q) steps — it is the Euclidean algorithm wearing different clothes. Truncating the expansion at level k gives the k-th convergent p_k/q_k, in lowest terms, and successive convergents are the best rational approximations of x at every denominator size.

The role in Shor's algorithm: quantum phase estimation measures a fraction \widetilde\varphi = y/2^t that approximates s/r to within 1/(2^{t+1}). When t \ge 2n, this error is below 1/(2N^2) \le 1/(2r^2), and Legendre's theorem then forces s/r to appear as one of the convergents of \widetilde\varphi. Running continued fractions on \widetilde\varphi and picking the first convergent with denominator \le N gives a candidate for r. Verify by checking a^r \equiv 1 \pmod N. The whole classical post-processing takes O(n^3) bit operations — negligible compared to the quantum modular exponentiation that precedes it.

Quantum phase estimation has just done its job. The ancilla register measured to an integer y, and you divide by 2^t to get \widetilde\varphi = y/2^t — a fraction that is promised to be close to s/r, where r is the order of a modulo N and s is an integer in \{0, 1, \ldots, r-1\} that you have no control over. The quantum machine has given you a rational number that is close to the thing you want. How do you recover the thing you want?

The answer is an algorithm that has been around for two thousand years. Aryabhata used it in the 5th century to solve linear Diophantine equations under the name kuṭṭaka — the pulveriser. The same algorithm, rediscovered by Euler and named "continued fractions" in the 18th century, is what turns a quantum measurement into the final answer of Shor's algorithm. The quantum part of Shor was sublime; the classical part that finishes it is one of the oldest computations in mathematics.

What you will get from this chapter. First, the definition of a continued fraction and how to compute one for any rational number — by hand, in a few seconds. Second, the convergents of the expansion and the remarkable fact that they are the best rational approximations possible. Third, Legendre's theorem, the precise statement that guarantees the convergent you want is there. Fourth, the Shor connection: how a noisy measurement \widetilde\varphi \approx s/r is decoded into the order r. Two worked examples: a pure number-theory case (the expansion of 13/15) and a full Shor-style recovery (N = 15, measurement 3/4 \to r = 4).

What a continued fraction is

Take any positive rational, say 13/15. Follow this recipe:

  1. The integer part is \lfloor 13/15 \rfloor = 0. Write that down: a_0 = 0. Remainder: 13/15 - 0 = 13/15.
  2. Invert the remainder: 15/13. Its integer part is \lfloor 15/13 \rfloor = 1. Write: a_1 = 1. Remainder: 15/13 - 1 = 2/13.
  3. Invert: 13/2. Integer part: \lfloor 13/2 \rfloor = 6. Write: a_2 = 6. Remainder: 13/2 - 6 = 1/2.
  4. Invert: 2/1 = 2. Integer part: 2. Write: a_3 = 2. Remainder: 0. Stop.

The sequence is [0; 1, 6, 2]. Reconstruct by stacking:

\frac{13}{15} \;=\; 0 + \cfrac{1}{1 + \cfrac{1}{6 + \cfrac{1}{2}}}.

Verify: 6 + 1/2 = 13/2; 1 + 2/13 = 15/13; 1/(15/13) = 13/15. Match.

That is the whole definition. A continued fraction is a finite or infinite tower of the form a_0 + 1/(a_1 + 1/(a_2 + \cdots)), compactly written [a_0; a_1, a_2, \ldots]. For a rational p/q, the expansion is the Euclidean-algorithm trace: each a_k is the quotient when you divide the current numerator by the current denominator, and the remainders feed the next step. The expansion terminates in O(\log q) steps, one per Euclidean division — the same count that makes Euclid's algorithm run in O(\log^2 N) total bit operations.

Continued fraction expansion

For a real number x, define a sequence of integers a_0, a_1, a_2, \ldots recursively. Let x_0 = x and, for k \ge 0,

a_k = \lfloor x_k \rfloor, \qquad x_{k+1} = \frac{1}{x_k - a_k}

(provided x_k \ne a_k; otherwise the sequence terminates at a_k). The continued fraction expansion of x is

x = [a_0; a_1, a_2, a_3, \ldots] \;=\; a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}}.

Each a_k for k \ge 1 is a positive integer; a_0 can be any integer (including 0). The expansion terminates if and only if x is rational. For irrational x, the expansion continues forever.

Reading the definition. The recipe peels off the integer part, inverts what is left, and repeats. Each integer a_k that comes out is a positive integer (except a_0, which is the floor of the whole thing). For rationals, the process stops when a remainder hits zero — exactly the stopping condition for Euclid's algorithm. For irrationals like \sqrt{2} or \pi, the process runs forever, which is a feature, not a bug: the infinite expansion encodes precise information about the irrational.

The standard convention: use [a_0; a_1, a_2, ...] with a semicolon after a_0, commas between the rest. This matches Hardy–Wright, Wikipedia, and every number-theory text you will see.

The continued-fraction algorithm as a chain of Euclidean stepsA flowchart showing four steps of the Euclidean-style recursion for thirteen over fifteen. Each row shows a box with the current numerator over denominator, an arrow labelled take integer part pointing to the output integer a sub k, a second arrow labelled invert the fractional remainder pointing to the next row. Starting values: thirteen over fifteen, yielding a zero equals zero. Next row: fifteen over thirteen yielding a one equals one. Next row: thirteen over two yielding a two equals six. Final row: two over one yielding a three equals two and zero remainder, ending the recursion.Continued-fraction expansion of 13/15x₀ =13 / 15floora₀ =0invert remainder 13/15 → 15/13x₁ =15 / 13a₁ =1invert 2/13 → 13/2x₂ =13 / 2a₂ =6continue one more stepx₃ = 2/1 = 2, remainder 0a₃ = 2recursion stops (remainder 0)13/15 = [0; 1, 6, 2]four integers, three Euclidean divisions
The continued-fraction expansion of $13/15 = [0; 1, 6, 2]$. Each step: take the floor to get the next integer $a_k$, then invert the fractional remainder and recurse. Stop when the remainder is zero. The sequence of integers is the expansion; the number of steps is the depth of Euclid's algorithm on $(13, 15)$, which is $O(\log 15)$.

Convergents — the best rational approximations

If you truncate the expansion at level k, you get a rational number called the k-th convergent and denoted p_k / q_k. For 13/15 = [0; 1, 6, 2] the four convergents are:

Two important facts about convergents, used constantly in Shor's post-processing.

Fact 1: each convergent is in lowest terms. That is, \gcd(p_k, q_k) = 1 for every k. This follows from the recurrence

p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},

with p_{-1} = 1, p_{-2} = 0, q_{-1} = 0, q_{-2} = 1. You can verify by induction that p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}, which forces \gcd(p_k, q_k) = 1. The details are in the going deeper section; the headline is: when continued fractions hands you a convergent, the numerator and denominator are automatically coprime.

Fact 2: each convergent is the best rational approximation with its denominator. More precisely, if p/q is any fraction with q \le q_k, then |x - p/q| \ge |x - p_k/q_k|. You cannot approximate x better with a small denominator than the convergents do.

The approximation quality tightens exponentially as you go deeper:

\left| x - \frac{p_k}{q_k} \right| < \frac{1}{q_k q_{k+1}}.

In words: each convergent gets you within one over the product of its denominator and the next denominator. Since denominators grow at least as fast as Fibonacci, convergents close in on x very fast.

Convergents of thirteen over fifteen approaching the true valueA number line from zero to one with a vertical tick at thirteen over fifteen highlighted in accent. Four markers labelled convergent zero at zero, convergent one at one, convergent two at six over seven close to the target, and convergent three at thirteen over fifteen exactly. Each convergent has a horizontal error bracket beneath showing the gap to thirteen over fifteen shrinks dramatically with each step.Convergents of 13/15 — how fast they close in0113/15 ≈ 0.867targetp₀/q₀ = 0/1error ≈ 0.867p₁/q₁ = 1/1error ≈ 0.133p₂/q₂ = 6/7 ≈ 0.857error ≈ 0.0095each convergent is the best rational approximation with its denominator — error shrinks from 0.867 to 0.133 to 0.0095 to 0
The four convergents of $13/15 = [0; 1, 6, 2]$ plotted on the number line. Convergents alternate above and below the target and close in exponentially: the error drops from $0.867$ to $0.133$ to $0.0095$ to $0$. The third convergent $6/7 \approx 0.857$ is within one percent of $13/15 \approx 0.867$ using only a denominator of $7$ — the kind of tight approximation that makes continued fractions the tool of choice for recovering small-denominator fractions from noisy measurements.

Legendre's theorem — the guarantee Shor needs

Here is the theorem that makes continued fractions the right tool for recovering s/r from \widetilde\varphi.

Legendre's theorem (rational approximation version)

Let x be a real number and let p, q be integers with q \ge 1. If

\left| x - \frac{p}{q} \right| < \frac{1}{2 q^2},

then p/q (in lowest terms) appears as one of the convergents of the continued-fraction expansion of x.

Reading the theorem. It says: if a rational p/q is a very good approximation of x — specifically, closer than 1/(2q^2) — then p/q is not some random rational; it is one of the distinguished convergents of x. The convergents are the only rationals that can approximate x this well with a denominator as small as q.

For Shor's algorithm, you want to recover s/r from a measurement \widetilde\varphi = y/2^t that is known to be within 1/(2^{t+1}) of s/r. Apply Legendre with p/q = s/r and x = \widetilde\varphi: you need

\left| \widetilde\varphi - \frac{s}{r} \right| < \frac{1}{2 r^2}.

This holds if 2^{t+1} > 2 r^2, i.e., 2^t > r^2. Since r < N, choosing t = 2n + 1 = 2 \lceil \log_2 N \rceil + 1 guarantees 2^t > N^2 > r^2, so Legendre applies. The conclusion: s/r (in lowest terms) is one of the convergents of the measured \widetilde\varphi. Compute the convergents, test each one by checking if its denominator works as an order for a, and you recover r.

That is the entire role of continued fractions in Shor. The quantum computer gives you a noisy rational; continued fractions picks out the clean one hiding inside.

The proof of Legendre is short and appears in every number-theory text. It is in the going deeper section at the end of this chapter.

Worked examples

Two examples. First: a pure number-theory computation, expanding a random rational. Second: a full Shor-style recovery on the toy case N = 15.

Example 1: continued-fraction expansion of 51/100

Setup. Compute the continued-fraction expansion of 51/100.

Step 1. Integer part of 51/100.

\lfloor 51/100 \rfloor = 0 \implies a_0 = 0.

Remainder: 51/100 - 0 = 51/100. Why the floor: for any real number, the continued-fraction expansion starts by peeling off the integer part. 51/100 < 1, so that part is zero.

Step 2. Invert the remainder and take the floor.

\frac{1}{51/100} = \frac{100}{51}, \qquad \lfloor 100/51 \rfloor = 1 \implies a_1 = 1.

Remainder: 100/51 - 1 = 49/51. Why invert: the continued-fraction form a_0 + 1/(a_1 + \cdots) puts the next step under a 1/\cdot fraction. Inverting what is left of 51/100 gives 100/51 — that is the input to the next peel-off.

Step 3. Continue. Invert 49/51 \to 51/49, floor is 1, so a_2 = 1. Remainder: 51/49 - 1 = 2/49.

Step 4. Invert 2/49 \to 49/2, floor is 24, so a_3 = 24. Remainder: 49/2 - 24 = 1/2.

Step 5. Invert 1/2 \to 2, floor is 2, so a_4 = 2. Remainder: 0. Stop.

Result. 51/100 = [0; 1, 1, 24, 2]. Verify by reconstructing from the bottom up:

2 + 0 = 2,\; 24 + 1/2 = 49/2,\; 1 + 2/49 = 51/49,\; 1 + 49/51 = 100/51,\; 0 + 51/100 = 51/100. \;\checkmark

Convergents. Compute them with the recurrence p_k = a_k p_{k-1} + p_{k-2}, q_k = a_k q_{k-1} + q_{k-2}, starting from p_{-1} = 1, q_{-1} = 0, p_{-2} = 0, q_{-2} = 1:

| k | a_k | p_k | q_k | p_k / q_k | error = |51/100 - p_k/q_k| | |---|---|---|---|---|---| | 0 | 0 | 0 | 1 | 0/1 | 0.51 | | 1 | 1 | 1 | 1 | 1/1 | 0.49 | | 2 | 1 | 1 | 2 | 1/2 | 0.01 | | 3 | 24 | 25 | 49 | 25/49 | 0.00020 | | 4 | 2 | 51 | 100 | 51/100 | 0 |

Each convergent improves dramatically. 1/2 is within 0.01 of 51/100, and 25/49 is within 2 \times 10^{-4} — this is the "every convergent is the best approximation with its denominator" phenomenon in action.

Convergents of fifty one over one hundredA horizontal error plot on a log scale showing the error of each convergent of fifty one over one hundred. Five points shown at convergent index zero through four, with errors approximately half, half, one hundredth, two ten-thousandths, and zero. A straight line connects them trending sharply downward.Approximation error of convergents of 51/10010⁻⁴10⁻³10⁻²10⁻¹10⁰errork=0 (0/1)k=1 (1/1)k=2 (1/2)k=3 (25/49)k=4
Error of the first five convergents of $51/100$ on a log scale. The jump from $1/1$ (error $0.49$) to $1/2$ (error $0.01$) is nearly two orders of magnitude; from $1/2$ to $25/49$ another two orders. Convergents are exponentially efficient rational approximations — the feature Shor exploits.

What this shows. For a random rational like 51/100, the continued-fraction expansion has depth 5 and takes a handful of Euclidean divisions to compute. This is exactly how Shor's classical post-processing recovers r: run this expansion on \widetilde\varphi, read off convergents, and test each denominator.

Example 2: Shor recovery — measurement 0.75 reveals $r = 4$ for $N = 15$

Setup. You are running Shor's algorithm on N = 15 with a = 7. Phase estimation with t = 4 ancilla qubits has just measured y = 12, giving

\widetilde\varphi = y/2^t = 12/16 = 0.75.

You need to recover the order r.

Step 1. Compute the continued-fraction expansion of 0.75 = 3/4.

\lfloor 3/4 \rfloor = 0 \implies a_0 = 0, \text{ remainder } 3/4.
\lfloor 4/3 \rfloor = 1 \implies a_1 = 1, \text{ remainder } 1/3.
\lfloor 3/1 \rfloor = 3 \implies a_2 = 3, \text{ remainder } 0. \text{ Stop.}

So 3/4 = [0; 1, 3].

Step 2. Compute convergents.

k a_k p_k q_k p_k/q_k
0 0 0 1 0/1
1 1 1 1 1/1
2 3 3 4 3/4

Step 3. Take the largest convergent with denominator q_k \le N = 15. That is q_2 = 4. The candidate order is r' = 4. Why test denominator \le N: Shor's theory guarantees the true order r satisfies r < N, so any convergent with denominator > N cannot be the target s/r. You always want the last convergent whose denominator is still in range.

Step 4. Verify. Compute a^{r'} \bmod N:

7^4 = 2401 = 160 \cdot 15 + 1 = 1 \bmod 15. \;\checkmark

So r' = 4 is a valid order. (If the check had failed — a^{r'} \ne 1 \bmod N — you would have tried smaller convergents, or re-run the quantum circuit with a different measurement.)

Step 5. Complete Shor. With r = 4 even and a^{r/2} = 7^2 = 49 = 4 \bmod 15, compute the factors:

\gcd(4 - 1, 15) = \gcd(3, 15) = 3, \qquad \gcd(4 + 1, 15) = \gcd(5, 15) = 5.

Result. The measurement \widetilde\varphi = 3/4 decoded into r = 4 via one three-step continued-fraction expansion. N = 15 = 3 \times 5.

Shor post-processing: measurement to order via continued fractionsA left to right flow. First box: quantum phase estimation output labelled y equals twelve, t equals four, giving phi tilde equals zero point seven five. Arrow labelled continued fractions. Second box: expansion zero, one, three with convergents table showing zero over one, one over one, three over four. Arrow labelled pick largest denominator less than or equal to N. Third box: candidate r equals four. Arrow labelled verify seven to the fourth mod fifteen equals one. Final box: r equals four confirmed.Shor classical post-processing: φ̃ → rQPE measuredy = 12, t = 43/4= 0.75CFexpansion [0; 1, 3]convergents:0/1, 1/1, 3/4denominator ≤ 15?candidater' = 4verify7⁴ mod 15= 1 ✓r = 4 confirmed
The entire Shor classical post-processing. The quantum measurement $\widetilde\varphi = 3/4$ is expanded as $[0; 1, 3]$; the largest convergent with denominator $\le N = 15$ is $3/4$ itself, giving candidate $r' = 4$; direct verification $7^4 \equiv 1 \pmod{15}$ confirms the order. Total classical work: a handful of Euclidean divisions, three modular exponentiations, one gcd.

What this shows. Continued fractions is the bridge between the quantum measurement and the final factoring answer. The quantum part was the sublime bit — exponential speedup, interference, phase kickback. The classical finisher is ancient arithmetic that runs in milliseconds on a laptop. Together they factor N.

Common confusions

Going deeper

The worked examples above are the Shor-relevant material. The going-deeper section below fills in the convergent recurrence and its proof, Legendre's theorem proof, Shor's success-probability analysis, the connection to Dirichlet's approximation theorem, and the Indian mathematical heritage of continued fractions from Aryabhata's kuṭṭaka to Ramanujan's modular expansions. If Shor's post-processing is all you came for, you can stop. The rest is for readers who want the full number-theoretic context.

The convergent recurrence and why it gives lowest terms

Define p_k, q_k by the recurrence

p_k = a_k p_{k-1} + p_{k-2}, \qquad q_k = a_k q_{k-1} + q_{k-2},

with base cases p_{-1} = 1, p_{-2} = 0, q_{-1} = 0, q_{-2} = 1. Then p_k / q_k = [a_0; a_1, \ldots, a_k], the k-th convergent. You can prove this by induction: at each level, the expansion adds a new "layer" at the bottom of the tower, and the recurrence tracks how that bottom-layer addition propagates up.

The key identity is

p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}.

Proof: at k = 0, p_0 q_{-1} - p_{-1} q_0 = a_0 \cdot 0 - 1 \cdot 1 = -1 = (-1)^{-1}, check. For the inductive step, substitute the recurrence:

p_k q_{k-1} - p_{k-1} q_k = (a_k p_{k-1} + p_{k-2}) q_{k-1} - p_{k-1}(a_k q_{k-1} + q_{k-2})
= a_k p_{k-1} q_{k-1} + p_{k-2} q_{k-1} - a_k p_{k-1} q_{k-1} - p_{k-1} q_{k-2} = -(p_{k-1} q_{k-2} - p_{k-2} q_{k-1}) = -(-1)^{k-2} = (-1)^{k-1}.

This identity forces \gcd(p_k, q_k) = 1: any common factor d of p_k and q_k divides the left side, hence divides \pm 1, so d = 1. Every convergent is automatically in lowest terms.

Proof sketch of Legendre's theorem

Suppose p/q is in lowest terms and |x - p/q| < 1/(2q^2). Expand x in continued fractions and let p_k/q_k be the convergents. Use the fact that successive convergents bracket x from alternate sides and the error bound

\left| x - \frac{p_k}{q_k} \right| < \frac{1}{q_k q_{k+1}}.

A few lines of inequality manipulation show that if p/q is a rational with |x - p/q| < 1/(2q^2) and p/q is not among the convergents, you reach a contradiction. The full proof (Hardy and Wright, An Introduction to the Theory of Numbers, §10.15) is about two pages of careful casework. The moral: the convergents exhaust all the "very good" rational approximations.

Dirichlet's approximation theorem

Related to Legendre's theorem is Dirichlet's approximation theorem: for any irrational x and any Q \ge 1, there exist integers p, q with 1 \le q \le Q and

\left| x - \frac{p}{q} \right| < \frac{1}{q Q}.

The continued-fraction convergents realise Dirichlet's bound: the convergent p_k/q_k with q_k as large as possible below Q satisfies exactly this. Dirichlet's theorem is the generic existence claim; the continued-fraction algorithm is the constructive proof.

Shor's success probability per shot

The full Shor probability analysis. For a random measurement outcome, the probability that phase estimation returns a \widetilde\varphi satisfying Legendre's condition for s/r is \ge 4/\pi^2 \approx 0.405 per shot (Shor 1994; Preskill Ch. 7). This is per eigenstate |u_s\rangle, and since the input is a uniform superposition of all r eigenstates, every s is equally likely. The probability that the recovered s is coprime to r (so that continued fractions gives the full r, not a divisor) is \ge 6/\pi^2 \cdot \varphi(r)/r where \varphi is Euler's totient; this is \ge 1/\log\log r asymptotically.

Combining: each quantum run succeeds with probability at least some constant; two or three runs on average recover r with probability close to 1. This is why Shor's algorithm is probabilistic but efficient: you re-run the quantum circuit a small number of times, apply continued fractions to each result, and take the smallest denominator consistent with the verification check.

Continued fractions for famous irrationals

Every irrational has a unique infinite continued-fraction expansion, and some of the most beautiful are:

Each of these expansions tells you something about how irrational the number is. The golden ratio, with all a_k = 1, is the hardest to approximate by rationals (its convergents close in slowest). \pi's huge fourth coefficient is why Aryabhata's approximation \pi \approx 62832/20000 = 3.1416 was so accurate for its era.

Indian heritage — the kuṭṭaka and Ramanujan

The continued-fraction algorithm is ancient Indian mathematics. Aryabhata (5th century CE), in the Āryabhaṭīya, gave a procedure called kuṭṭaka (the "pulveriser") for solving linear Diophantine equations ax + by = c in integers. Aryabhata's kuṭṭaka is exactly the continued-fraction expansion of a/b, used to back-solve the equation. Over the next millennium, Indian mathematicians — Brahmagupta (7th century), Bhāskara II (12th century), and the Kerala school (14th–16th centuries) — refined the algorithm and applied it to Pell's equation, astronomical calculations, and approximations of irrationals.

Bhāskara II's Bījagaṇita uses continued-fraction-style recursion to solve x^2 - Ny^2 = 1 for integers, via the chakravāla method — a technique that eluded European mathematicians until the 18th century. Bhāskara's approximations of \sqrt{2}, \pi, and \sqrt{3} are all convergents of the corresponding continued fractions.

Srinivasa Ramanujan took continued fractions into entirely new territory in the 20th century: the Rogers-Ramanujan continued fraction

R(q) = \cfrac{q^{1/5}}{1 + \cfrac{q}{1 + \cfrac{q^2}{1 + \cfrac{q^3}{1 + \cdots}}}}

converges for |q| < 1 and has extraordinary identities connecting it to modular forms. Ramanujan discovered many of these in his notebooks (later edited by Hardy) without proofs — most have been verified since, and some are still being interpreted. When you run continued fractions on Shor's output, you are using a tool with roots in Indian mathematics that predate Shor's algorithm by sixteen hundred years.

Where this leads next

References

  1. Wikipedia, Continued fraction. Comprehensive reference with all the standard identities and famous examples.
  2. Peter Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer (1994) — arXiv:quant-ph/9508027. §5 contains the continued-fractions post-processing argument and success-probability bound.
  3. Nielsen and Chuang, Quantum Computation and Quantum Information §5.3 and Appendix 4 — Cambridge University Press. The continued-fractions analysis of Shor in full detail.
  4. John Preskill, Lecture Notes on Quantum Computation Chapter 7 — theory.caltech.edu/~preskill/ph229. Clear derivation of Legendre's theorem in the Shor context.
  5. Wikipedia, Legendre's theorem on continued fractions. Statement and proof of the approximation-uniqueness theorem.
  6. Wikipedia, Kuṭṭaka. Aryabhata's continued-fraction algorithm and its role in Indian mathematics.