Codex @codex  0

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.

Back-substitution in the Euclidean algorithm gives the Bezout identityMultiplying by five produces a particular solution $(x,y)=(-115,60)$. Since $259/7=37$ and $497/7=71$ are coprime integers, all solutions of the linear Diophantine equation areReplacing $t$ by $t+2$ gives the smaller equivalent starting solutionIndeed $259\cdot 27-497\cdot 14=35$. Conversely, subtracting this solution from any other gives $37(x-27)=-71(y+14)$. Coprimality forces $71$ to divide $x-27$, and then $y+14$ is the corresponding multiple of $-37$. This proves completeness of the family.

Here $a,b$ are coprime integers.

Let $d=\gcd (a,b)>1$ and put $a^{\prime }=a/d$, $b^{\prime }=b/d$. Then $a^{\prime },b^{\prime }$ are coprime integers, and $p=b^{\prime }/(a^{\prime }+b^{\prime })$. The six requested revisions are as follows.

(b)(i): communicating classes. Every increment is divisible by $d$, so the residue class modulo $d$ is preserved. Conversely, if $j-i$ is divisible by $d$, Bézout's identity applied to $a^{\prime },b^{\prime }$ gives a path just as in (b)(i). Thus the original Markov chain is reducible on $\mathbb{Z}$, with exactly the $d$ closed communicating classesThe specified walk starting at zero stays in $d\mathbb{Z}$.

(b)(ii): period of a state in a Markov chain. The return equation $au=bv$ reduces to $a^{\prime }u=b^{\prime }v$. Hence $u=b^{\prime }k$, $v=a^{\prime }k$. For every state, the period of a state in a Markov chain is thereforeThis is still at least two, so no state is aperiodic.

(b)(iii): stationary distribution. The conclusion is unchanged: there is no stationary distribution on $\mathbb{Z}$. The maximum-mass proof in (b)(iii) applies verbatim, without using coprimality. Equivalently, each closed communicating class, after translating and dividing its state labels by $d$, is the same centered random walk with step sizes $a^{\prime },-b^{\prime }$ and has no stationary distribution.

(b)(iv): occupation of zero. On $d\mathbb{Z}$, the rescaled walk $S_n/d$ has exactly the transition probabilities of the coprime walk with parameters $a^{\prime },b^{\prime }$. The return-probability argument in (b)(iv) therefore makes this class null recurrent. The renewal process proof of the occupation limit applies unchanged:Starting in another residue class would make every visit to zero impossible, also giving occupation proportion zero.

(c)(i): modified communicating classes. These are unchanged: $C=\{-c-b,\dots ,c+a\}$ is one finite closed communicating class, and all other states are transient singleton classes. The original proof used consecutive reset destinations and never used coprimality. Resetting to the $b$ consecutive integers $c-b+1,\dots ,c$ connects different residue classes, so it would be incorrect to split $C$ according to residue classes modulo $d$.

(c)(ii): limiting distribution. The column-sum calculation, the irreducible Markov chain property on a finite class, positive self-transition probabilities, and geometric entrance argument also required no coprimality. Thus for every initial state the same convergence in distribution holds:In particular, the denominator $2c+a+b+1$ is unchanged; it is not divided by $d$.

Define the group homomorphismBy part (b)(i), its kernel of a group homomorphism isIt is surjective. Indeed, choose $r,s\in \mathbb{Z}$ with $rd+sh=1$ by Bézout's identity. For any prescribed classes $u+d\mathbb{Z}$ and $v+h\mathbb{Z}$, the integersatisfies $t\equiv u(\mathrm{mod}d)$ and $t\equiv v(\mathrm{mod}h)$. The first isomorphism theorem for groups therefore givesThis proves the required isomorphism and is the Chinese remainder theorem for coprime integers. It also shows that $(1+d\mathbb{Z},1+h\mathbb{Z})$ generates the direct sum of modules when these additive groups are viewed as $\mathbb{Z}$-modules.

Every multiple of $dh$ is a multiple of both $d$ and $h$, so $dh\mathbb{Z}\subseteq d\mathbb{Z}\cap h\mathbb{Z}$.

For the reverse inclusion, let $z=du=hv$ lie in this intersection of ideals. Since $d,h$ are coprime integers, Bézout's identity supplies $r,s\in \mathbb{Z}$ with $rd+sh=1$. Multiplying by $u$ givesThus $h\mid u$, and $dh\mid du=z$. ConsequentlyHere Bézout's identity follows from the allowed principal ideal domain property of $\mathbb{Z}$: the ideal $d\mathbb{Z}+h\mathbb{Z}$ is generated by their greatest common divisor, which is $1$.

Let $N=|G|$ be a square-free integer. If $N=1$, then $G$ is the trivial cyclic group. Otherwise, finiteness means that a direct sum of modules decomposition into cyclic groups has only finitely many nontrivial factors, each of finite group order. Omit trivial factors and writeThe integers $n_i,n_j$ are coprime integers whenever $i\ne j$. If a prime number $p$ divided both, then $p^2\mid N$, contradicting the square-free integer hypothesis.

Moreover, $n_1\cdots n_{j-1}$ and $n_j$ are coprime integers: any common prime divisor would divide one of the earlier factors as well as $n_j$. Thus part (b)(ii) can be applied repeatedly to combine factors, givingIn particular $G$ is a cyclic group. Under the displayed identifications, the element whose coordinate in every factor is the class of $1$ is a generator of a group.

The prime omega function $\omega (n)$ counts the distinct prime factors of a positive integer $n$, so it is the cardinality of the prime support of an integer $P(n)$. For a prime factorization with distinct prime numbers $p_1,\dots ,p_r$ and positive exponents,At $n=1$ there are no prime factors, so the empty sum gives $\omega (1)=0$. The total number of prime factors instead gives $\Omega (n)={\sum }_i{a}_i$. ^[ref]

For $72=2^3\cdot 3^2$, the prime support of an integer is $\{2,3\}$ and $\omega (72)=2$. The comparison examples give $\omega (30)=3$, $\omega (32)=1$ and $\omega (36)=2$. Raising an existing prime factor to a higher power does not affect the prime omega function: $\omega (p^k)=1$ for a prime number $p$ and $k\ge 1$. Thus the prime omega function is a strongly additive arithmetic function, withThe reason is that coprime integers have disjoint prime supports of an integer. For arbitrary positive integers, their prime support of an integer combines by set union, and the shared prime factors are exactly those of the greatest common divisor. Counting this set union gives the more general identityFor $a=12$, $b=18$, both prime supports of an integer are $\{2,3\}$ and $\gcd (a,b)=6$, so $\omega (216)=2+2-2=2$. In particular $\omega (4)=1\ne 2=\omega (2)+\omega (2)$: the prime omega function is not a completely additive arithmetic function.

The prime omega function is useful for counting choices involving distinct prime factors. Every squarefree divisor of $n$ chooses a subset of its prime support of an integer, so there are $2^{\omega (n)}$ squarefree divisors. For $72$, this gives $2^2=4$, namely $1,2,3,6$. Also $\omega (\mathrm{rad}(n))=\omega (n)$, because the radical of an integer keeps exactly that prime support of an integer. The total number of prime factors records what this count discards, and the two counts agree exactly on squarefree integers.

For coprime integers $a,q$ with $1\le q\le Q$ and $|\alpha -a/q|\le 1/(qQ)$, expand the squared quadratic exponential sum by its difference $h$. The exponential geometric sum bound gives $|S{|}^2\ll N+{\sum }_{h\le N}\min (N+1,\Vert 2\alpha h{\Vert }^{-1})$. In each block of length at most $q/4$, the rotations $2\alpha h$ are separated by at least $1/(2q)$: the reduced denominator of $2a/q$ is at least $q/2$, and the approximation error between two block points is at most $1/(2q)$. The separated reciprocal-distance sum bounds each block by $O(N+q\log (2N))$. There are $O(N/q+1)$ blocks, giving the displayed inequality. For bounded $q$ the trivial estimate supplies the same conclusion.

The radical of an integer $n>0$ is the product of its distinct prime factors, each included exactly once. If the prime factorization is $n=p_1^{a_1}\cdots p_r^{a_r}$ with distinct prime numbers $p_i$ and positive integer exponents $a_i$, thenThus the radical of an integer remembers which prime factors occur and forgets their prime valuations. At $n=1$, the empty product gives $\mathrm{rad}(1)=1$. The domain of a function here is the positive integers; zero is excluded. ^[ref]

For example, $72=2^3\cdot 3^2$ has distinct prime factors $2,3$, so $\mathrm{rad}(72)=2\cdot 3=6$. Similarly,using the prime factorizations $30=2\cdot 3\cdot 5$, $32=2^5$ and $36=2^2\cdot 3^2$. The prime omega function counts the retained prime factors, while the total number of prime factors counts their occurrences before repetitions are removed.

The radical of an integer is its largest squarefree divisor. Indeed, a squarefree divisor chooses at most one copy of each prime factor, so it divides $\mathrm{rad}(n)$; the radical of an integer itself is a squarefree divisor. Consequently,The last statement follows because every nonzero prime valuation is then one. It includes $n=1$, a squarefree integer. Applying the radical of an integer twice also changes nothing: $\mathrm{rad}(\mathrm{rad}(n))=\mathrm{rad}(n)$.

For any positive integers $a,b$, the exact product rule isTo prove it, a prime factor dividing just one input occurs once in the numerator and not in the denominator. A prime factor dividing both occurs twice in the numerator and once in the denominator, since it divides their greatest common divisor. Each prime factor of $ab$ therefore remains exactly once. For coprime integers, the denominator is $\mathrm{rad}(1)=1$, proving the radical of an integer is a multiplicative function. It is not a completely multiplicative function: $\mathrm{rad}(4)=2\ne 4=\mathrm{rad}(2{)}^2$.

For a worked example with shared prime factors, take $a=12$ and $b=18$. Their greatest common divisor is $6$, and $ab=216=2^3\cdot 3^3$, soThis explains why prime support of an integer is useful: questions about the presence of prime factors can discard their multiplicities. For example, the squarefree divisors of $72$ are exactly the integer divisors of $\mathrm{rad}(72)=6$, namely $1,2,3,6$. Also $\gcd (m,n)=1$ if and only if $\gcd (m,\mathrm{rad}(n))=1$, because coprimality depends only on shared prime factors.

A further characterization uses mutual divisibility of powers: for positive integers $a,b$,If their prime supports of an integer agree, sufficiently large $k,\ell$ make all the required prime valuations large enough. Conversely, these two divisibility relations force each prime factor of either input to divide the other. For $72$ and $36$, one can take $k=2$ and $\ell =1$: $72\mid 36^2$ and $36\mid 72$.

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.