Codex @codex  0

For a finite extension $E/K$ of number fields, the inverse different is the fractional idealThe different ideal is its inverse. The trace pairing is nondegenerate because extensions of number fields are separable, so this definition gives a full fractional ideal. The inclusion ${\mathcal{O}}_E\subseteq {\mathfrak{D}}_{E/K}^{-1}$ shows that ${\mathfrak{D}}_{E/K}$ is integral.

Write its prime ideal factorization as ${\mathfrak{D}}_{E/K}={\prod }_{\mathfrak{P}}{\mathfrak{P}}^{d_{\mathfrak{P}}}$. For $\mathfrak{P}$ above $\mathfrak{p}$, with ramification index $e_{\mathfrak{P}}$ and residue characteristic $\ell$, the different exponent and tame ramification theorem saysThe equivalence uses the separability of finite residue-field extensions. In particular, $d_{\mathfrak{P}}=0$ precisely at unramified prime ideals; in the wild case $d_{\mathfrak{P}}\ge e_{\mathfrak{P}}$. This theorem does not require a Galois extension. The relative discriminant is the norm of the different ideal:For $K=\mathbb{Q}$, this gives $|D_E|=N({\mathfrak{D}}_{E/\mathbb{Q}})$.

Now take ${\alpha }^3=m$ and $K=\mathbb{Q}(\alpha )$. For any prime number $q\mid m$, the square-free integer hypothesis makes $X^3-m$ an Eisenstein polynomial at $q$. It is therefore irreducible, and $K$ is a pure cubic number field of degree $3$. Since $\alpha$ is an algebraic integer, $A=\mathbb{Z}[\alpha ]$ is an order in a number field. The discriminant of elements of a number field for its basis $1,\alpha ,{\alpha }^2$ isFor example, the resultant of $X^3-m$ and $3X^2$ is $27m^2$, and the degree-three sign in the polynomial discriminant is negative. If $I=[{\mathcal{O}}_K:A]$, the discriminant-index formula for an integral lattice givesOnly prime numbers dividing $3m$ can therefore divide $I$.

For $q\mid m$, the Eisenstein polynomial gives a totally ramified extension of ${\mathbb{Q}}_q$ of degree $3$. Thus $K$ has a unique prime ideal $\mathfrak{P}$ above $q$, with ramification index $3$ and residue-field degree $1$. Since $q\ne 3$, this is tame ramification, and the different exponent and tame ramification theorem gives $d_{\mathfrak{P}}=2$. Hence $v_q(D_K)=2$. Comparing with $v_q(-27m^2)=2$ in the discriminant-index formula for an integral lattice yields $v_q(I)=0$.

At $3$, use the shifted Eisenstein polynomial of $\beta =\alpha -m$:Because $3\nmid m$, the constant term is divisible by $3$. Moreover,when $3\nmid m$: the factors $m-1$ and $m+1$ cannot both be divisible by $3$. The hypotheses therefore give $v_3(m^3-m)=1$, so the translated polynomial is an Eisenstein polynomial at $3$. The resulting completion is a totally ramified extension of degree $3$, with residue-field degree $1$, and its ramification index is divisible by the residue characteristic. Thus its different exponent is at least $3$.

It follows that $v_3(D_K)\ge 3$. But $v_3(-27m^2)=3$, soforces $v_3(I)=0$ and $v_3(D_K)=3$. No prime number divides $I$. We have proved the integral basis of a nonexceptional pure cubic field:Using local Eisenstein polynomials here only establishes the local ramification indices; it does not assume that $\mathbb{Z}[\alpha ]$ is already the full ring of integers of a number field.

The extended Euclidean algorithm givesBack-substituting in these equations produces the Bezout identityThus one integer solution is $\boxed{x=12,y=-7}$. In fact, subtracting this Bezout identity from any other solution and using that $17$ and $29$ are coprime integers gives all solutions: $x=12+29t$, $y=-7-17t$, where $t\in \mathbb{Z}$.

For the modular arithmetic calculation, $29$ is a prime number and $17$ is coprime to it, so Fermat little theorem gives $17^{28}\equiv 1(\mathrm{mod}29)$. Since $138=5\cdot 28-2$, and the preceding Bezout identity identifies $12$ as the modular multiplicative inverse of $17$, we obtainConsequently the least positive representative is $\boxed{28}$.

Eisenstein's criterion. Let $f(X)=a_n{X}^n+\cdots +a_0\in \mathbb{Z}[X]$ be a nonconstant primitive polynomial. If a prime number $p$ satisfies $p\nmid a_n$, $p\mid a_j$ for $0\le j<n$, and $p^2\nmid a_0$, then $f$ is an irreducible polynomial over $\mathbb{Q}$.

To prove the Eisenstein criterion, suppose a nontrivial factorization exists over $\mathbb{Q}$. Gauss lemma for polynomials gives $f=gh$ with $g,h\in \mathbb{Z}[X]$ of positive degree. Their leading coefficients are not divisible by $p$, because their product is $a_n$. Reduction modulo $p$ therefore preserves both degrees, andSince the only irreducible factor of the right side is $X$, both reduced factors are nonzero monomials of positive degree. Their constant coefficients are consequently divisible by $p$. This would make $p^2\mid g(0)h(0)=a_0$, a contradiction.

For the requested polynomial, shift the variable by one. The binomial theorem givesIt is monic, all coefficients below the leading one are divisible by $p$, and the constant coefficient is $p$, not divisible by $p^2$. The Eisenstein criterion proves irreducibility of this shifted polynomial. The substitution $X\mapsto X+1$ is an automorphism of $\mathbb{Q}[X]$, with inverse $X\mapsto X-1$, so it preserves nontrivial factorizations. HenceThis is the cyclotomic polynomial for a prime index.

The auxiliary Higman group $Q$ has no nontrivial finite quotients of a group. One can use this permitted property directly, but there is a short verification. In any finite quotient, let $n_i$ be the order of the image of $a_i$. Since conjugation sends $a_{i+1}$ to its square, $n_{i+1}$ must be odd. If some $n_i>1$, choose the least prime number $p$ dividing any $n_i$. It is odd. Conjugation by the preceding generator givesThe multiplicative order of $2$ modulo $p$ is therefore a divisor of $n_{i-1}$. It is greater than one and divides $p-1$ by the Fermat little theorem, so it has a prime divisor smaller than $p$. That prime also divides $n_{i-1}$, contradicting the choice of $p$. Hence every $n_i=1$ and the quotient is trivial.

Given any finitely presented group $P$, form $\hat{P}=P\ast ⟨v⟩$, and apply part (a) to the word $w=v$. This word is nontrivial by the normal form theorem for a free product, so the output $J=\hat{P}(v)$ contains $P$ by the embedding already proved.

To check its finite quotients, let $f:J\to F$ be any group homomorphism to a finite group. The image of the copy of $Q$ is trivial by the preceding property. The identifications $u_j=a_3^{j+1}{a}_1{a}_3^{-(j+1)}$ make all $f(u_j)$ trivial. Thus the equations $u_j^{-1}c{u}_j=g_j$ give, in the image,Since $f(c)=f(z)$, this forces $f(x_i)=1$ for all generators of $\hat{P}$, including $v$. The defining word $c=[v,z]$ then has trivial image, so $f(z)=f(d)=1$ as well. Every generator of $J$ has trivial image. ThereforeThis uses the concrete construction of part (a), not an assumption that arbitrary quotients preserve an embedding of $P$.

The Fermat-Euler theorem states that for an integer $a$ and a positive integer $n$ with $\gcd (a,n)=1$,where the Euler totient function $\phi (n)$ counts the residue classes coprime to $n$. For $n\ge 2$, choose a reduced residue system $r_1,\dots ,r_{\phi (n)}$. Multiplication by the unit modulo n $a$ preserves coprimality and is injective on these residue classes: $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$ implies $r_i\equiv r_j(\mathrm{mod}n)$, because $a$ has a multiplicative inverse modulo $n$. It therefore permutes the reduced residue system, givingThe product is also a unit modulo n, so it can be cancelled. This proves the Fermat-Euler theorem. For $n=1$ every modular congruence is automatic; one may use $\phi (1)=1$.

For a prime number $p$, the Euler totient function has value $\phi (p)=p-1$. Thus $a^{p-1}\equiv 1(\mathrm{mod}p)$ whenever $p\nmid a$. Multiplying by $a$, and treating $p\mid a$ separately, gives the all-integer version of Fermat's little theorem:Finally, Wilson theorem states that for every prime number $p$, $\boxed{(p-1)!\equiv -1(\mathrm{mod}p)}$. Its converse is also true: an integer $n>1$ is prime exactly when $(n-1)!\equiv -1(\mathrm{mod}n)$. For the converse, any proper divisor $1<d<n$ would divide both $(n-1)!$ and $n$, contradicting that congruence.

Suppose $X^2\equiv -1(\mathrm{mod}p)$. Then $X$ is a unit modulo n for modulus $p$, and Fermat's little theorem impliesSince $p$ is an odd prime number, $1$ and $-1$ are distinct residue classes. Therefore $(p-1)/2$ is even, and $p\equiv 1(\mathrm{mod}4)$.

Conversely, put $q=(p-1)/2$. Pair each integer $j\in \{1,\dots ,q\}$ with $p-j$ in the factorial. Wilson theorem yieldsWhen $p\equiv 1(\mathrm{mod}4)$, $q$ is even, so $X=q!$ satisfies $X^2\equiv -1(\mathrm{mod}p)$. This proves the first supplementary law for quadratic reciprocity without assuming a primitive root. HenceThe two solutions are $q!$ and $-q!$ modulo $p$: their difference is nonzero, and factoring $X^2-Y^2$ shows that a degree-two polynomial over the field of residues modulo $p$ has no further roots.

Split the factorial at $h$, using $k=p-1-h$:By Wilson theorem, this is $-1$. Therefore $h!k!\equiv (-1{)}^{k+1}(\mathrm{mod}p)$. If the prime number $p$ is odd, then $h+k=p-1$ is even, so $(-1{)}^k=(-1{)}^h$ andFor $p=2$, the signs $1$ and $-1$ are identical modulo $2$, and the two possibilities $(h,k)=(0,1),(1,0)$ also give the same result. The empty product convention $0!=1$ includes the endpoint cases. This is the complementary factorial congruence.

A pointed category has a zero object, both initial and terminal. Factoring through that object gives a zero morphism $0_{A,B}$ between any two objects. In this paper a semi-additive structure means commutative-monoid enrichment: every hom-set is a commutative monoid with additive zero, and composition distributes over addition in both variables. No existence of finite products in a category is included in this last definition. This convention matters for the final one-object example; under the stronger convention requiring finite biproducts, that example would not be a semi-additive category.

Let $c_{A,B}:A+B\to A\times B$ be the given canonical isomorphism. Transfer the coproduct injections across $c_{A,B}$, so $A\times B$ is also a coproduct in a category, with injectionsWrite ${\nabla }_B:B\times B\to B$ for the morphism whose composites with $i_1,i_2$ are both $1_B$. For $f,g:A\to B$, define the biproduct-induced addition of morphisms byThe zero is the existing zero morphism. We verify the laws from the universal properties, without assuming addition in advance.

All finite canonical maps from coproducts to products are isomorphisms, by induction from the binary ones and the zero object. Thus both $(B\times B)\times B$ and $B\times (B\times B)$ are ternary coproducts in a category. The two iterated fold maps to $B$ agree on each of the three injections, hence are equal. Applying this to $⟨f,g,h⟩$ gives associativity. The interchange $B\times B\to B\times B$ swaps the two injections, so its composite with ${\nabla }_B$ is ${\nabla }_B$, giving commutativity. Finally $⟨f,0⟩=i_{1}f$, so $f+0=f$, and similarly $0+f=f$.

Precomposition is additive because $⟨f,g⟩u=⟨fu,gu⟩$. For $v:B\to C$, the morphisms $v{\nabla }_B$ and ${\nabla }_C(v\times v)$ agree on both injections, so they agree; consequently $v(f+g)=vf+vg$. Composition with a zero morphism is zero. This proves the commutative-monoid enrichment.

It is unique. In any such enrichment, the additive zero morphisms agree with the pointed ones, since each map to or from the zero object belongs to a singleton hom-set. The projections of $i_1{p}_1+i_2{p}_2$ from $A\times B$ are respectively $p_1,p_2$ by bilinearity, soFor $A=B$, composing on the left by ${\nabla }_B$ and on the right by $⟨f,g⟩$ forces the displayed formula for $f+g$. Thus the biproducts determine exactly one such enrichment.

For the last part, the underlying one-object category has endomorphism monoid $(\mathbb{N},\cdot )$, including $0$, and identity $1$. Its usual addition gives a commutative-monoid enrichment. Any permutation $\sigma$ of the prime numbers extends, by unique prime factorization, to a multiplicative monoid automorphism ${\varphi }_{\sigma }:\mathbb{N}\to \mathbb{N}$, fixing $0,1$. Transport addition byThis is a commutative monoid operation with zero $0$, and multiplication distributes over it: applying ${\varphi }_{\sigma }$ reduces each distributive law to the ordinary one in $\mathbb{N}$. Thus each operation supplies a semi-additive structure on the same fixed composition law.

For each odd prime $p$, take $\sigma$ to interchange $2$ and $p$, fixing every other prime. ThenDifferent choices of $p$ give different additions, and there are infinitely many prime numbers. Hence there are infinitely many distinct semi-additive structures, even though these transported structures are isomorphic as enriched categories. The underlying one-object category has no terminal object, because its endomorphism set is not a singleton, so it indeed has no finite products in a category.

Use the standard definition of a partition regular matrix: for every finite coloring of the positive integers, there is a positive solution whose coordinates all have one color. Coordinates may repeat. Clearing denominators lets us assume $a_i\in \mathbb{Z}\setminus \{0\}$; multiplication of the row by a nonzero rational number changes neither its zero-sum subsets nor its solutions. We prove both directions of the Rado theorem for one equation directly, without invoking any form of Rado's theorem.

For necessity, choose a prime number $p>{\sum }_i|a_i|$ and use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and assign color $u\mathrm{mod}p$. Given a monochromatic solution, let $v={\min }_i{v}_p(x_i)$, let $I=\{i:v_p(x_i)=v\}$, and let $r\ne 0$ be the common color. Divide ${\sum }_i{a}_i{x}_i=0$ by $p^v$ and reduce modulo $p$. Terms outside $I$ vanish; the others giveThe nonzero residue $r$ is invertible modulo the prime number $p$, so $p$ divides ${\sum }_{i\in I}{a}_i$. This sum has absolute value less than $p$, forcing it to be zero. The set $I$ is nonempty by its definition.

For sufficiency we first derive the needed Brauer progression theorem from the permitted Van der Waerden theorem. Fix positive integers $s,\ell$. We claim that for every number of colors $r$, a finite integer interval $[B(r,s,\ell )]$ forces a monochromatic setThe case $\ell =1$ is immediate by taking $a=s$ and $d=1$. For $r=1$ and $\ell \ge 2$, take $a=d=1$ in an interval of length at least $\max (s,\ell )$. Suppose the claim holds for $r-1$ and write $M=B(r-1,s,\ell )$. By the Van der Waerden theorem, some $R$ forces an arithmetic progression of length $(\ell -1)M+1$ in $[R]$ with one color $q$. Work in $[\max (R,sMR)]$ so that all needed multiples also lie in the coloring's domain. If a subprogression of length $\ell$ and step $td$ has $std$ of color $q$, we are done. Otherwise, for every $1\le t\le M$, the initial long arithmetic progression contains such a subprogression, and $std$ avoids color $q$. The induced finite coloring $t\mapsto \chi (sdt)$ of $[M]$ therefore uses at most $r-1$ colors. The induction hypothesis gives a monochromatic set $\{se,b,b+e,\dots ,b+(\ell -1)e\}$ for this induced finite coloring. Multiplying by $sd$ gives the desired configuration in the original coloring, with initial term $sdb$ and step $sde$. This proves the claim for $\ell \ge 2$; the only use below has $\ell \ge 3$.

Now suppose ${\sum }_{i\in I}{a}_i=0$ for a nonempty $I$. Choose $i_0\in I$, put $B={\sum }_{i\notin I}{a}_i$, and put $s=|a_{i_0}|$. If $B=0$, then ${\sum }_i{a}_i=0$ and any constant positive vector is already a monochromatic solution. Otherwise take $L=|B|$ and apply the proved Brauer progression theorem with $\ell =2L+1$. All of $sd$ and $a+jd$ for $0\le j\le 2L$ have one color. DefineEvery coordinate is a positive integer in that monochromatic set, since $L-\mathrm{sgn}(a_{i_0})B$ is either $0$ or $2L$. Using the zero sum on $I$ givesThus both directions are proved:For $n=1$ the right side is impossible, agreeing with the absence of positive solutions for a single nonzero coefficient.

A deterministic finite automaton is described by finite state and alphabet label lists, one initial state label, an accepting-state bit mask, and a finite transition table. Keep each label in increasing order and list transitions lexicographically by the actual state and alphabet labels. This retains arbitrary finite subsets of the permitted labels, rather than assuming they are consecutive.

The prime-exponent encoding of a finite list gives an explicit Gödel encoding for a list $(a_0,\dots ,a_{r-1})$ of nonnegative integers:where $p_i$ is the $i$th prime number. Encode the descriptor as a list beginning with the numbers of states and alphabet symbols, followed by their sorted labels, the start label, the accepting mask, and all transition destinations. The lengths are then known during decoding.

Unique prime factorization recovers the list and hence the automaton. Reject an integer if the prescribed prime exponents are missing, additional primes occur, the list lengths disagree, state or alphabet labels repeat, the initial state or a transition target is absent, or the mask is out of range. These are effective finite checks. Thus every automaton has an integer code, valid codes are decidable, and the transition system of a coded automaton is computable. Invalid integers may be excluded explicitly or assigned a fixed empty-language automaton.

For an odd prime number $p$, the Legendre symbol is zero when $p\mid a$, one when $a$ is a nonzero quadratic residue modulo $p$, and minus one otherwise. The number-theoretic Gauss lemma says that, for $p\nmid a$, $(a/p)=(-1{)}^r$, where $r$ counts those least positive residues of $a,2a,\dots ,(p-1)a/2$ exceeding $p/2$.

For $a=2$, the residues are simply $2,4,\dots ,p-1$, so $r=(p-1)/2-\lfloor p/4\rfloor$. Examining the four odd residue classes modulo eight givesNow $2^m\equiv -1(\mathrm{mod}p)$ and $p$ is odd. The multiplicative order $d$ of $2$ divides $2m$ but not $m$. Since $m$ is a power of two, every proper divisor of $2m$ divides $m$, whence $d=2m$. Lagrange's theorem for finite groups gives $2m\mid p-1$. Because $m\ge 4$, this implies $p\equiv 1(\mathrm{mod}8)$, so the supplementary law just proved gives $(2/p)=1$. By Euler's criterion, $2^{(p-1)/2}\equiv 1(\mathrm{mod}p)$, and consequently $2m\mid (p-1)/2$. Therefore

Dirichlet theorem on primes in arithmetic progressions states that if positive integer $q$ and integer $a$ satisfy $\gcd (a,q)=1$, then infinitely many prime numbers satisfyThe coprimality hypothesis is essential: if $a$ and $q$ have a common factor greater than one, a prime in the progression must divide that factor, giving at most finitely many possibilities.

Expand the finite Euler product into geometric series. By unique prime factorization, it is the sum of $1/n$ over positive integers whose prime factors do not exceed $x$, and hence contains every term up to $m=\lfloor x\rfloor$. The harmonic sum satisfiesThe last inequality uses $m+1>x$, including when $x$ is an integer. For each prime number $p$,The telescoping series over all integers $n\ge 2$ bounds the sum of these remainders by $\frac{1}{2}{\sum }_{n\ge 2}[n(n-1){]}^{-1}=1/2$. Taking logarithms of the product bound therefore givesThis explicit constant suffices; no asymptotic theorem about the distribution of prime numbers is needed.

In the RSA cryptosystem, choose distinct large prime numbers $p,q$, set $N=pq$, and choose $e$ coprime to $\phi (N)=(p-1)(q-1)$. Choose $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. A plaintext residue class $m$ is encrypted as $c=m^e(\mathrm{mod}N)$ and decrypted as $c^d(\mathrm{mod}N)$. Fermat's little theorem modulo $p$ and $q$, followed by the Chinese remainder theorem, proves correctness even when $m$ is not coprime to $N$.

Textbook RSA cryptosystem is multiplicative: $E(m_1{m}_2)=E(m_1)E(m_2)(\mathrm{mod}N)$. For a chosen-ciphertext attack, multiply an intercepted $c$ by $r^e$ for a known invertible $r$. A decryption oracle returns $mr$, from which multiplication by $r^{-1}$ recovers $m$. Likewise, multiplying two textbook RSA signatures produces a signature of their product. These are homomorphism attacks, exploiting algebra rather than factoring $N$.

For an ElGamal signature, choose a prime $p$, a primitive root $g$ modulo $p$, a private exponent $a$, and public $y=g^a$. To sign a message digest $h=H(m)$, choose a fresh secret $k$ coprime to $p-1$ and setVerification checks $1\le r\le p-1$ and $g^{H(m)}\equiv y^r{r}^s(\mathrm{mod}p)$, which follows because $ar+ks\equiv h(\mathrm{mod}p-1)$. Authenticating the ciphertext and its context with such a digital signature, before decryption, prevents the simple multiplicative modification from being accepted without a fresh valid signature. One needs an appropriate cryptographic hash function and fresh secret cryptographic nonces: this is not a claim that every algebraic attack is impossible. In particular, the unhashed historical ElGamal signature scheme admits existential forgeries of specially chosen message exponents; mere multiplication of encrypted messages is not an authentication mechanism.

Let $f\in R$ be irreducible. If $\mathrm{deg}f=0$, then $f\in \mathbb{Z}$. A nonzero integer that is neither a unit nor, up to sign, a prime number factors nontrivially in $R$, so necessarily $f=\pm p$ for a prime $p$.

Now suppose $\mathrm{deg}f\ge 1$ and write $m=f(0)\in \mathbb{Z}$. If $m=0$, thenand both factors lie in $R$ and are nonunits. If $|m|>1$, choose a prime $p\mid m$; then $f=p(f/p)$ is again a factorization into two nonunits of $R$, since $(f/p)(0)=m/p\in \mathbb{Z}$. Both cases contradict irreducibility. Hence

Eisenstein criterion states that ifhas a prime number $p$ such that $p\nmid a_n$, $p\mid a_i$ for every $i<n$, and $p^2\nmid a_0$, then $f$ is irreducible over $\mathbb{Q}$.

After dividing out the polynomial content, suppose for contradiction that the resulting primitive polynomial factors as $f=gh$ with positive-degree $g,h\in \mathbb{Z}[X]$, using Gauss lemma for polynomials. Reduction modulo $p$ gives $\bar{f}=a_n{X}^n$, so in the polynomial ring ${\mathbb{F}}_p[X]$ both $\bar{g}$ and $\bar{h}$ are monomials. Because both factors have positive degree, their constant coefficients are divisible by $p$. Their product $a_0$ is then divisible by $p^2$, a contradiction.