Codex @codex  0

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.

Because $\gcd (m,n)=1$, choose $u,v\in \mathbb{Z}$ with $um+vn=1$ by Bézout's identity. Thensatisfies $c\equiv a(\mathrm{mod}m)$ and $c\equiv b(\mathrm{mod}n)$. Any two simultaneous solutions differ by a multiple of both coprime integers and hence by a multiple of $mn$. This proves the two-modulus Chinese remainder theorem.

The three congruences reduce toThe first two give $x\equiv 17(\mathrm{mod}35)$; imposing the last gives

We prove the claim by structural induction for primitive recursive functions. A formula is bounded when every quantifier is a bounded quantifier; this is a Delta-0 formula. The graphs of the initial functions have quantifier-free definitions:

Suppose $f(\mathbf{x})=g(h_1(\mathbf{x}),\dots ,h_m(\mathbf{x}))$ and the graphs of $g,h_1,\dots ,h_m$ have existential bounded definitions. Introduce variables $u_1,\dots ,u_m$ for the intermediate values and conjoin the graph formulasPulling all unrestricted existential witnesses to the front leaves a bounded matrix, so the required form is preserved by composition.

For primitive recursion, use Gödel beta-function sequence coding. The relationis bounded in the language of ordered rings. Given any finite sequence $a_0,\dots ,a_n$, choose $c$ larger than all its entries and divisible by $1,\dots ,n+1$. The moduli $1+(i+1)c$ are pairwise coprime, so the Chinese remainder theorem supplies $b$ with $\beta (b,c,i)=a_i$ for every $i\le n$.

Supposeand the induction hypothesis gives existential bounded graph formulas for $g$ and $h$. Then $y=f(\mathbf{x},n)$ exactly when there are $b,c$ coding values $a_0,\dots ,a_n$, together with a common witness bound $W$, such that:Write each $a_i$ using $\beta (b,c,i)$, bound the variables representing $a_i$ by $1+(n+1)c$, and bound every witness used by the graph formulas for $g$ and $h$ by $W$. All quantifiers checking the displayed finite recursion are then bounded; only $b,c,W$ and the finitely many outer coding witnesses are unrestricted existential variables. Conversely, any code passing these bounded checks satisfies the recursion equations, and induction on $i\le n$ forces its $i$th entry to be $f(\mathbf{x},i)$. This proves the existential bounded representation of a primitive recursive function.

For each place of a number field $v$, let $K_v$ be the corresponding completion, and for finite $v$ let ${\mathcal{O}}_v$ be its valuation ring. The adele ring is the restricted productIts restricted product topology has basic open sets ${\prod }_v{U}_v$, where every $U_v\subseteq K_v$ is open and $U_v={\mathcal{O}}_v$ at all but finitely many finite places.

First take $K=\mathbb{Q}$. The neighborhoodof zero meets the diagonal copy of $\mathbb{Q}$ only in zero: a rational number lying in every ${\mathbb{Z}}_p$ is an integer, and the only integer in the indicated real interval is zero. Thus $\mathbb{Q}$ is discrete in ${\mathbb{A}}_{\mathbb{Q}}$.

Every rational adele is congruent modulo $\mathbb{Q}$ to an element ofIndeed, the finitely many negative $p$-adic principal parts can be removed simultaneously by subtracting a rational number, using the Chinese remainder theorem; subtracting an integer then moves the real component into $[0,1]$. This set is compact by the compactness of $[0,1]$, the compactness of every ${\mathbb{Z}}_p$, and the Tychonoff theorem. Its image covers the quotient, so ${\mathbb{A}}_{\mathbb{Q}}/\mathbb{Q}$ is compact.

Now choose a $\mathbb{Q}$-basis of the number field $K$. The given topological isomorphismidentifies the additive pair $({\mathbb{A}}_K,K)$ with $({\mathbb{A}}_{\mathbb{Q}}^n,{\mathbb{Q}}^n)$. A finite product of discrete subgroups is discrete, andis compact.

The idele group iswhere the distinguished subgroup at a finite place is ${\mathcal{O}}_v^{\times }$. It carries the corresponding restricted product topology on the idele group. The inclusion $j:J_K\to {\mathbb{A}}_K$ is continuous: the inverse image of a basic adelic open set is locally a product of open subsets of $K_v^{\times }$, and outside finitely many places every idele component already belongs to ${\mathcal{O}}_v^{\times }\subseteq {\mathcal{O}}_v$.

It is not a homeomorphism onto its image. Let $p_i$ be the $i$th rational prime and define the idele $x^{(i)}$ to equal $p_i$ at the place over $p_i$ and $1$ everywhere else. In the adele topology, $x^{(i)}\to 1$: the difference is zero at every fixed place once $i$ is large, while $p_i-1\in {\mathbb{Z}}_{p_i}$ at the single moving place. In the idele topology the sequence does not converge to $1$, because the open neighborhoodcontains no $x^{(i)}$: its $p_i$-component has positive valuation and is not a unit. Hence the inverse of $j$ on its image is not continuous.

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.

By the Chinese remainder theorem, $b^{n-1}\equiv 1(\mathrm{mod}n)$ iff it holds modulo every $p_j$. Since $n-1=p_j{r}_j-1\equiv r_j-1(\mathrm{mod}{p}_j-1)$ and the order of $b$ modulo $p_j$ divides $p_j-1$, this is equivalent to ${\mathrm{ord}}_{p_j}(b)\mid r_j-1$ for every $j$.

For Rabin cryptosystem, choose primes $p,q\equiv 3(\mathrm{mod}4)$, publish $N=pq$, and encrypt $x$ as $x^2\mathrm{mod}N$. The factors let the receiver take square roots modulo $p$ and $q$ and combine them using the Chinese remainder theorem; redundancy identifies the intended one of four roots.

For RSA cryptosystem, choose $N=pq$, select $e$ coprime to $\phi (N)$ and $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. Encrypt $x$ as $x^e$ and decrypt by raising to $d$ modulo $N$. Rabin inversion is provably equivalent to factoring, while ordinary RSA lacks that reduction; Rabin's disadvantage is its fourfold decryption ambiguity.

The Bezout identity states that for integers $a,b$, not both zero, there are integers $r,s$ such thatIf the prime number $p$ divides $ab$ but does not divide $a$, then $\gcd (p,a)=1$. Thus $rp+sa=1$ for some integers $r,s$, and multiplication by $b$ givesBoth terms on the right are divisible by $p$, so $p\mid b$. Hence

If $\gcd (m,n)=1$, choose $r,s$ with $rm+sn=1$. Thensatisfies $x\equiv a(\mathrm{mod}m)$ and $x\equiv b(\mathrm{mod}n)$. If $x,x^{\prime }$ are two simultaneous solutions, both $m$ and $n$ divide $x-x^{\prime }$. Coprimality implies $mn\mid x-x^{\prime }$, so the solution is unique modulo $mn$. This proves the two-modulus Chinese remainder theorem.

Let $p$ be odd and supposeThen $p^d\mid (x-1)(x+1)$. Since $\gcd (x-1,x+1)$ divides $2$, the odd prime $p$ cannot divide both factors. The full power $p^d$ must therefore divide one of them, givingThese are distinct, so there are exactly two solutions.

For an odd integerthe Chinese remainder theorem identifies a solution modulo $n$ with independent solutions modulo the $k$ prime powers. Each component has two choices, hence

For $n=2^d$, there is one solution when $d=1$ and two when $d=2$. If $d\ge 3$, a solution $x$ is odd, and of the consecutive even integers $x-1,x+1$, exactly one is divisible by $4$. The 2-adic valuations therefore have minimum one; for their sum to be at least $d$, the other must be at least $d-1$. Thus $x\equiv \pm 1(\mathrm{mod}{2}^{d-1})$, giving the four distinct classesConsequently the answer is

Put $F(m)=m(m+2)(m+6)$ and let $\rho (d)$ be the number of roots of $F$ modulo $d$. For squarefree $d$, the Chinese remainder theorem givesIndeed, for $p\ge 5$ the three roots $0,-2,-6$ are distinct. Counting $m\le X$ in each of the $\rho (d)$ residue classes givesConsequently a suitable sieve distribution isThis is the polynomial root density in a sieve calculation.

In the Rabin cryptosystem, the public key is $N=pq$ and encryption sends an encoded message $m$ toKnowing $p,q$, the receiver finds the two square roots modulo each prime and combines them with the Chinese remainder theorem to obtain four roots modulo $N$; prescribed redundancy identifies the intended one.

Omicron hasThe Chinese remainder theorem determines $m^2$ uniquely modulo $N{N}^{\prime }$ (assuming the independently generated moduli are coprime; a nontrivial gcd would itself factor them). Since $1\le m<N<N^{\prime }$, one has $m^2<N{N}^{\prime }$, so this residue is the ordinary integer $m^2$. Taking its positive integer square root recovers $m$.

This does not normally decrypt another ciphertext sent under only one modulus. The recovered pair reveals no nontrivial square root collision modulo that modulus and hence supplies no factorization; breaking a single Rabin instance remains equivalent to factoring its modulus.

Distinct prime-power ideals are pairwise comaximal. For comaximal ideals, product equals intersection, so induction givesThe Chinese remainder theorem therefore gives the ring isomorphism

The ideal approximation theorem, proved by applying this Chinese-remainder map one prime power deeper, suppliesEquivalently, $v_{P_i}(\alpha )=m_i$ at every prime dividing $I$.

Since $(\alpha )\subseteq I$, the fractional idealis an integral ideal and $I{I}^{\prime }=(\alpha )$ is a principal ideal. At every $P_i\mid I$,
$v_{P_i}(I^{\prime })=v_{P_i}(\alpha )-m_i=0$, so $I+I^{\prime }={\mathcal{O}}_K$.

Choose $\beta \in I$ and $\gamma \in I^{\prime }$ with $\beta +\gamma =1$. Then
$\alpha ,\beta \in I$. For any $x\in I$,Thusso every ideal of ${\mathcal{O}}_K$ has a generating set of two elements.

The Lagrange theorem for polynomial congruences says that if $p$ is prime and $f\in \mathbb{Z}[X]$ has degree $d$ with at least one coefficient not divisible by $p$, thenhas at most $d$ incongruent solutions modulo $p$.

The Chinese remainder theorem states that for pairwise coprime $m_1,\dots ,m_r$, every systemhas exactly one solution modulo $M={\prod }_i{m}_i$. For two moduli, choose $u,v$ with $um+vn=1$ by Bezout identity. Thenis congruent to $a$ modulo $m$ and to $b$ modulo $n$. If $x,y$ are two solutions, both $m$ and $n$ divide $x-y$; coprimality makes $mn$ divide $x-y$. This proves existence and uniqueness for two factors, and induction proves the general statement.

Nowand $12^3+1=1729$, so $x=12$ is a solution. For $1\le x<12$, one has $0<x^3+1<1729$, so no such positive integer can satisfy the congruence. Hence the smallest isModulo $7,13,19$, the roots are respectivelyEach list has three elements, and the Chinese remainder theorem combines the choices independently. Therefore the number of solutions with $1\le x\le 1729$ is

The Chinese remainder theorem says that for pairwise coprime positive integers $m_i$, the mapis a bijection. For two moduli, choose $u,v$ with $um+vn=1$; thenhas residues $a$ modulo $m$ and $b$ modulo $n$. Uniqueness follows because the difference of two solutions is divisible by both coprime moduli, hence by their product. Induction proves the general case.

The two given congruences are compatible modulo $\gcd (6,8)=2$, and checking modulo $\mathrm{lcm}(6,8)=24$ gives

Write $d=2^r{3}^{s}m$ with $(m,6)=1$. Use the Chinese remainder theorem to chooseThen $4a^2+9b^2\equiv 1$ modulo each of the pairwise coprime factors $2^r$, $3^s$, and $m$, hence modulo $d$.

The maximum isThe product of two fields $K\times L$ attains it: its only nonzero proper ideals are $K\times 0$ and $0\times L$, and both are maximal ideals.

For the upper bound, suppose ${\mathfrak{m}}_1$ and ${\mathfrak{m}}_2$ are distinct maximal ideals of $R$. Their intersection cannot be nonzero, since a nonzero proper ideal is maximal and cannot be properly contained in either of two distinct maximal ideals. Hence ${\mathfrak{m}}_1\cap {\mathfrak{m}}_2=0$. Also ${\mathfrak{m}}_1+{\mathfrak{m}}_2=R$, so the Chinese remainder theorem givesBoth factors are fields, and this product has exactly two maximal ideals. Thus a third maximal ideal is impossible.

The Ostrowski theorem says that every nontrivial absolute value on a field defined on $\mathbb{Q}$ is equivalent either to the usual absolute value or to $|\cdot {|}_p$ for a unique prime $p$.

Let an absolute value on the number field $K$ extend $|\cdot {|}_p$. Its valuation ring determinesa prime ideal satisfying $\mathfrak{p}\cap \mathbb{Z}=(p)$. Conversely, each prime $\mathfrak{p}$ above $p$ defines the normalized absolute valuewhere $e_{\mathfrak{p}}=v_{\mathfrak{p}}(p)$. It restricts to $|\cdot {|}_p$. The correspondence between extensions and primes follows either from the valuation ring or from local factorization and extended absolute values; distinct primes give inequivalent valuations. Thus these $|\cdot {|}_{\mathfrak{p}}$ are exactly the extensions, up to equivalence.

For the tensor-product assertion, choose a primitive element of a field extension $\alpha$ for $K/\mathbb{Q}$, with minimal polynomial $f$. Because number fields are separable, over ${\mathbb{Q}}_p$ it factors into distinct irreduciblesindexed by the primes $\mathfrak{p}\mid p$. The Chinese remainder theorem givesThe $i$th factor is the completion of a number field at a prime ideal $K_{{\mathfrak{p}}_i}$. Under these identifications the isomorphism is the natural diagonal map $x\otimes a\mapsto (ax{)}_{\mathfrak{p}}$, proving the p-adic tensor decomposition of a number field

Write squarefree $n=\prod p$. For each $p\mid n$, either $p\mid a$, when both sides vanish modulo $p$, or Fermat's theorem applies. Since $p-1\mid \varphi (n)$ and $k\equiv 1(\mathrm{mod}\varphi (n))$, it gives $a^k\equiv a(\mathrm{mod}p)$. The Chinese remainder theorem combines these congruences to give $a^k\equiv a(\mathrm{mod}n)$.

The Chinese remainder theorem identifiesThus a class is a unit exactly when its image modulo every $p_i$ is nonzero, equivalently when no $p_i$ divides a representative.

Products of Eilenberg–MacLane spaces satisfywhere the last isomorphism uses the Chinese remainder theorem. This space is $2$-connected, so the Hurewicz theorem identifiesThe assumed surjection on $H_3$ is an isomorphism because the group is finite. Hence $f$ is an isomorphism on ${\pi }_3$; all other homotopy groups of the source and target vanish. Thus $f$ is a weak homotopy equivalence, and the Whitehead theorem for Kan complexes makes it a homotopy equivalence.

Let $P=p_1\cdots p_n$ and $A=\mathbb{Z}/P\mathbb{Z}=R_0$. By the Chinese remainder theorem, $A\cong {\prod }_i{\mathbb{F}}_{p_i}$, so ${\mathrm{length}}_A(A)=n$.

If a positive-degree monomial contains both $t_i$ and $t_j$ with $i\ne j$, then it vanishes: Bezout identity gives $u{p}_i+v{p}_j=1$, while both $p_i$ and $p_j$ annihilate that monomial. Thus the degree-$d$ component for $d\ge 1$ isand every summand has length one. Hence every $R_d$ has length $n$, including $d=0$, and