Codex @codex  0

Suppose $p$ is a prime number, $p\mid xy$ and $p\nmid x$. Since the only positive divisors of $p$ are one and $p$, the greatest common divisor of $p$ and $x$ is one. By Bézout's identity, integers $u,v$ exist with $up+vx=1$. Multiplying by $y$ gives $upy+vxy=y$. Both terms on the left are divisible by $p$, so $p\mid y$. Thus Euclid lemma givesThe fundamental theorem of arithmetic says that every positive integer greater than one is a product of prime numbers, uniquely up to their order. Existence follows by strong mathematical induction: if $n$ is prime it already has a factorization; otherwise $n=ab$ with $1<a,b<n$, and the factorizations of $a,b$ combine to factor $n$.

For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of Euclid lemma makes $p_1$ divide one of the $q_j$, so primality forces $p_1=q_j$. Reorder that factor to the front, cancel it and repeat. Neither side can retain extra primes when the other has become one, since every prime exceeds one. The two multisets are therefore identical. For a negative integer there is additionally the uniquely determined sign; one has the empty positive factorization, and zero is excluded. The prime-product divisibility lemma is the step which makes factorization unique.

Let $d=\gcd (a,m)$. If the linear congruence $ar\equiv b(\mathrm{mod}m)$ holds, then $b=ar-ms$ for some integer $s$, so the greatest common divisor $d$ divides $b$. Conversely, Bézout's identity gives integers $u,v$ with $au+mv=d$. If $b=dj$, multiply this identity by $j$ to obtain $a(uj)\equiv b(\mathrm{mod}m)$. HenceFor the number of solutions, write $a=d{a}^{\prime }$, $m=d{m}^{\prime }$ and $b=d{b}^{\prime }$. The linear congruence becomes $a^{\prime }r\equiv b^{\prime }(\mathrm{mod}{m}^{\prime })$, where $a^{\prime },m^{\prime }$ are coprime integers. Multiplication by $a^{\prime }$ is invertible modulo $m^{\prime }$ by Bézout's identity, so the solutions form one residue class $r\equiv r_0(\mathrm{mod}{m}^{\prime })$. Modulo $m=d{m}^{\prime }$, these are exactlyThey are distinct: if two have the same residue class modulo $m$, then $d{m}^{\prime }$ divides $(j-\ell )m^{\prime }$, forcing $d\mid j-\ell$; with $0\le j,\ell <d$, this forces $j=\ell$. Every other solution differs from $r_0$ by a multiple of $m^{\prime }$, so these exhaust the $d$ solutions.

Finally,Combining this with the existence criterion gives the requested equivalent modular congruence.

The greatest common divisor issince $19$ and $44$ are coprime integers. Part (b) therefore gives $\boxed{1012/23=44}$ distinct $437$th powers in the nonzero multiplicative group of a finite field ${\mathbb{F}}_{1013}^{\times }$. If “powers mod $1013$” includes all residue classes, the additional value $0=0^{437}$ gives $\boxed{45}$ values including zero. The distinction is relevant because part (b) explicitly works in the nonzero group.

The maximal condition on subgroups, denoted $\max$, says that every ascending sequence $H_1\le H_2\le \cdots$ of subgroups eventually stabilizes. Suppose a subgroup $H$ were not finitely generated. Starting with the trivial subgroup, repeatedly choose an element of $H$ outside the subgroup generated so far. This produces a strictly ascending sequence, contradicting $\max$.

Conversely, suppose every subgroup is a finitely generated group. The union $H={\bigcup }_i{H}_i$ of an ascending sequence is a subgroup. A finite generating set of $H$ lies in a single $H_m$, since the sequence is ascending. Thus $H=H_m$, and $H_i=H_m$ for all $i\ge m$. We have proved

For the extension arguments, let $N◃G$ and let $\pi :G\to G/N$ be the quotient map. If $N$ and $G/N$ are finitely generated groups, choose generators $a_1,\dots ,a_r$ of $N$ and lifts $b_1,\dots ,b_s$ of generators of $G/N$. For every $g\in G$, its image is a word $w(\pi (b_1),\dots ,\pi (b_s))$, so $w(b_1,\dots ,b_s{)}^{-1}g\in N$. ThereforeHere $d$ denotes the minimal number of generators. If instead $N$ and $G/N$ satisfy the maximal condition on subgroups, take any $H\le G$. Its intersection $H\cap N$ and its image $\pi (H)$ are finitely generated by the condition in those two groups. The exact sequence $1\to H\cap N\to H\to \pi (H)\to 1$ and the preceding argument make $H$ finitely generated. The equivalence already proved now gives $\max$ for $G$. Hence both finite generation and the maximal condition are preserved by group extensions.

An infinitely generated group of finite Prüfer rank is the additive group $\mathbb{Q}$. A finite set of rational numbers lies in $D^{-1}\mathbb{Z}$ for a common denominator $D$, and its generated subgroup is cyclic: after multiplying by $D$, use the greatest common divisor of the integer numerators. Every finitely generated subgroup of $\mathbb{Q}$ therefore needs at most one generator, while $\mathbb{Z}$ needs one. But no finitely generated subgroup contains $1/(2D)$ once its elements all lie in $D^{-1}\mathbb{Z}$. Thus

If $G$ has Prüfer rank $r$, every finitely generated subgroup of any subgroup $K\le G$ is also a finitely generated subgroup of $G$, so ${\mathrm{rk}}_{\mathrm{P}}(K)\le r$. For a quotient $G/N$, let $A=⟨{\bar{g}}_1,\dots ,{\bar{g}}_k⟩$ be finitely generated and choose lifts $g_i\in G$. The subgroup $L=⟨g_1,\dots ,g_k⟩$ needs at most $r$ generators and maps onto $A$, so $d(A)\le d(L)\le r$. This proves the rank bound for every subgroup and quotient.

Now suppose $N$ and $G/N$ have Prüfer ranks $r$ and $s$. For finitely generated $H\le G$ with $H\cap N$ also finitely generated, the extension generating argument givesThe final request needs an argument even when $H\cap N$ is not finitely generated. Write $H=⟨h_1,\dots ,h_k⟩$. Choose at most $s$ elements $x_1,\dots ,x_s\in H$ whose images generate $\pi (H)$, omitting unused entries if fewer are needed. For each $h_i$, choose a word $w_i$ in these $x_j$ with the same image and setThe finitely generated subgroup $K=⟨n_1,\dots ,n_k⟩$ of $N$ has generators $y_1,\dots ,y_r$, again allowing fewer. Each original $h_i$ belongs to $⟨x_1,\dots ,x_s,y_1,\dots ,y_r⟩$, and all these new generators belong to $H$. Thus $d(H)\le r+s$ without requiring finite generation of the full intersection. Taking the supremum proves the Prüfer rank bound for extensions:

For the Fibonacci addition formula, use mathematical induction on $k$, with the assertion applying to every $n\ge 1$. At $k=2$, $F_{n+2}=F_{n+1}+F_n=F_2{F}_{n+1}+F_1{F}_n$. If the formula holds for some $k\ge 2$ and all $n$, apply it at $n+1$ and use the Fibonacci number recurrence:This is the assertion at $k+1$, completing the mathematical induction. ThusTaking $k=n\ge 2$ gives the doubling identity

For the Lucas numbers, $L_2=F_3+F_1=3$, and $L_3=F_4+F_2=4=L_2+L_1$. For $n\ge 4$, both expressions for earlier Lucas numbers are available, andHence $\boxed{L_1=1,L_2=3,L_n=L_{n-1}+L_{n-2}(n\ge 3)}$. The separate $n=3$ check matters because the defining expression for $L_1$ was given separately.

The Euclidean algorithm and the Fibonacci number recurrence give, for $n\ge 2$,Repeating reduces to $\gcd (F_2,F_1)=1$; the case $n=1$ is immediate. Therefore $\boxed{\gcd (F_n,F_{n+1})=1(n\ge 1)}$.

For $n\ge 2$, $L_n=F_n+2F_{n-1}$, so a common divisor $d$ of $F_n,L_n$ divides both $F_n$ and $2F_{n-1}$. Since $F_n,F_{n-1}$ are coprime, Bézout's identity gives integers $s,t$ with $s{F}_n+t{F}_{n-1}=1$. Multiplying by $2$ shows $d\mid 2$. Conversely any common divisor of $F_n$ and $2$ divides $L_n$. Including $n=1$, this proves the stronger greatest common divisor identity

The eigenvalue on $|0⟩$ of every power is one, and its eigenvalue on $|1⟩$ is $e^{2\pi iak/N}$. ThusIf $a$ is odd, its greatest common divisor with $N=2^n$ is one. Divisibility can therefore be cancelled, givingIn particular, the $N$ powers with $0\le k<N$ are distinct. Each is the phase gate $R_m$ with $m\equiv ak(\mathrm{mod}N)$, and multiplication by $a$ is a permutation of these residue classes. Equivalently, for any desired $m$, choose $k\equiv a^{-1}m(\mathrm{mod}N)$, where $a^{-1}$ is the modular inverse. Then $R_a^k=R_m$, using the representative $0\le k<N$ and repeated forward applications only. Thus the powers generate the entire set. Once the preceding identification procedure has found $a$, these powers can also be labelled and selected classically.

The greatest common divisor $d=\gcd (a,b)$ is the largest positive integer dividing both $a$ and $b$. To prove Bezout identity without assuming unique factorization, let $d_0$ be the least positive member ofThis set has positive members, for example $a$, so well-ordering principle supplies $d_0$. Divide $a$ by $d_0$ using Euclidean division: $a=q{d}_0+r$, $0\le r<d_0$. The remainder $r=a-q{d}_0$ is another integer linear combination of $a,b$. Minimality forces $r=0$, so $d_0\mid a$. The same argument gives $d_0\mid b$. Every common divisor divides every integer linear combination, hence divides $d_0$. Therefore $d_0$ is the greatest common divisor, andThis argument also proves that every common divisor divides the greatest common divisor.

The positive integers with the stated product-divisibility property areThe case $n=1$ is immediate. If $p$ is prime and $p\nmid a$, its only possible common positive divisor with $a$ is one. By Bezout identity, $\lambda p+\mu a=1$. Multiplying by $b$ shows that $p\mid ab$ implies $p\mid b$. This proves Euclid lemma directly. Conversely, if $n>1$ is not prime, it has a divisor $r$ with $1<r<n$. Put $s=n/r$; then $1<s<n$. Although $n\mid rs$, neither $r$ nor $s$ is divisible by $n$, disproving the property for a composite $n$.

Finally, suppose $ab=cd$ for four distinct primes. Then $a\mid cd$, so Euclid lemma gives $a\mid c$ or $a\mid d$. A prime has no positive divisor other than one and itself, so this would mean $a=c$ or $a=d$, a contradiction. Products of these two disjoint pairs cannot be equal. No form of the fundamental theorem of arithmetic was used: the required prime-divisibility fact was proved from Bezout identity.

Use the square-root encryption convention called the Rabin-Williams scheme in the Cambridge course notes. Choose distinct large primes $p,q\equiv 3(\mathrm{mod}4)$, keep them secret, and publish $N=pq$. A message block $m\in \{0,\dots ,N-1\}$ is encrypted asUsually require $\gcd (m,N)=1$; otherwise the message itself reveals a factor. For a quadratic residue $c$ modulo $p$, Euler criterion gives $c^{(p-1)/2}=1$, so $c^{(p+1)/4}$ is a square root. Compute both signs modulo each prime, then combine the four sign choices by the Chinese remainder theorem. For a unit ciphertext there are four roots modulo $N$. Message redundancy identifies the intended root; squaring alone does not identify it uniquely.

To reduce integer factorization to recovery of square roots, choose $x$ uniformly from $(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$, compute $c=x^2$, and ask the alleged decoder for any root $y$ of $c$. Conditional on $c$, the secret $x$ is uniform among its four roots, even if the decoder deterministically chooses $y$. With probability $1/2$, $y\not\equiv \pm x(\mathrm{mod}N)$. Then the signs agree modulo one prime and disagree modulo the other. Sincethe greatest common divisor factors $N$. Independent trials require an expected two successful oracle calls. If a trial's chosen $x$ is not a unit, $\gcd (x,N)$ already factors $N$. This establishes the computational equivalence between factorization and inversion of the squaring map; it does not claim that learning any partial information about a formatted message is equivalent to full inversion.

For coin flipping by telephone, Alice publishes $N$ with its factorization secret. Bob chooses uniformly a unit $x$ with $0<x<N/2$ and sends $c=x^2\mathrm{mod}N$. Alice computes the two roots $r_1,r_2$ in this half interval, selects a binary digit in which they differ, and announces a guess for that digit of Bob's $x$. Bob reveals $x$; Alice verifies its range and square, and their common bit records whether her guess was correct. Alice then reveals $p,q$, so Bob verifies the primes, product, and differing digit.

Conditional on $c$, Bob's original root is equally likely to be $r_1$ or $r_2$, so Alice's guess succeeds with probability $1/2$. Bob cannot change his answer to the other half-interval root without finding a nontrivial second square root, which would factor $N$ by the argument above. Thus, assuming factorization is hard and the prescribed sampling and completed exchange are followed,The revealed factors make the completed transcript checkable. The protocol does not prevent a party from aborting communication.

Cyclic periodicity on ${\mathbb{Z}}_N$ implies that the least positive period $r$ divides $N$: the shifts preserving the function form a subgroup of the cyclic group. Injectivity within one period says that distinct residue classes modulo $r$ have distinct function values. Write $L=N/r$.

Prepare the uniform superposition state by applying the quantum Fourier transform to $|0⟩$, and evaluate $f$ reversibly into a second quantum register. This is efficient because the given classical Boolean circuit can be converted into a reversible circuit, with its workspace cleaned by uncomputation. The resulting quantum state isMeasuring the function quantum register leaves a uniform coset state $L^{-1/2}{\sum }_{j=0}^{L-1}|x_0+jr⟩$ for some $0\le x_0<r$. The amplitude at $c$ after a quantum Fourier transform isThe finite geometric series is zero unless $c$ is a multiple of $L$, and then equals $L$. Thus a computational-basis measurement produces a uniform Fourier sampleThe exact period recovery from a Fourier sample computesA greatest common divisor is computable in time polynomial in $\log N$. The candidate is always a divisor of the true period, and equals it precisely when $s$ is coprime to $r$.

For the success flag, compute $f(\hat{r}\mathrm{mod}N)$ and compare with $f(0)$. If $\hat{r}<r$, injectivity within the first period makes these unequal. If $\hat{r}=r$, periodicity makes them equal, including $r=N$. Hence accept and output $\hat{r}$ exactly when this comparison succeeds; otherwise report failure. This is heralded exact quantum period finding when the period divides the register size, with no false acceptance. The case $r=1$ succeeds even on the sample $c=0$.

The exact success probability iswhere $\phi$ is the Euler totient function. For $r\mid N$, the prime-product formula gives $\phi (r)/r\ge \phi (N)/N$. A Rosser–Schoenfeld totient bound supplies the needed lower bound $\phi (N)/N=\Omega (1/\log \log N)$ for large $N$. Every single attempt, including verification, has the assumed polynomial-in-$\log N$ gate cost. Repeating $O(\log \log N)$ times gives constant success probability with a certified result whenever one is found.

The printed $O$ in the totient hint should be a lower-bound statement, $\Omega$. Literally, $\phi (N)=O(N/\log \log N)$ is false: at primes $N$, $\phi (N)=N-1$. Likewise the exact single-sample success probability need not be $O(1/\log \log N)$; for prime period it tends to one. The useful intended guarantee is the displayed inverse-log-log lower bound, not a universal upper bound. If an algorithm satisfying the literal success upper bound is desired, one can additionally accept an otherwise certified run only when $k=\lceil \log \log N\rceil$ independent fair bits are all zero. This retains a detectable failure flag and polynomial runtime, and has success at most $2^{-k}=O(1/\log \log N)$, but deliberately weakens the useful guarantee. The standard unsuppressed algorithm above gives the stronger intended performance. Small $N$ can be handled directly. Primary evidence for the totient lower bound is Theorem 15, equations (3.41)–(3.42), in denisevellachemla.eu/Rosser-Schoenfeld-1962.pdf .

The greatest common divisor $d=\gcd (m,n)$ is the largest positive integer dividing both $m$ and $n$. To prove Bézout's identity without assuming a factorization theorem, consider the nonempty set of positive integer linear combinationsIt contains $m$, so the well-ordering principle gives a least element $d_0=am+bn$. By Euclidean division, write $m=q{d}_0+r$ with $0\le r<d_0$. Thenis another integer linear combination. If $r>0$, it contradicts minimality, so $r=0$ and $d_0\mid m$. Applying the same argument to $n$ gives $d_0\mid n$. Conversely, every common divisor divides every integer linear combination and therefore divides $d_0$. In particular every positive common divisor is at most $d_0$. Thus $d_0=d$ andThis also proves the requested divisibility implication for any integer $k$: if $k\mid m$ and $k\mid n$, then $k\mid (am+bn)=d$.

For the scaling identity for greatest common divisors, put $D=\gcd (km,kn)$ with $k>0$. Since $kd$ divides $km$ and $kn$, $D\ge kd$. On the other hand, multiplying Bézout's identity by $k$ expresses $kd$ as $a(km)+b(kn)$, so $D\mid kd$. Positivity gives $D\le kd$. Therefore without using prime factorization,

The PDF's small superscript is essential: $f(x)=a^x\mathrm{mod}N$. Interpret $r$ as the least positive period, the multiplicative order of $a$ modulo $N$. If one permitted an unspecified nonminimal period, the answer would not be identifiable; for example, $a=1,N=8$ gives the same constant function with period one or period eight. Under the promised periodic modular-exponential interpretation, $a^r\equiv 1(\mathrm{mod}N)$, so $a$ is a unit. ThusIn particular, different residue classes modulo $r$ have different function values, which is necessary for the usual quantum period finding coset argument.

Prepare $N^{-1/2}{\sum }_x|x⟩|1⟩$ by applying the quantum Fourier transform to the first register. Use repeated squaring to precompute $a^{2^j}\mathrm{mod}N$, then multiply the value register by that known number controlled on bit $j$ of $x$. These controlled modular multiplications are reversible because $a$ is a unit; their inverses use the modular inverses of the same constants. This produces $N^{-1/2}{\sum }_x|x⟩|a^x\mathrm{mod}N⟩$ with a polynomial number of the assumed arithmetic operations. Known work registers can be uncomputed.

Measure the value register. Since $r\mid N$, its fiber is exactly one coset, and the first register becomesThe quantum Fourier transform of a periodic coset state is supported uniformly on the $r$ outcomes $c=jN/r$, $0\le j<r$. Indeed the inner geometric series ${\sum }_{\ell =0}^{N/r-1}{e}^{2\pi i\ell rc/N}$ is zero unless $(N/r)\mid c$, and each allowed amplitude has modulus $1/\sqrt{r}$.

Take two independent Fourier samples $c_1,c_2$ and returnThis is two-sample exact period recovery. The Chinese remainder theorem makes divisibility of independent uniform residues independent across the different prime divisors of $r$. For each such prime $\ell$, both $j_1$ and $j_2$ are divisible by $\ell$ with probability ${\ell }^{-2}$. ThereforeThe number-theoretic facts used here are the Chinese remainder theorem, the Euler product for the Riemann zeta function at two, and $\zeta (2)={\pi }^2/6$. The candidate can also be certified by $a^{\hat{r}}\equiv 1(\mathrm{mod}N)$: it divides the least period, so this equality holds exactly when it is the full period. Each preparation, reversible evaluation, QFT, measurement and greatest common divisor calculation has the assumed or standard polynomial time cost in $\log N$. Two runs suffice for the desired constant success probability. Quantum period finding recovers the least period with probability at least $6/{\pi }^2$ in polynomial time.

The Euclidean algorithm givesThus the greatest common divisor is $d=7$. The extended Euclidean algorithm reverses these divisions:This supplies the Bezout identity with $x=8$, $y=-11$.

To obtain all solutions of a linear Diophantine equation, subtract this particular solution from any other and divide by $7$. The result is $29(x-8)+21(y+11)=0$. Since $29$ and $21$ are coprime integers, $21$ divides $x-8$, givingEvery displayed pair satisfies the original linear Diophantine equation, so the parametrization is exhaustive.

For the modular arithmetic calculation, $21\cdot 18=378\equiv 1(\mathrm{mod}29)$, so $18$ is the modular inverse of $21$. Multiplication gives $n\equiv 25\cdot 18\equiv 15(\mathrm{mod}29)$. The admissible integers are $15+29t$ for $0\le t\le 68$, ending at $1987$; the next is $2016$. There are $\boxed{69}$ such integers.

Both relators have zero exponent sums, so abelianization gives $H_1(Y)={\mathbb{Z}}^3$, with meridian variables $x,y,z$ corresponding to $a,b,c$. The universal abelian cover has deck transformation group ${\mathbb{Z}}^3$ and coefficient group ringThe generalized Heegaard diagram gives a two-dimensional spine with one vertex, three edges and two faces. Its lifted cellular chain complex iswhere chosen lifts of the cells giveThe two columns are the abelianized Fox derivatives of $[a,bc]$ and $[ab,c]$. The Fox calculus identity gives $d_1{d}_2=0$; this can also be checked by multiplying the displayed matrices. There is no three-cell in this spine. One may use the lifted spine because its deformation retraction from $Y$ lifts to the universal abelian cover.

The maximal minors of the Alexander matrix, in row-pair order $(1,2),(1,3),(2,3)$, areTheir greatest common divisor in $R$ is $xyz-1$, since $x-1,y-1,z-1$ have no common nonunit divisor. Accordingly the multivariable Alexander polynomial isThe allowed units are $\pm x^i{y}^j{z}^k$. The single-variable specialization convention can introduce extra $(t-1)$ factors; the answer here is the genuinely multivariable Alexander polynomial.

Use the positive-sign quantum Fourier transformOrthogonality of the finite-group characters makes $F_N$ a unitary operator. Here $r$ is the least positive period. The injectivity within one period implies $r\mid N$: write $N=qr+s$, $0\le s<r$. Periodicity gives $f(s)=f(N)=f(0)$, and injectivity forces $s=0$. Put $L=N/r$.

Start with two available computational basis states $|0⟩|0⟩$. Apply $F_N$ to the first register and query the modular-addition quantum oracle:Measure the second register. For some $t\in \{0,\dots ,r-1\}$, the first register becomes the normalized coset stateThe quantum Fourier transform of a periodic coset state isIndeed, the inner geometric sum vanishes unless the Fourier label is a multiple of $N/r$. Measuring that label gives $j=sN/r$ for a uniformly random $s$. Compute, by the Euclidean algorithm,Thus exact period recovery from a Fourier sample succeeds whenever $s$ is coprime to $r$, andHere $\phi$ is the Euler totient function. The classical number-theory input is the totient lower bound from the Mertens product: for sufficiently large $m$, $\phi (m)/m\ge c/\log \log m$ for an absolute $c>0$, with the finitely many small cases handled separately. For $r=1$ recovery is certain; for $r=2$ its probability is $1/2$. The useful asymptotic probability statement is a lower bound, hence $\Omega$ notation; it can be much larger for particular periods, for example a prime period.

There is one oracle query, two Fourier transforms and two measurements. The final greatest common divisor and division use polynomial time in $\log N$. This meets the specified primitive-operation model without assuming that an arbitrary-$N$ Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently $O(\log \log N)$ times and return the least common multiple of the candidates: each candidate divides $r$, and one successful sample makes that least common multiple exactly $r$.

Write $Q=2^n$, $t=(p-1)(q-1)$ and $a=t/Q$. The easy starting state is uniform over all $n$-bit labels, so its good fraction is $a$, not $t/N$. For distinct primes one has $a\ge 1/4$. If both primes are odd, $t/N\ge (1-1/3)(1-1/5)=8/15$ and $N/Q\ge 1/2$, giving $a\ge 4/15$. If one prime is two, the other is an odd prime $q$; since $2q$ has $n$ bits, $q>2^{n-2}$, and $t=q-1\ge 2^{n-2}=Q/4$.

The uniform coprime state for a semiprime can now be prepared by one exact Grover rotation. SetPrepareUse the good subspace spanned by $|k⟩|1⟩$ with $1\le k<N$ and $\gcd (k,N)=1$. Its squared overlap with $|\Psi ⟩$ is exactly $a\lambda =1/4$. The Euclidean algorithm supplies a reversible computation of the membership predicate, including the range check; condition a sign flip on membership and the extra qubit being one, then uncompute the workspace. This implements $S_G=I-2{\Pi }_G$.

The starting-state reflection $D_{\Psi }=2|\Psi ⟩⟨\Psi |-I$ uses the inverse of its known preparation and a reflection on the all-zero state. Applying $D_{\Psi }{S}_G$ once invokes exact amplitude amplification at $\theta =\pi /6$, and givesThe extra qubit factors off, and the arithmetic workspace is returned to zero. Although the stated range includes $N$, that label is not coprime to itself, so the predicate $k<N$ is equivalent and avoids admitting labels outside the intended range.

The supplied $p,q$ determine $t$ in polynomial time; no factoring procedure is needed. Binary arithmetic, range comparison, the reversible greatest common divisor, the two starting-state reflections and the controlled sign flip all have polynomial-size circuits. Thus the construction takes polynomial time in $n$ in the ideal model allowing the specified one-qubit state preparation. Exactness uses the rotation with known amplitudes $\sqrt{\lambda },\sqrt{1-\lambda }$; with a fixed finite approximate gate library one obtains arbitrary accuracy with precision overhead, rather than an automatic promise of exact state preparation. In the ideal model the preparation succeeds with certainty, without rejection sampling. If desired, the extra $|1⟩$ can be reset by a Pauli X gate.

For an additive arithmetic function $f$, one standard form of the Turán-Kubilius inequality usesIt states, with an absolute constant,For real $f$, this also bounds the variance under the discrete uniform distribution, because centering at the actual expectation minimizes the mean square.

For the prime omega function, $f(p^k)=1$. The Mertens theorem for reciprocal primes states ${\sum }_{p\le N}1/p=\log \log N+O(1)$. The contribution of higher prime powers is bounded by ${\sum }_{p}1/(p(p-1))\le 1$, as proved in 1(a). It follows that $A_{\omega }(N)=\log \log N+O(1)$ and $B_{\omega }(N{)}^2\ll \log \log N$. Writing $L=\log \log N$, the Turán-Kubilius inequality and Chebyshev inequality therefore yieldThe bounded error in $A_{\omega }-L$ is absorbed by, for example, using the threshold $0.005L$ around $A_{\omega }$ for sufficiently large $N$.

For the multiplication table problem, call a pair $(a,b)\in [N{]}^2$ good when $\omega (a),\omega (b)\ge 0.99L$ and $\omega (\gcd (a,b))\le 0.1L$. The preceding Chebyshev inequality excludes only $O(N^2/L)$ pairs by either of the first two conditions. For the greatest common divisor condition, linearity of expectation under uniform sampling of the two coordinates givesMarkov inequality therefore excludes only another $O(N^2/L)$ pairs.

The prime factors of a product form the union of those of its factors. Consequently, for every good pair,On the other hand, apply the proved concentration estimate at $N^2$. Since $\log \log (N^2)=L+\log 2$, for large $N$ every integer $m\le N^2$ with $\omega (m)\ge 1.88L$ is exceptional there. There are only $O(N^2/L)$ such integers. Products of good pairs lie in this exceptional set; products having only bad representations are at most as numerous as the bad pairs. This proves the multiplication-table upper bound, using distinct prime factors alone:

Let $L=\lceil {\log }_{2}N\rceil$. In the Shor algorithm, first use classical arithmetic to deal with even $N$ and perfect powers, and to reject prime inputs. Perfect-power recognition and primality testing have polynomial-time classical algorithms. Factoring a perfect power $b^k$, with $b,k>1$, already gives a nontrivial factor $b$. We may therefore consider an odd composite $N$ with at least two distinct prime factors.

Choose $\alpha$ uniformly from $1<\alpha <N$ and compute its greatest common divisor with $N$ using the Euclidean algorithm. A proper nontrivial divisor ends the computation. Otherwise $\alpha$ is a unit, and the remaining task is quantum order finding. SetPrepare a uniform quantum superposition in a $t$-qubit register and use quantum modular exponentiation in a second register to obtainRepeated squaring and reversible modular multiplication implement this step with polynomially many quantum gates in $L$. Apply the inverse quantum Fourier transform to the first register and perform a quantum measurement in the computational basis, obtaining $j$. Measuring the second register first, and Fourier-transforming the resulting periodic coset, gives the same distribution of $j$.

Here is a quantitative quantum Fourier sampling bound for order finding. If $r={\mathrm{ord}}_N(\alpha )$, multiplication by $\alpha$ cycles its $r$ orbit states. The Fourier eigenstates of that cycle have eigenvalues $e^{2\pi is/r}$, and the initial state $|1⟩$ has squared overlap $1/r$ with each, for $0\le s<r$. ThereforeConditioned on a particular eigenphase $s/r$, its nearest integer outcome $j_s$ obeys $|j_s/Q-s/r|\le 1/(2Q)$ and has probability at least $4/{\pi }^2$. Indeed the absolute amplitude is $|\sin (\pi Q\delta )/(Q\sin (\pi \delta ))|$, where $\delta =s/r-j_s/Q$. For $|Q\delta |\le 1/2$, the numerator is at least $2Q|\delta |$ and the denominator at most $\pi Q|\delta |$; the limiting value at $\delta =0$ is one.

If $\gcd (s,r)=1$, the fraction $s/r$ is reduced, and $r<N$ givesUse continued-fraction recovery in quantum order finding. The relevant approximation theorem says that reduced fractions satisfying $|a/b-p/q|<1/(2q^2)$ are continued fraction convergents of $a/b$. For an input rational of $O(L)$ digits, their $O(L)$ candidates can be enumerated classically in $O(L^3)$ time, and their denominators are at most the reduced input denominator. This is the supplied continued-fraction result; discard candidate denominators exceeding $N$. A zero measurement is treated as a failed order-finding sample.

For each remaining even candidate denominator $q$, compute $z={\alpha }^{q/2}\mathrm{mod}N$ by repeated squaring, and try $\gcd (z-1,N)$ and $\gcd (z+1,N)$. Return only a divisor $d$ with $1<d<N$; otherwise repeat the quantum sample or choose another $\alpha$. This candidate-denominator gcd post-processing cannot return an incorrect factor, since its output is checked directly. When the recovered denominator is the true even multiplicative order and the square root of one is nontrivial, part (i) guarantees success. Checking ${\alpha }^q\equiv 1(\mathrm{mod}N)$ before trying the gcds is also a valid, more restrictive convention; the single-run distinction matters in part (iii).

Two further standard quantitative facts explain why repetitions remain efficient. First, for a uniformly chosen unit modulo an odd integer with at least two distinct prime divisors, the probability of a useful unit in Shor factorization is at least $1/2$: its true multiplicative order is even and ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$. To see the source of this bound, the Chinese remainder theorem for unit groups makes the prime-power components independent. Each odd-prime-power unit group is cyclic. If its 2-primary order is $2^v$, the probability of the largest possible value of $v$ is $1/2$, and the probability of any specified smaller value is at most $1/2$. Failure requires all components to have the same $v$: either all zero, making $r$ odd, or all the same positive value, making the halfway power $-1$ in every component. Conditioning on one component, the chance another component matches it is at most $1/2$, so total failure is at most $1/2$.

Second, the fraction of phase numerators coprime to $r$ is $\phi (r)/r$, where $\phi$ is the Euler totient function. The elementary totient-ratio lower bound suffices: if the distinct prime divisors are $p_1<\cdots <p_k$, then $p_j\ge j+1$ and $k\le {\log }_{2}r$. The totient product formula therefore givesThus for a good $\alpha$, the probability of sampling a coprime phase numerator with the required accuracy is at least $(4/{\pi }^2)\phi (r)/r$. This is inverse-polynomial in the input length, so polynomially many repetitions achieve any fixed success probability. The quantum Fourier transform uses $O(t^2)$ elementary rotations and Hadamard gates in the ideal gate description, and the other quantum and classical stages are polynomial in $L$.

The reduction is therefore polynomial in the bit length:A small denominator need not itself be the true multiplicative order; verification of the final factor is essential, and no guarantee is claimed for every individual sample.

For coprime integers $\alpha ,N$, the multiplicative order is the smallest positive exponentIt exists because multiplication by $\alpha$ is an element of the finite group of units modulo an integer. For the example, the successive residues areNone of the first three is one, so the order is four.

The factor extraction from an even modular order uses the factorization ${\alpha }^r-1=({\alpha }^{r/2}-1)({\alpha }^{r/2}+1)$. If the multiplicative order $r$ is even, put $z={\alpha }^{r/2}\mathrm{mod}N$. Minimality of the multiplicative order excludes $z=1$; we also require $z\ne -1(\mathrm{mod}N)$. Thus $z^2\equiv 1(\mathrm{mod}N)$ is a nontrivial square root of one. Neither $z-1$ nor $z+1$ is divisible by all of $N$. If either were coprime to $N$, its inverse modulo $N$, applied to $(z-1)(z+1)\equiv 0$, would make the other divisible by $N$, a contradiction. Hence the greatest common divisorsare proper nontrivial factors. For odd $N$, $(z-1)$ and $(z+1)$ have no common prime divisor of $N$, so these two divisors are complementary. If the initial $\alpha$ is not coprime to $N$, a proper $\gcd (\alpha ,N)$ already supplies a factor without quantum order finding.

For $N=15$ and $\alpha =7$, $r=4$ and $z=7^2\mathrm{mod}15=4$, which is neither $1$ nor $14$. The factors areThe necessary conditions for this order-based reduction are a unit $\alpha \mathrm{mod}N$, even true multiplicative order, and ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$.

Every reachable state $i$ reaches zero deterministically in $i$ steps. For $j\in E$, choose a supported lifetime $k>j$; zero can jump to $k-1$ and then count down to $j$. Thus the chain is an irreducible Markov chain on $E$. Its positive-probability first return lengths are exactly the support of $Y_1$; all other return lengths are sums of such lengths. Their greatest common divisor is therefore one by assumption, so the chain is an aperiodic Markov chain.