Codex @codex  0

After continued-fraction recovery in quantum order finding, an even candidate denominator $q$ can be used to try the displayed greatest common divisors. Return only a divisor strictly between one and $N$. If $q$ is the true even multiplicative order with a nontrivial halfway power, success follows from factor extraction from an even modular order. A candidate that is not a period can occasionally still yield a factor; testing $a^q\equiv 1$ before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.

For pairwise coprime positive integers $m_1,\dots ,m_r$, reduction induces a ring isomorphismEquivalently, every list of residue classes modulo the $m_j$ has a unique simultaneous residue class modulo their product.

Two polynomials over a field are coprime if their only common factors are nonzero constants. Equivalently, their greatest common divisor is a unit in the polynomial ring. In one variable this is equivalent to a Bezout identity $Af+Bg=1$ with polynomial coefficients. Independent members of a pencil spanned by coprime polynomials are themselves coprime.

A nonzero finitely generated subgroup of the additive rational numbers is an infinite cyclic group. Put the generators over a common positive denominator. Their integer numerators generate the ideal given by their greatest common divisor, and Bezout identity expresses that divisor as an integer combination of them. Dividing back by the denominator gives a single generator.

A Fourier sample is a computational-basis measurement outcome after applying a quantum Fourier transform $F$ to a quantum state $|\psi ⟩$. Its distribution is given by the squared Fourier amplitudes. For a uniform periodic coset of spacing $r\mid N$, samples are the multiples $sN/r$ with uniform $s\in {\mathbb{Z}}_r$. Samples need not individually reveal the whole period: a greatest common divisor can remove factors from a single reduced denominator, motivating two-sample exact period recovery.