LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The complete quotients of $\sqrt{D}$ satisfy the $P_{n}, Q_{n}$ recurrence

Statement

Let $D$ be a positive integer that is not a square, let $α_{0} : = \sqrt{D},$ and let $a_{n}, α_{n}$ be the continued-fraction digits and complete quotients of $\sqrt{D}$ . Then there are unique integer pairs $(P_{n}, Q_{n})$ with $P_{0} = 0, Q_{0} = 1,$ such that for every $n \geq 0$ , $α_{n} = \frac{\sqrt{D} + P_{n}}{Q_{n}}, Q_{n} > 0, Q_{n} ∣ D - P_{n}^{2} .$ Moreover, if $a_{n} = ⌊ α_{n} ⌋,$ then $P_{n + 1} = a_{n} Q_{n} - P_{n}, Q_{n + 1} = \frac{D - P_{n + 1}^{2}}{Q_{n}}, α_{n + 1} = \frac{\sqrt{D} + P_{n + 1}}{Q_{n + 1}} .$

Facts & Assumptions

Given: A positive nonsquare integer $D$ , the real number $α_{0} = \sqrt{D}$ , and its complete quotients $α_{n}$ .

[F1]

For each complete quotient $α_{n}$ , the continued-fraction algorithm chooses the unique integer $a_{n}$ with $a_{n} \leq α_{n} < a_{n} + 1$ , and if $α_{n} \neq a_{n}$ then $α_{n + 1} = 1 / (α_{n} - a_{n})$ (Complete quotients in the continued-fraction algorithm).

Proof

technique · direct

1.1givenbasealgebra

At $n = 0$ one has $α_{0} = \sqrt{D} = \frac{\sqrt{D} + 0}{1},$ so the claimed form holds with $P_{0} = 0$ and $Q_{0} = 1$ , and certainly $Q_{0} > 0$ and $Q_{0} ∣ D - P_{0}^{2} = D$ .

1.2F1ihalgebra

Assume $α_{n} = \frac{\sqrt{D} + P_{n}}{Q_{n}}, Q_{n} > 0, Q_{n} ∣ D - P_{n}^{2} .$ Let $a_{n}$ be the integer from [F1], and set $P_{n + 1} : = a_{n} Q_{n} - P_{n} .$ Since $α_{n} - a_{n} > 0$ , one has $\sqrt{D} - P_{n + 1} = \sqrt{D} + P_{n} - a_{n} Q_{n} > 0,$ so $D - P_{n + 1}^{2} > 0$ . Also $P_{n + 1} \equiv - P_{n} (m o d Q_{n})$ , hence $P_{n + 1}^{2} \equiv P_{n}^{2} (m o d Q_{n})$ and therefore $Q_{n} ∣ D - P_{n + 1}^{2}$ . Thus $Q_{n + 1} : = \frac{D - P_{n + 1}^{2}}{Q_{n}}$ is a positive integer. Rationalizing the denominator now gives $α_{n + 1} = \frac{1}{α_{n} - a_{n}} = \frac{Q_{n}}{\sqrt{D} - P_{n + 1}} = \frac{\sqrt{D} + P_{n + 1}}{Q_{n + 1}} .$

2.1step 1.1step 1.2discharge-inductionalgebra∎

If also $\frac{\sqrt{D} + P}{Q} = \frac{\sqrt{D} + P^{'}}{Q^{'}}$ with $Q, Q^{'} > 0$ , then cross-multiplication gives $(Q^{'} - Q) \sqrt{D} = Q P^{'} - Q^{'} P .$ If $Q^{'} \neq Q$ , this would make $\sqrt{D}$ rational, impossible because $D$ is a positive nonsquare integer. Hence $Q^{'} = Q$ , and then $P^{'} = P$ . So the normalized pair $(P_{n}, Q_{n})$ is unique at each stage. Steps 1.1 and 1.2 therefore prove the statement for all $n \geq 0$ .

Depends on

Complete quotients in the continued-fraction algorithm

Used by

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Peter Hackman, Elementary Number Theory (standard reference, not scraped)
MIT 18.781, Lecture 21: Brahmagupta-Pell Equation (standard reference, not scraped)

The complete quotients of DD​ satisfy the Pn,QnPn​,Qn​ recurrence