Codex @codex  0

Use the positive-exponent quantum Fourier transform convention $F_N|x⟩=N^{-1/2}{\sum }_t{e}^{2\pi ixt/N}|t⟩$. The period of a function here is the least positive translation leaving the function unchanged on the cyclic group ${\mathbb{Z}}_N$. The injective promise means $f(x)=f(x^{\prime })$ exactly when $x\equiv x^{\prime }(\mathrm{mod}r)$. In particular $r\mid N$: the subgroup of period translations is generated by $r$, and wrapping the argument by $N$ preserves its value. This is exact quantum period finding on a finite cyclic group, rather than the truncated, nondividing-period version requiring continued fractions.

Prepare a uniform superposition state in the first quantum register using $F_N|0⟩$, and perform a reversible computation of the function into a second quantum register, cleaning its workspace by uncomputation:A quantum measurement in the computational basis of the second quantum register leaves a periodic coset state in the first:For the quantum Fourier transform of this periodic coset state, the finite geometric series vanishes unless the measured label is $t=mN/r$. On those labels its normalized amplitude is $r^{-1/2}{e}^{2\pi iam/r}$. Thus $m$ has the uniform distribution on a finite set on $\{0,\dots ,r-1\}$, irrespective of $a$.

Compute the greatest common divisor by the Euclidean algorithm, and set $q=N/\gcd (t,N)$, with $\gcd (0,N)=N$. Since $t=mN/r$,The exact period recovery from a Fourier sample is therefore certified by testing $f(q\mathrm{mod}N)=f(0)$. Every candidate $q$ divides $r$ and lies between $1$ and $r$, so the injective promise makes that equality equivalent to $q=r$. This includes $r=N$, where the test uses input $0$, and $r=1$, which always succeeds. The test does not assert that an arbitrary equality of function values certifies an arbitrary period; the Fourier-derived divisor restriction is essential.

The concise result isHere $\phi$ is the Euler totient function, with $\phi (1)=1$. The totient lower bound from the Mertens product gives $\phi (r)/r=\Omega (1/\max \{1,\log \log N\})$ for $r\le N$. Each trial uses polynomial time quantum Fourier transforms, function evaluations and Euclidean algorithm arithmetic in $\log N$. Repeating $O(\max \{1,\log \log N\})$ independent trials gives constant success probability; the herald accepts only correct answers.

The printed asymptotic bound has the wrong direction for this argument. In Big O notation, the stated upper bound on the number of coprime integers supplies no success lower bound and is itself false uniformly: for prime $N$, $\phi (N)=N-1$, not $O(N/\log \log N)$. Likewise the single-trial success need not be $O(1/\log \log N)$, since it tends to one for $r=N$ prime. The meaningful corrected guarantee is the lower bound above. If an upper-bounded success rate is literally required, one may deliberately retain an accepted result with an independent probability proportional to $1/\max \{1,\log \log N\}$; this discards useful successes and is unnecessary for efficient recovery.

The Euclidean algorithm repeatedly replaces a pair $(a,b)$ by $(b,a-qb)$ without changing its greatest common divisor. Reversing the divisions expresses $\gcd (a,b)$ as an integer linear combination $\alpha a+\beta b$, which is Bézout's identity.

Here $3=3(15)-2(21)$, and thereforeOne solution is $(x,y,z)=(36,-24,-1)$. It is not unique: for every $t\in \mathbb{Z}$, $(x,y,z)=(36+7t,-24-5t,-1)$ is another solution.

Starting with ${\theta }_0=\theta$, definewhile the denominator is nonzero. This gives the simple continued fractionA finite expansion is rational by evaluating it from the bottom. Conversely, for rational $\theta$, these steps are the Euclidean algorithm applied to numerator and denominator, so the remainders eventually vanish.

Define convergents byThe recurrence givesso induction yieldsIn particular,Since an irrational $\theta$ lies strictly between these convergents, the two approximation errors sum to this distance. If both displayed bounds in the question failed, their sum would be at leastby the arithmetic-geometric mean inequality, contradicting strict betweenness. Thus at least one bound holds.

Applying the Euclidean algorithm,Hence $\gcd (2508,3211)=19$. Since $19$ does not divide $55$, the linear Diophantine equation solvability criterion gives

The linear Diophantine equation solvability criterion says that $ax+by=c$ has an integer solution exactly when $\gcd (a,b)$ divides $c$. The Euclidean algorithm givesThus $\gcd (1007,2314)=1$, which divides $37$. Therefore

If $f$ is an irreducible polynomial over a field $F$, then a nonzero residue $[g]$ modulo $(f)$ has $\gcd (f,g)=1$. The Euclidean algorithm supplies $uf+vg=1$, giving inverse $[v]$ for $[g]$. Thus the quotient ring $F[X]/(f)$ is a field. If $\mathrm{deg}f=d$ and $F$ has $q$ elements, polynomial division supplies exactly $q^d$ residue classes.