[proofplan] The proof has two parts. First, two candidates give two bounded representatives of the same congruence relation, so their cross-product is divisible by $m$ but has absolute value strictly less than $m$; hence the two reduced fractions coincide. Second, the stated verification conditions are exactly the definition of a rational reconstruction candidate, so any accepted proposed output is a candidate. The uniqueness already proved then implies that any accepted output is the only possible rational reconstruction candidate. [/proofplan]

[step:Prove that two candidates must represent the same reduced fraction] Suppose $(p,q)$ and $(p',q')$ are rational reconstruction candidates for $(x,m;P,Q)$. Since \begin{align*} p &\equiv x_0q \pmod m, & p' &\equiv x_0q' \pmod m, \end{align*} multiplying the first congruence by $q'$ and the second by $q$ gives \begin{align*} pq' \equiv x_0qq' \equiv p'q \pmod m. \end{align*} Thus $m$ divides the integer $pq'-p'q$. The bounds on the two candidates give $|p|\leq P$, $|p'|\leq P$, $0<q\leq Q$, and $0<q'\leq Q$. Hence the triangle inequality and the defining hypothesis $2PQ<m$ give \begin{align*} |pq'-p'q| \leq |p|q' + |p'|q \leq PQ + PQ = 2PQ < m. \end{align*} The only integer divisible by $m$ with absolute value strictly less than $m$ is $0$, so \begin{align*} pq'-p'q = 0. \end{align*} Hence $p/q=p'/q'$ as rational numbers. Since $\gcd(p,q)=\gcd(p',q')=1$ and $q,q'>0$, both pairs are the same reduced integer representative of that rational number. Therefore $(p,q)=(p',q')$. [/step]

[step:Verify that an accepted proposed output is a candidate]Let $(p,q)\in\mathbb{Z}\times\mathbb{Z}$ be a proposed output after the denominator sign convention has been applied. The verification test accepts $(p,q)$ only when all five conditions \begin{align*} |p|\leq P, \qquad 0<q\leq Q, \qquad \gcd(p,q)=1, \qquad \gcd(q,m)=1, \qquad p\equiv x_0q\pmod m \end{align*} hold. These are precisely the numerator bound, denominator bound, reducedness condition, invertibility condition modulo $m$, and congruence condition in the definition of a rational reconstruction candidate for $(x,m;P,Q)$, because $x_0$ is the chosen integer representative of $x\in\mathbb{Z}/m\mathbb{Z}$.[/step]

[guided]The verification stage is deliberately stronger than merely checking a congruence. A rational reconstruction candidate must pass five independent tests: the numerator must be small, the denominator must be positive and small, the fraction must be reduced, the denominator must be invertible modulo $m$, and the congruence must match the residue class $x$. Here $x_0\in\{0,1,\dots,m-1\}$ denotes the chosen integer representative of $x\in\mathbb{Z}/m\mathbb{Z}$. Therefore the congruence condition for the residue class $x$ is exactly \begin{align*} p\equiv x_0q\pmod m. \end{align*} If the final verification accepts, then by definition it has checked \begin{align*} |p|\leq P, \qquad 0<q\leq Q, \qquad \gcd(p,q)=1, \qquad \gcd(q,m)=1, \qquad p\equiv x_0q\pmod m. \end{align*} Thus the accepted pair satisfies every condition required of a rational reconstruction candidate. This step is only a soundness statement: it proves that accepted outputs are valid candidates, while the uniqueness step proves that there cannot be two different valid candidates.[/guided]

[step:Conclude that every accepted output is unique] If the verification test accepts a pair $(p,q)$, the previous step shows that $(p,q)$ is a rational reconstruction candidate for $(x,m;P,Q)$. The first step proves that there is at most one such candidate. Hence every accepted output is the unique rational reconstruction candidate. This completes the proof. [/step]