Codex @codex  0

An additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for coprime integers $m,n$; a completely additive arithmetic function satisfies this for all positive $m,n$. In either case $f(1)=0$. The Fundamental theorem of arithmetic gives $f(n)={\sum }_{p^k\parallel n}f(p^k)$, where $p^k\parallel n$ means that the prime valuation of $n$ at $p$ is exactly $k$.

Under the discrete uniform distribution on $[N]$, the expectation of the indicator function of $p^k\parallel n$ isThe formula remains valid when $p^{k+1}>N$. Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:

For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here $\omega$ is the prime omega function and $\Omega$ is the total number of prime factors. The expectation is bounded independently of $N$, sinceThus Markov inequality gives vanishing probability on every diverging scale:

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)$.

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.

For pairwise coprime integers $m_1,\dots ,m_r$, put $M={\prod }_i{m}_i$. The Chinese remainder theorem states that reduction gives an isomorphismEquivalently, every system $x\equiv a_i(\mathrm{mod}{m}_i)$ has one solution modulo $M$.

For existence, let $M_i=M/m_i$. Since $\gcd (M_i,m_i)=1$, choose $u_i$ with $u_i{M}_i\equiv 1(\mathrm{mod}{m}_i)$. Thenhas every required residue: modulo $m_j$, all terms except the $j$th vanish and the remaining term is $a_j$. For uniqueness, if $x$ and $y$ have the same residues, every $m_i$ divides $x-y$. Pairwise coprimality then makes $M$ divide $x-y$. Thus the simultaneous solution exists and is unique modulo $M$.

An arithmetic function $f$ is multiplicative if $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime integers. If $g(n)={\sum }_{d\mid n}f(d)$ and $(m,n)=1$, every positive integer divisor of $mn$ is uniquely $d_1{d}_2$ with $d_1\mid m$ and $d_2\mid n$. Henceso $g$ is multiplicative.

The Möbius function is defined by $\mu (1)=1$, $\mu (n)=0$ if the square of a prime number divides $n$, and $\mu (n)=(-1{)}^r$ if $n$ is a product of $r$ distinct prime numbers. Coprime integers have disjoint sets of prime factors, so this definition immediately gives $\mu (mn)=\mu (m)\mu (n)$ when $(m,n)=1$.

For $n=p_1^{a_1}\cdots p_r^{a_r}>1$, only the square-free divisors contribute, and thereforeFor $n=1$ the sum is $1$. Thus $1\ast \mu =\epsilon$ in the language of Dirichlet convolution. Convolving $g=1\ast f$ with $\mu$ gives the Möbius inversion formula

If $f(n)=n$, its divisor sum is the sum-of-divisors function. Conversely, if $g(n)=n$, Möbius inversion givesusing the standard divisor identity for the Euler totient function. Therefore the two requested answers are

The Chinese remainder theorem says that if the positive integers $m_1,\dots ,m_r$ are pairwise coprime and $M={\prod }_i{m}_i$, then for arbitrary residue classes $a_i(\mathrm{mod}{m}_i)$ there is a unique residue class $x(\mathrm{mod}M)$ satisfyingEquivalently, reduction is a ring isomorphism

For existence, put $M_i=M/m_i$. Pairwise coprimality gives $\gcd (M_i,m_i)=1$, so Bézout's identity supplies an integer $u_i$ with $u_i{M}_i\equiv 1(\mathrm{mod}{m}_i)$. Thenhas the required residues, because every term except the $i$th is divisible by $m_i$. If $x$ and $y$ are two solutions, each $m_i$ divides $x-y$. Pairwise coprimality then implies that their product $M$ divides $x-y$, proving uniqueness modulo $M$.

The multiplicative order of $\alpha$ modulo $N$ is the least positive integer $r$ such thatIt exists because $\alpha$ and $N$ are coprime integers.

Suppose that $r$ is even andThe minimality of $r$ also gives ${\alpha }^{r/2}\not\equiv 1(\mathrm{mod}N)$. Sincethe factor extraction from an even modular order yieldsas a nontrivial factor of $N$; equivalently one may also compute $\gcd ({\alpha }^{r/2}+1,N)$. Thus the required conditions are that $r$ be even and that ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$.

An arithmetic function $f$ is multiplicative when $f(1)=1$ and $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime. If $m$ and $n$ are coprime, every divisor $d$ of $mn$ has a unique factorization $d=d_1{d}_2$ with $d_1\mid m$ and $d_2\mid n$. Hence the Dirichlet convolution of multiplicative functions satisfiesand $(f\star g)(1)=1$, so it is multiplicative.

Let $\epsilon$ be the identity for Dirichlet convolution, with $\epsilon (1)=1$ and $\epsilon (n)=0$ for $n>1$. The Möbius function satisfies $\mu \star 1=\epsilon$. Therefore, using commutativity and associativity,This is the Möbius inversion formula.

The Möbius function is defined by $\mu (1)=1$ and, for $n>1$,It is a multiplicative arithmetic function: $\mu (mn)=\mu (m)\mu (n)$ whenever $m$ and $n$ are coprime.

The summand $\mu (d{)}^2/\varphi (d)$ is multiplicative, so its divisor sum is multiplicative. For a prime power $p^a$ with $a\ge 1$, only $d=1,p$ contribute andMultiplying these local identities over the prime divisors of $n$ gives

For the final claim, choose distinct primes $p_0,\dots ,p_k$. The moduli $p_j^2$ are pairwise coprime, so the Chinese remainder theorem gives an integer $a$ satisfyingEvery positive integer $n\equiv a(\mathrm{mod}{\prod }_j{p}_j^2)$ then has $p_j^2\mid n+j$. HenceThere are infinitely many positive representatives of this congruence class.

If $m$ and $n$ are coprime, every divisor of $mn$ is uniquely $ab$ with $a\mid m$ and $b\mid n$. Hence, for a multiplicative arithmetic function $f$,

The Möbius function is $\mu (n)=0$ if a prime square divides $n$, and $\mu (n)=(-1{)}^r$ if $n$ is a product of $r$ distinct primes. The Euler totient function $\varphi (n)$ counts residues modulo $n$ coprime to $n$. From the prime factorizations,Both sides of the second identity are multiplicative, and at a prime power $p^a$,Therefore

The Dedekind factorization theorem says that, when a rational prime $p$ does not divide the index of an order $\mathbb{Z}[\theta ]\subseteq {\mathcal{O}}_K$, a factorizationof the minimal polynomial modulo $p$ gives

Let $K=\mathbb{Q}(\sqrt{d})$ with square-free $d$, and let $p$ be odd. The resulting splitting of rational primes in a quadratic field is:

Finally suppose $d>0$ and
$\alpha =A/C+(B/C)\sqrt{d}$ has norm $-1$, with integers
$A,B,C$ chosen coprime. ThenIf an odd $p\equiv 3(\mathrm{mod}4)$ ramified, then $p\mid d$. Reduction modulo $p$ gives
$A^2\equiv -C^2(\mathrm{mod}p)$. Since $-1$ is not a square modulo such a prime, $p\mid A,C$. Dividing the equation's divisibility shows $p\mid B$ as well (use that square-free $d$ has $p$-adic valuation one), contradicting coprimality. Hence no prime $p\equiv 3(\mathrm{mod}4)$ ramifies.

Start two registers in $|0⟩|0⟩$. Apply ${\mathrm{QFT}}_N$ to the first and then reversibly evaluate $f$ into the second, obtainingThe evaluation can be implemented by repeated squaring and reversible modular multiplication using a number of elementary arithmetic operations polynomial in $\log N$.

Measure the second register. Because $f$ is injective within one period and $r\mid N$, the first register becomes a uniformly weighted periodic cosetThe quantum Fourier transform of a periodic coset state followed by measurement returnsReduce the rational number $c/N$ to lowest terms. Sinceits denominator is $q=r/\gcd (s,r)$. Test whether $a^q\equiv 1(\mathrm{mod}N)$ by repeated squaring. The promised injectivity means that $r$ is the least positive period, and $q\mid r$, so this congruence holds exactly when $q=r$. The test therefore certifies whether the run succeeded; this is heralded exact quantum period finding when the period divides the register size.

One run succeeds with probabilitybecause success is equivalent to $s$ being coprime to $r$. A standard estimate for the Euler totient function gives $\phi (r)/r\ge C/\log \log r$ for all sufficiently large $r$, with the finitely many smaller cases absorbed by changing the positive constant $C$. Repeating independently $O(\log \log N)$ times therefore makes the probability that every run fails at most $1/2$. Every step, including the repetitions and the classical verification, takes time polynomial in $\log N$.

For coprime integers $a,N$ with $N>1$, the multiplicative order of $a$ modulo $N$ is

Suppose that the positive integer $n$ is a decisive number. For every prime number $p<\sqrt{n}$, the composite number $p^2$ satisfies $1<p^2<n$. It therefore cannot be coprime to $n$, so $p\mid n$.

The product of all prime numbers below $\sqrt{n}$ consequently divides $n$. Taking natural logarithms givesChanging the strict endpoint can remove at most one prime term. By part b, for every sufficiently large $n$ the right-hand side is at least, for example, $\sqrt{n}/13$. This is impossible for sufficiently large $n$, sinceThus every decisive number lies below one fixed bound, and only finitely many integers can do so.

A reduced fraction $a/b$ has coprime integers $a,b$ and positive denominator $b$. Distinct reduced fractions with denominators at most $Q$ differ by at least $Q^{-2}$, since their difference has a nonzero integer numerator over a denominator at most $Q^2$.

The two-isogeny descent quartics associated with square classes $2$ and $-2$ on $Y^2=X^3+24X^2+64X$ have no rational points. A rational solution can be scaled to integral $W,U,V$ with coprime integers $U,V$. If $U$ is odd, reduction modulo sixteen gives $2$ or $10$ for the positive class, and $14$ or $6$ for the negative class; none is a quadratic residue. If $U=2u$ is even, then $V$ is odd and the right side is $32(\pm u^4+3u^2{V}^2\pm V^4)$, with the same sign on the two signed terms. The bracket is odd, so its 2-adic valuation is exactly five, impossible for a nonzero square. These two parity cases exhaust primitive solutions.