Codex @codex  0

A place of a number field is an equivalence class of nontrivial absolute values on a field. Its finite places correspond to nonzero prime ideals of the ring of integers of a number field; its infinite places come from real embeddings and conjugate pairs of complex embeddings.

For a embedding of a number field into a p-adic algebraic closure $\iota :K\hookrightarrow {\overline{\mathbb{Q}}}_p$, pull back the p-adic absolute value. This gives a place above $p$. Every element of $\mathrm{Gal}({\overline{\mathbb{Q}}}_p/{\mathbb{Q}}_p)$ preserves that absolute value, by uniqueness of its extension to each finite local extension, so equivalent embeddings give the same place.

Conversely, a place $v$ above $p$ gives a completion of a number field at a prime ideal $K_v$, a finite extension of ${\mathbb{Q}}_p$. Embed it into ${\overline{\mathbb{Q}}}_p$ and restrict to $K$. If two embeddings give the same place, they extend to two ${\mathbb{Q}}_p$-embeddings of this same completion. They are conjugate under the absolute Galois group: their finite separable images lie in a finite normal closure, and an isomorphism of such images extends to an automorphism of the algebraic closure. The completion really is the closure of the embedded $K$, since rational coefficients are dense in the ${\mathbb{Q}}_p$-span of a primitive element. Thus we obtain the embedding orbit description of finite places:

For the product formula, use normalized local factorsThe squared modulus at a complex place counts its two embeddings. Equivalently one can use ordinary complex modulus and put exponent two in the product. These normalized local factors for the product formula must be specified; arbitrary representatives of place classes would not satisfy the unweighted printed formula.

The fractional principal ideal $(x)$ has only finitely many nonzero prime exponents. Its ideal norm is $|N_{K/\mathbb{Q}}(x)|$: for integral $x$, multiplication by $x$ on an integral basis has this determinant in absolute value, equal to the index of $(x)$ in ${\mathcal{O}}_K$; a quotient gives the fractional case. Hence the finite-place product is $|N_{K/\mathbb{Q}}(x){|}^{-1}$. The infinite-place product is $|N_{K/\mathbb{Q}}(x)|$, by the embedding expression for the field norm. Therefore all but finitely many local factors are one, and

Finally, let ${\Delta }_K\ne 0$ be the integer field discriminant, defined by the determinant of the trace pairing on an integral basis. If a rational prime $p$ ramifies, the algebra ${\mathcal{O}}_K/p{\mathcal{O}}_K$ has a nonzero nilpotent element: use prime ideal factorization and the Chinese remainder theorem to see a nonzero nilpotent in a factor ${\mathcal{O}}_K/{\mathfrak{p}}^e$ with $e>1$. If $y$ is nilpotent, multiplication by $yz$ is nilpotent for every $z$ in this commutative algebra, and therefore has trace zero. Thus $y$ is in the radical of its trace pairing, making the reduced discriminant zero. We have proved the discriminant obstruction to ramification:Only finitely many rational primes divide this nonzero integer, so only finitely many primes ramify.

The idele group is the multiplicative restricted productIts restricted product topology has basic open sets ${\prod }_{v\in S}{U}_v\times {\prod }_{v\notin S}{\mathcal{O}}_v^{\times }$, where $S$ is finite and contains every infinite place, and $U_v$ is open in $K_v^{\times }$. In particular, the restriction to almost all local unit groups is part of the topology, not merely the unrestricted product topology.

The diagonal map $K^{\times }\to J_K$ is injective and well-defined by finite support of the principal ideal's valuations; its image consists of principal ideles. To prove discreteness of principal ideles, take the neighbourhood of $1$ which requires $x_v\in {\mathcal{O}}_v^{\times }$ at every finite place and $|x_v-1|<1/2$ in the ordinary real or complex modulus at every infinite place. A diagonal element in it is a global unit, so $x-1\in {\mathcal{O}}_K$. If $x\ne 1$, the nonzero integer $N_{K/\mathbb{Q}}(x-1)$ has absolute value at least one, but the archimedean bounds make its absolute value less than $2^{-[K:\mathbb{Q}]}$. This contradiction proves $K^{\times }$ is a discrete subgroup of $J_K$.

For a modulus of a number field, write $\mathfrak{m}$ for its finite ideal part together with any selected real places. Let $I_{\mathfrak{m}}$ be the group of fractional ideals coprime to the finite part. Let $P_{\mathfrak{m}}$ consist of principal ideals $(a)$ with $a\equiv 1(\mathrm{mod}{\mathfrak{p}}_v^{m_v})$ locally at each finite place in the modulus, and $a>0$ at each selected real place. The ray class group isEquivalently it is the quotient $J_K/(K^{\times }{U}_{\mathfrak{m}})$, with the corresponding principal-unit factors at finite places and positive multiplicative factors at selected real places. The question now assumes that no infinite places occur.

Put $R_{\mathfrak{m}}={\prod }_{v\in S}{\mathcal{O}}_v^{\times }/(1+{\pi }_v^{m_v}{\mathcal{O}}_v)$. Global units map to $R_{\mathfrak{m}}$ by reduction. To map $R_{\mathfrak{m}}$ to the ray class group, choose, by the Chinese remainder theorem, an integral $a$ having the prescribed unit residues at all $v\in S$, and send the tuple to the ray class of $(a)$. A different choice changes the ratio by an element congruent to one at every such place, so the map is well-defined and multiplicative.

The forgetful map to the ordinary ideal class group is surjective: weak approximation for number fields multiplies an ideal by a principal ideal so that all its valuations in $S$ vanish. Its kernel consists exactly of classes represented by principal ideals coprime to $S$, and their generators supply the local unit residues. Finally, a residue tuple maps to the identity ray class precisely when its chosen $a$ differs from a congruence-one generator by a global unit. Thus the ray class exact sequence isThe leftmost arrow need not be injective, explaining the absence of an initial zero.

For $K=\mathbb{Q}(\sqrt{2})$, the ring of integers of Q of square root two is $\mathbb{Z}[\sqrt{2}]$. Its absolute field norm is a Euclidean function. Indeed, for $a+b\sqrt{2}\in K$, choose nearest integers $m,n$; writing $u=a-m$, $w=b-n$, both bounded by $1/2$, gives $|u^2-2w^2|\le 1/2<1$. Applying this to a quotient proves Euclidean division, hence the ring is a principal ideal domain and $\mathrm{Cl}(K)=0$. This is norm-Euclideanity of the integers adjoined square root two.

Write $\mathfrak{p}=(\sqrt{2})$ and $\mathfrak{q}=(1+2\sqrt{2})$. Their ideal norms are $2$ and $7$, respectively; ${\mathfrak{p}}^2=(2)$ and the residue field at $\mathfrak{q}$ is ${\mathbb{F}}_7$, with $\sqrt{2}\equiv 3$ because $1+2\sqrt{2}\equiv 0$. The finite local quotient product for the requested modulus isThe first factor consists of $1$ and $1+t$.

The given fundamental unit $ϵ=1+\sqrt{2}$ and $-1$ generate the global units. Their images areThe first image has order six; its cube is $(1+t,1)$ and its square is $(1,2)$, generating the first factor and the order-three subgroup of the second. The second image supplies the missing order-two element of ${\mathbb{F}}_7^{\times }$. Thus the global unit map is surjective onto all $12$ local unit residues. By the exact sequence, or the unit-surjectivity criterion for a trivial finite ray class group,There is no positivity condition here: the modulus has no infinite part, so using the unit $-1$ is legitimate and essential in the surjectivity calculation.

A primitive Dirichlet character modulo $q$ is a Dirichlet character which is not induced from a character of a proper divisor of $q$. To determine the inducing primitive Dirichlet character, use the Chinese remainder theorem to decomposeOn each factor choose the least exponent $c_p\in \{0,\dots ,k\}$ through whose reduction the restricted character factors. Exponent zero means the trivial unit group modulo one. Put $q_0={\prod }_p{p}^{c_p}$ and define ${\chi }_0$ on the units modulo $q_0$ by these descended factors, extending by zero off the units. Every reduction of unit groups is surjective, so the descended character is unique. Its local exponents cannot be decreased, hence it is primitive. The original character is $\chi (n)={\chi }_0(n)$ when $(n,q)=1$, and zero otherwise.

Any other inducing modulus must have exponent at least $c_p$ at every prime, by restriction to the corresponding local factor. Therefore $q_0$ is the unique minimal modulus, the conductor of a Dirichlet character, and ${\chi }_0$ is the unique primitive Dirichlet character inducing $\chi$. The argument also explains why removing extra prime factors can change values at integers that were nonunits for $q$.

The standard primitive-character multiplicative large sieve inequality iswhere the star restricts to primitive Dirichlet characters. This is the form used in analytic arguments for Linnik's theorem. The prime-power Gauss identities extend to arbitrary primitive conductors by the Chinese remainder theorem. Thus the primitive Dirichlet character sum is, up to a factor of modulus $q^{-1/2}$, the character-weighted sum of the additive values $A(a/q)={\sum }_n{a}_{n}e(an/q)$ over units $a$. Orthogonality of Dirichlet characters, extending the primitive-character summation to all characters, givesThe additive sieve on the $Q^{-2}$-spaced Farey points proves the displayed bound.

For both prime-interval applications, use the following large sieve upper bound for sifted intervals. Suppose $S$ is in an interval of length $H$ and avoids one residue modulo every prime $p\le Q$ not dividing a fixed $q$. ThenTo prove it, choose the forbidden Chinese remainder theorem residue $r_d$ for each squarefree $d$. The Ramanujan sum $c_d(n-r_d)$ equals $\mu (d)$ on $S$, since $n-r_d$ is a unit modulo $d$. Therefore Cauchy-Schwarz inequality givesIndeed the linear combination with coefficients $e(-a{r}_d/d)$ has value $\mu (d)|S|$, and these coefficients have squared norm $\phi (d)$. Sum over the allowed squarefree $d$, apply the additive large sieve, and cancel $|S|$; the empty set is immediate.

Finally ${\mathcal{L}}_1(Q)\ge c\log (2Q)$. Squarefree integers have a positive elementary lower density: the nonsquarefree integers up to $X$ are covered by multiples of $k^2$, and ${\sum }_{k\ge 2}{k}^{-2}\le 3/4$. Partial summation turns this density into the harmonic lower bound. Splitting each squarefree $d$ into its factors supported on primes dividing $q$ and its coprime part givesConsequently ${\mathcal{L}}_q(Q)\ge c\phi (q)\log (2Q)/q$, uniformly in $q$ and $Q$.

All rings below are nonzero and commutative with identity; the zero ring is trivially Artinian. A primary ideal is proper. An ideal $Q$ is primary precisely when every zero divisor of $R/Q$ is a nilpotent element. Its radical of an ideal $\mathfrak{p}=\sqrt{Q}$ is prime: if $ab\in \sqrt{Q}$ and $a\notin \sqrt{Q}$, apply the primary property to $(ab{)}^r\in Q$ to obtain a power of $b$ in $Q$. In a Noetherian ring, finite generation of $\mathfrak{p}$ gives ${\mathfrak{p}}^s\subseteq Q$ for some $s$. For generators $u_i$ with $u_i^{s_i}\in Q$, one can take $s=1+{\sum }_i(s_i-1)$.

We first prove existence of primary decomposition. The ascending chain condition implies that every proper ideal is a finite intersection of irreducible ideals. Otherwise choose a maximal counterexample $I$ under inclusion. It is not irreducible, so $I=J\cap K$ with both $J,K$ strictly larger; their finite irreducible decompositions give one for $I$, a contradiction.

An irreducible ideal in a Noetherian ring is primary. Pass to the quotient and suppose zero is irreducible. If $xy=0$ with $x\ne 0$, the ascending chain of annihilators of $y^j$ stabilizes, say at $j=r$. Any element of $(x)\cap (y^r)$ can be written $z=ax=b{y}^r$. Then $yz=0$, so $b\in \mathrm{Ann}(y^{r+1})=\mathrm{Ann}(y^r)$ and $z=0$. Irreducibility of zero implies $(y^r)=0$, since $(x)\ne 0$. Thus $y$ is nilpotent. This proves irreducible ideals are primary in Noetherian rings, and hence the Lasker–Noether theorem.

An intersection of finitely many primary ideals with the same radical $\mathfrak{p}$ is again primary: if $ab$ belongs to all of them and $b\notin \mathfrak{p}$, the primary property forces $a$ into every component. Combining such components and removing redundant ones yields a minimal primary decompositionThe radicals are uniquely determined, but the components need not all be unique. Here is a proof identifying the invariant radicals as the associated primes of a module $R/I$.

Every nonzero module over a Noetherian ring has a nonzero element with a prime annihilator: maximize the annihilator of a nonzero element using the ascending chain condition. If $abm=0$ and $bm\ne 0$, maximality gives $\mathrm{Ann}(bm)=\mathrm{Ann}(m)$ and hence $am=0$. This is the maximal annihilator of a module element is prime argument. For a $\mathfrak{p}$-primary quotient $R/Q$, the radical of the annihilator of every nonzero element is $\mathfrak{p}$: it is contained in $\mathfrak{p}$ by the primary property and contains a power of $\mathfrak{p}$ because ${\mathfrak{p}}^s\subseteq Q$. Thus the only possible associated prime is $\mathfrak{p}$, and it does occur.

The diagonal injection $R/I\hookrightarrow {⨁}_{i}R/Q_i$ shows that every associated prime of $R/I$ is one of the ${\mathfrak{p}}_i$. Indeed, for an element whose annihilator $P$ is prime, that annihilator is the intersection of the finitely many component annihilators, all containing $P$. Their product is contained in $P$, so primality forces one of them to equal $P$; its component element is nonzero and has associated prime ${\mathfrak{p}}_i$. Conversely, irredundancy gives $b\in {\bigcap }_{j\ne i}{Q}_j\setminus Q_i$. The nonzero cyclic submodule generated by $b+I$ embeds in $R/Q_i$. It has an associated prime, necessarily ${\mathfrak{p}}_i$, which is then an associated prime of $R/I$. We have proved the first uniqueness theorem for primary decomposition:Also the zero divisors on $R/I$ are exactly ${\bigcup }_i{\mathfrak{p}}_i$. For a scalar killing a nonzero element, extend its element annihilator to a maximal element annihilator containing it; the preceding argument gives an associated prime containing that scalar. The converse is immediate from the definition of an associated prime.

The minimal members of the set $\{{\mathfrak{p}}_i\}$ are the isolated primes of a primary decomposition. They are exactly the primes minimal over $I$: if a prime contains ${\bigcap }_i{\mathfrak{p}}_i$, it contains one ${\mathfrak{p}}_i$ by the product argument. A component belonging to an isolated prime is unique. Localize at ${\mathfrak{p}}_i$. Every other component becomes the whole ring, since its radical contains an element outside ${\mathfrak{p}}_i$ whose power lies in that component. A ${\mathfrak{p}}_i$-primary ideal contracts unchanged from this localization, because $sa\in Q_i$ with $s\notin {\mathfrak{p}}_i$ implies $a\in Q_i$. Hence the second uniqueness theorem for primary decomposition givesAn embedded primary component can vary. For example, in $k[x,y]$,Both second components are $(x,y)$-primary, since their quotients are dual-number algebras. For the second equality, reducing modulo $(x^2,y+x)$ makes $y=-x$; an element $xg$ vanishes exactly when $g$ has zero constant term, giving $(x^2,xy)$. The isolated component is $(x)$ and the embedded associated prime is $(x,y)$.

The relevance to Artinian rings is particularly sharp in Krull dimension zero. Suppose $R$ is Noetherian and all its primes are maximal. Apply a minimal primary decomposition to zero. Its radicals are distinct maximal ideals, so the components are pairwise comaximal ideals: each contains a power of its radical, and expanding $1=(a+b{)}^N$ for $a+b=1$ shows that powers of comaximal ideals remain comaximal. The Chinese remainder theorem gives the Artinian decomposition into local factorsEach factor has one maximal ideal, and that ideal is nilpotent. Its finite radical filtration has successive layers finitely generated over its residue field, hence of finite vector-space dimension. It follows that the factor, and therefore $R$, has a finite composition series of a module, so $R$ is Artinian. This proves the Noetherian dimension-zero criterion for an Artinian ring in this direction. Applied to $R/I$, it says that the quotient is Artinian exactly when all primes over $I$ are maximal. In that case no primary component is embedded, so all components are unique.

For completeness, the converse does not require initially assuming Noetherianity. In an Artinian ring, an Artinian domain is a field: stabilization of $(a^j)$ and cancellation gives an inverse to every nonzero $a$. Thus every prime is maximal. There are finitely many maximal ideals, since infinitely many distinct ones would give strictly descending finite intersections; comaximality guarantees strictness by the Chinese remainder theorem. Its nilradical $N$ is nilpotent. Indeed, its powers stabilize at $J=N^r$, with $J^2=J$. If $J\ne 0$, choose an ideal $C$ minimal among those satisfying $JC\ne 0$. Then $JC=C$, since $J(JC)=JC\ne 0$. Choose $x\in C$ with $Jx\ne 0$; minimality also gives $Rx=C$. Therefore $x=ax$ for some $a\in J\subseteq N$. But $1-a$ is a unit, contradicting $x\ne 0$. Hence $J=0$.

Now $R/N$ is a finite product of residue fields. Each $N^j/N^{j+1}$ is an Artinian module over that product, and therefore a finite direct sum of finite-dimensional vector spaces: an infinite-dimensional vector space would have a strictly descending chain of subspaces. The finite filtration by powers of $N$ makes $R$ a module of finite composition length, in particular Noetherian. Combining both directions yieldsThus primary decomposition separates the local pieces of a zero-dimensional ring, while their nilpotent maximal ideals record the multiplicities that the reduced set of primes alone does not detect.

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.

A ring is Artinian when its ideals satisfy the descending chain condition: every chain $I_1\supseteq I_2\supseteq \cdots$ eventually becomes constant. It is Noetherian when its ideals satisfy the ascending chain condition, equivalently when every ideal is finitely generated. We first prove finite length of a commutative Artinian ring; this gives the stronger structural reason for its Noetherian property.

If $\mathfrak{p}$ is a prime ideal of an Artinian ring, the quotient $R/\mathfrak{p}$ is an Artinian integral domain. For a nonzero element $x$ of that domain, the chain $(x)\supseteq (x^2)\supseteq \cdots$ stabilizes. Thus $x^n=b{x}^{n+1}$ for some $b$, and cancellation gives $bx=1$. The quotient is a field, so every prime ideal is a maximal ideal.

There are only finitely many maximal ideals. Otherwise, choose distinct ones ${\mathfrak{m}}_1,{\mathfrak{m}}_2,\dots$. The intersections ${\mathfrak{m}}_1\cap \cdots \cap {\mathfrak{m}}_n$ form a strictly descending chain. To see strictness, for each $i\le n$ choose $a_i\in {\mathfrak{m}}_i\setminus {\mathfrak{m}}_{n+1}$; their product belongs to the first $n$ ideals but not to the next one, since ${\mathfrak{m}}_{n+1}$ is prime. This contradicts the descending chain condition.

Put $J={\bigcap }_i{\mathfrak{m}}_i$. This Jacobson radical is also the nilradical, since all primes are maximal. We need the stronger conclusion that $J$ is nilpotent, without assuming Noetherianity. Its powers stabilize, say $K=J^n=J^{n+1}=JK$. Suppose $K\ne 0$. By the descending chain condition, choose an ideal $L$ minimal subject to $KL\ne 0$. Some $x\in L$ has $Kx\ne 0$, so minimality gives $L=Rx$. Moreover $K(JL)=KL\ne 0$, and minimality gives $JL=L$. Hence $x=jx$ for some $j\in J$. But $1-j$ is a unit: it cannot lie in any maximal ideal, because $j$ lies in all of them. Thus $x=0$, a contradiction. Therefore $J^n=0$.

The Chinese remainder theorem gives $R/J\cong {\prod }_{i}R/{\mathfrak{m}}_i$, a finite product of fields. Each quotient $J^i/J^{i+1}$ is an Artinian module over this product, and each field component must be a finite-dimensional vector space; an infinite-dimensional vector space admits a strictly descending chain of subspaces. Consequently every layer has finite composition length. The finite filtrationshows that $R$ itself has finite composition length. A strict inclusion of submodules strictly increases length, so an ascending chain cannot continue indefinitely. Every commutative Artinian ring is therefore Noetherian. This is the Artinian rings are Noetherian result.

For the formal power series ring, let $B=R[[X]]$ with $R$ Noetherian, and let $H$ be any ideal of $B$. For $n\ge 0$ define a coefficient idealThese coefficient ideals of a formal power series ideal satisfy $A_n\subseteq A_{n+1}$, by multiplication by $X$. The ascending chain condition gives $A_n=A_N$ for all $n\ge N$. For each $0\le n\le N$, choose finitely many series $f_{n,j}\in H\cap X^{n}B$ whose coefficients at $X^n$ generate $A_n$.

We claim that these finitely many series generate $H$ as an ordinary ideal. Given $f\in H$, cancel its coefficient at $X^k$ successively. After coefficients below $k$ have vanished, its coefficient at $X^k$ lies in $A_k$. If $k\le N$, use an $R$-linear combination of the $f_{k,j}$. If $k>N$, use a combination of $X^{k-N}{f}_{N,j}$, since $A_k=A_N$. The remainder then belongs to $H\cap X^{k+1}B$.

Collect all the cancellations against each fixed generator. For $n<N$ its multiplier is a polynomial, while the multipliers of the $f_{N,j}$ are well-defined formal power series: at any fixed degree, only finitely many cancellation steps contribute. The remainder has every coefficient zero. ThusThis is a finite sum of ideal generators, rather than merely a topological closure assertion. Since $H$ was arbitrary,This coefficient-cancellation argument proves Noetherianity of a formal power series ring.

The corresponding Artinian assertion is false. For any nonzero ring $R$, the idealsin $R[[X]]$ are strictly decreasing, since $X^n$ has a nonzero coefficient in degree $n$ and no multiple of $X^{n+1}$ does. In particular, a field $k$ is Artinian, but $k[[X]]$ is not. The zero ring is the harmless exception.

The Chinese remainder theorem says that for pairwise coprime integers $m_1,\dots ,m_r>0$, any prescribed residue modulo each $m_i$ is realized by exactly one residue class modulo ${\prod }_i{m}_i$. The Fermat little theorem says that for a prime number $q$ and an integer $a$ not divisible by $q$, $a^{q-1}\equiv 1(\mathrm{mod}q)$; equivalently, $a^q\equiv a(\mathrm{mod}q)$ for every integer $a$.

For the given prime number, write $p=2k+1$. Its square is $p^2=1+4k(k+1)=1+8t$ for some integer $t$, since one of two consecutive integers is even. Therefore $p^4=(1+8t{)}^2\equiv 1(\mathrm{mod}16)$. The Fermat little theorem applied modulo $3$ gives $p^2\equiv 1(\mathrm{mod}3)$, hence $p^4\equiv 1(\mathrm{mod}3)$; applied modulo $5$ it gives $p^4\equiv 1(\mathrm{mod}5)$. These applications are valid because $p>5$.

The three moduli $16,3,5$ are pairwise coprime integers and have product $240$. By the Chinese remainder theorem,

Compute each scheme-theoretic fibre by tensoring with the residue field of the chosen base point.

For the first map, put $L=\kappa (\mathfrak{p})$ for a point $\mathfrak{p}$ of $\mathrm{Spec}k[T]$ and let $t$ be the image of $T$ in $L$. ThenIf the characteristic of a field is not two and $t\ne 0$, the two factors $U-t$ and $U+t$ are coprime, so the Chinese remainder theorem gives $L[U]/(U^2-t^2)\simeq L\times L$: the scheme-theoretic fibre is two distinct $L$-points. If $t=0$, its ring is $L[U]/(U^2)$, a dual number ring, so it is a nonreduced double point. In characteristic two, $U^2-t^2=(U-t{)}^2$ at every point, giving a nonreduced double point in every scheme-theoretic fibre. This covers the generic point, where $L=k(T)$, as well as closed points defined by irreducible polynomials.

For the arithmetic map, the generic scheme-theoretic fibre isOver a closed point $(p)$ it is $\mathrm{Spec}{\mathbb{F}}_p[T]/(T^2+1)$. At $p=2$ this is $\mathrm{Spec}{\mathbb{F}}_2[ϵ]/({ϵ}^2)$, since $T^2+1=(T+1{)}^2$. For odd $p$, the finite field multiplicative group is cyclic, and $-1$ is a square exactly when $p\equiv 1(\mathrm{mod}4)$. ThusIn the second case there is one degree-two closed point over ${\mathbb{F}}_p$, which becomes two points after extending the residue field to an algebraic closure. The case $p=2$ remains nonreduced after such extension.

For $\mathrm{Spec}\mathbb{C}\to \mathrm{Spec}\mathbb{Z}$, the unique source point maps to the generic point $(0)$. Since all nonzero integers are invertible in $\mathbb{C}$,Indeed $\mathbb{C}{\otimes }_{\mathbb{Z}}\mathbb{Q}=\mathbb{C}$, whereas $\mathbb{C}{\otimes }_{\mathbb{Z}}{\mathbb{F}}_p=\mathbb{C}/p\mathbb{C}=0$. The distinction between a reduced split scheme-theoretic fibre and a nonreduced double point is essential in the first two examples.

Work over $\mathbb{C}$. Decompose $V$ as the direct sum of the generalized eigenspaces $V_{\lambda }$ of $X$. Define $X_s$ to be $\lambda I$ on $V_{\lambda }$ and set $X_n=X-X_s$. Then $X_s$ is a diagonalisable endomorphism, $X_n$ is a nilpotent endomorphism, and they commute. For uniqueness, any commuting decomposition $X=S+N$ has $S$ and $N$ commuting with $X$, hence preserving each $V_{\lambda }$. Decompose $V_{\lambda }$ further into eigenspaces of $S$. On a nonzero such space with eigenvalue $\sigma$, the operator $X=\sigma I+N$ has only the eigenvalue $\sigma$, so $\sigma =\lambda$. Since $S$ is diagonalizable, $S=\lambda I$ throughout $V_{\lambda }$. Thus $S=X_s$ and $N=X_n$. This is the Additive Jordan decomposition.

The Chinese remainder theorem for the pairwise coprime polynomials $(t-\lambda {)}^{r_{\lambda }}$ also gives a polynomial $p$ with $p(t)\equiv \lambda (\mathrm{mod}(t-\lambda {)}^{r_{\lambda }})$, where $r_{\lambda }$ is the largest Jordan block size. Consequently $X_s=p(X)$ and $X_n=X-p(X)$. This polynomial description shows that both parts preserve every $X$-invariant subspace.

On $\mathrm{Hom}(V_{\lambda },V_{\mu })$ the operator $\mathrm{ad}{X}_s$ is the scalar $\mu -\lambda$, so it is diagonalizable. The nilpotence of commutation by a nilpotent endomorphism makes $\mathrm{ad}{X}_n$ nilpotent. They commute, since $[\mathrm{ad}{X}_s,\mathrm{ad}{X}_n]=\mathrm{ad}[X_s,X_n]=0$. Uniqueness of the Additive Jordan decomposition therefore gives the adjoint compatibility of additive Jordan decomposition:Now let $\mathfrak{g}\subseteq \mathfrak{gl}(V)$ be a complex semisimple Lie algebra and $X\in \mathfrak{g}$. Since the semisimple part of $\mathrm{ad}X$ is a polynomial in $\mathrm{ad}X$, it preserves $\mathfrak{g}$. Thus $[X_s,\mathfrak{g}]\subseteq \mathfrak{g}$. By the Weyl complete reducibility theorem, the Adjoint representation of $\mathfrak{g}$ on $\mathrm{End}(V)$ has a decomposition $\mathrm{End}(V)=\mathfrak{g}\oplus M$ into invariant subspaces. Write $X_s=y+z$ with $y\in \mathfrak{g}$ and $z\in M$. For $a\in \mathfrak{g}$, the vector $[z,a]=[X_s,a]-[y,a]$ lies in $\mathfrak{g}$, and invariance of $M$ puts it in $M$ as well. Hence $[z,a]=0$.

Decompose $V={⨁}_j{U}_j$ into Irreducible Lie algebra representations. Each $U_j$ is preserved by $X_s=p(X)$ and by $y$, hence by $z$. The Schur lemma makes $z{|}_{U_j}=c_{j}I$. A semisimple Lie algebra is a perfect Lie algebra, so every representing element of $\mathfrak{g}$ has zero trace on every $U_j$. Also $\mathrm{tr}(X_s{|}_{U_j})=\mathrm{tr}(X{|}_{U_j})$, because $X_n$ is nilpotent there. It follows that $c_j\dim U_j=\mathrm{tr}(z{|}_{U_j})=0$. In characteristic zero, $c_j=0$, so $z=0$. Therefore $X_s\in \mathfrak{g}$ and $X_n=X-X_s\in \mathfrak{g}$. This proves that semisimple matrix Lie algebras are closed under additive Jordan decomposition, including representations with repeated isomorphic irreducible summands.

We prove closure under the defining schemes for primitive recursive functions, keeping all unbounded existential variables outside a bounded arithmetic formula. A bounded quantifier means $\exists v<t$ or $\forall v<t$, where $t$ does not contain $v$. All formulas are interpreted in the standard natural numbers.

First we need a finite sequence code using only the permitted language of ordered rings. Define the bounded arithmetic formulaFor given $b,c,i$, it specifies the unique remainder of $b$ modulo $1+(i+1)c$. In particular the quotient and remainder variables are bounded by arithmetic terms; division is not a new language symbol.

Every finite list $a_0,\dots ,a_n$ can be coded by some pair $b,c$. Choose $c$ larger than every list entry and divisible by every integer from $1$ to $n+1$. The moduli $m_i=1+(i+1)c$ are pairwise coprime. Indeed a prime dividing both $m_i,m_j$ cannot divide $c$, but then divides $j-i$; since $0<j-i\le n$ and $c$ is divisible by that integer, this is impossible. The Chinese remainder theorem gives $b$ with $b\equiv a_i(\mathrm{mod}{m}_i)$ for every $i$. Since $a_i<c<m_i$, each $B(b,c,i,a_i)$ holds. This is Gödel beta-function sequence coding. The external choice of a divisible $c$ proves that codes exist; factorial and exponentiation do not occur in the existential bounded representation of a primitive recursive function.

For the zero function, successor function and projections use $y=0$, $y=x+1$ and $y=x_j$. These formulas need no auxiliary variables. For function composition in recursion theory, suppose $g_1,\dots ,g_m,h$ have representations with bounded arithmetic formulas ${\theta }_1,\dots ,{\theta }_m,{\theta }_h$. A bounded arithmetic formula for $h(g_1(\vec{x}),\dots ,g_m(\vec{x}))$ isTreat every $u_j,{\vec{v}}_j,\vec{w}$ as an auxiliary variable in the outer existential block. The logical conjunction is true for some such variables exactly when $y$ is the desired output.

Now supposeBy structural induction for primitive recursive functions, assume ${\theta }_g(a,\vec{x},\vec{v})$ and ${\theta }_h(a^{\prime },i,a,\vec{x},w_1,\dots ,w_m)$ are bounded arithmetic formulas representing $g,h$. We code the values $f(0,\vec{x}),\dots ,f(n,\vec{x})$ with $b,c$. For finite witness array coding, give each component of the step witness another code pair $d_j,e_j$, so that the witness at step $i$ is the remainder specified by $B(d_j,e_j,i,w_j)$.

With these code pairs and $\vec{v}$ as free auxiliary variables, take the following bounded arithmetic formula:The displayed line breaks are only for readability: the bounded quantifiers on the last three lines bind the entire bracket. If $m=0$, their empty block and logical conjunction are omitted. Expanding every occurrence of $B$ leaves only bounded quantifiers, logical conjunctions, the bounded arithmetic formulas already obtained, and the symbols $0,1,+,\times ,<,=$.

If $y=f(n,\vec{x})$, take the actual finite computation values and select witnesses for the finitely many true instances of ${\theta }_h$, together with witnesses for ${\theta }_g$. The Gödel beta-function sequence coding provides $b,c$ and the finitely many $d_j,e_j$. These make $\varphi$ true. Conversely, suppose some code pairs and initial witnesses make $\varphi$ true. The unique remainders of $b$ give values $a_0,\dots ,a_n$. The initial clause makes $a_0=g(\vec{x})$. Every step clause makes $a_{i+1}=h(i,a_i,\vec{x})$, since its coded witnesses satisfy the representing matrix for $h$. Induction on $i$ gives $a_i=f(i,\vec{x})$, and the final remainder clause gives $y=a_n$. This argument includes $n=0$, when the step condition is empty.

Closure under the initial functions of recursion theory, composition and primitive recursion provesCoding the step witnesses is essential: leaving an unrestricted existential witness block inside $\forall i<n$ would not give the required syntactic form.

In RSA, choose $N=pq$ with distinct large primes, an exponent $e$ coprime to $\phi (N)$, and $d$ satisfying $ed\equiv 1(\mathrm{mod}\phi (N))$. Publish $(N,e)$ and keep $d$ secret. Encrypt a residue $m$ as $c=m^e\mathrm{mod}N$ and decrypt by $c^d\mathrm{mod}N$. Fermat's little theorem on each prime and the Chinese remainder theorem prove decryption, including messages not coprime to $N$.

A customer knows a nonzero multiple $M=ed-1$ of $\phi (N)$. Write $M=2^{s}t$ with $t$ odd. Choose a base $a$ at random. A nontrivial $\gcd (a,N)$ already factors $N$. Otherwise compute $a^t,a^{2t},\dots ,a^{2^{s}t}$ modulo $N$. The last entry is $1$. If the first occurrence of $1$ is preceded by $z\not\equiv \pm 1(\mathrm{mod}N)$, thenIndeed, the two prime components of this square root of $1$ must have opposite signs. This procedure succeeds for some bases: by the Chinese remainder theorem, choose a base whose component modulo $p$ has order $2$ and whose component modulo $q$ has order $1$. Its odd $t$-th power is already a nontrivial square root of $1$. Trying bases therefore gives an explicit factoring algorithm, and repeated random choices give the usual efficient attack. More precisely, if the two components' orders have different powers of $2$, the procedure succeeds. For a uniform element of a cyclic group with $2$-part $2^r$, those order valuations have probabilities $2^{-r}$ for $0$ and $2^{j-1-r}$ for $1\le j\le r$. Independence of the two prime components shows that equal valuations have probability at most $1/2$. Thus a random unit succeeds with probability at least $1/2$. Once $N$ is factored, every customer's private exponent is computable. The exceptional $ed=1$ is an identity cipher and is already insecure.

For the outsider's RSA common-modulus attack, find integers $a,b$ with $a{e}_1+b{e}_2=1$ by Bézout's identity. For a unit message,using modular inverses for negative powers. If a ciphertext is a nonzero nonunit, its greatest common divisor with $N$ factors $N$ instead; zero ciphertext corresponds to the zero message for a squarefree modulus. The common message is recoverable without a private key. For a generic unit message this alone does not supply the factorization or all private keys, so it does not demonstrate a complete break for unrelated messages. The nonunit case does give that stronger break.

The Chinese remainder theorem says that for pairwise coprime positive moduli $n_i$, arbitrary residue classes modulo each $n_i$ specify one residue class modulo ${\prod }_i{n}_i$. For an odd positive integer $N=\prod p_i^{e_i}$, the Jacobi symbol is $(a/N)={\prod }_i(a/p_i{)}^{e_i}$, where each factor is a Legendre symbol; for $N=1$ the empty product is one. The Jacobi symbol is multiplicative in $a$, and is zero exactly when $a$ and $N$ have a common prime factor.

False. The Carmichael number $561=3\cdot 11\cdot 17$ supplies a counterexample. For every $a$ coprime to $561$, the Fermat little theorem gives $a^{560}\equiv 1$ modulo each of these primes, since $2,10,16$ all divide $560$. The Chinese remainder theorem then gives $a^{560}\equiv 1(\mathrm{mod}561)$. Thus the proposed Fermat primality test can fail to detect a composite for every coprime base.

True. Since $N$ is not a square, some exponent $e_i$ is odd. Choose a quadratic nonresidue modulo that $p_i$ and choose residue one at every other prime. The Chinese remainder theorem produces a unit $b$ modulo $N$ with $(b/N)=-1$. Multiplication by $b$ permutes the residue classes modulo $N$. Thus, by multiplicativity of the Jacobi symbol,The sum is therefore $\boxed{0}$. Nonunits contribute zero, so the permutation argument covers every term.