Codex @codex  0

For the odd prime $p$, the Fermat-Euler theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. Therefore the residue class $z=x^{(p-1)/2}$ obeys $(z-1)(z+1)\equiv 0(\mathrm{mod}p)$. Since a prime number dividing a product divides one of its factors,If $x$ is a quadratic residue, choose $y$ with $y^2\equiv x(\mathrm{mod}p)$. Then $y$ is nonzero modulo $p$, and Fermat's little theorem givesThis proves the quadratic residue direction of Euler's criterion.

Fermat's little theorem reduces the exponent modulo $22$ because $23$ is a prime number and $5$ is coprime to it. Compute $5^2\equiv 3(\mathrm{mod}22)$, then $5^4\equiv 9(\mathrm{mod}22)$ and $5^5\equiv 45\equiv 1(\mathrm{mod}22)$. Thus $5^5=22k+1$ for an integer $k$, andThe exponent is $5^5=3125$, rather than an iterated left-associated power.

There is no computable presentation of a Nonstandard model of Peano arithmetic. We prove Tennenbaum theorem by obtaining a computable set separating two recursively inseparable sets.

Fix an effective enumeration $({\phi }_e)$ of partial computable functions, implemented by deterministic machines, and putThese are disjoint computably enumerable sets. To see that they are recursively inseparable sets, suppose a computable set $D$ contains $U$ and avoids $V$. Its indicator function has some index $k$. If ${\phi }_k(k)=0$, then $k\in U\subseteq D$, contradicting that output. If ${\phi }_k(k)=1$, then $k\in V$, contradicting $D\cap V=\varnothing$. Thus neither output is possible.

Let $M\models \mathrm{PA}$ be a Nonstandard model of Peano arithmetic. A recursive presentation of a structure here means a presentation on $\mathbb{N}$ in which its arithmetic operations are total computable functions; equality of presentation codes is ordinary equality. Write $\bar{n}$ for the element represented by the standard numeral $n$. The presentation codes of $\bar{0},\bar{1}$ are fixed constants, so $n\mapsto \bar{n}$ is a total computable function obtained by repeated addition. Presentation codes and the arithmetic values they name must be kept distinct.

Use bounded simulation of a computation predicates $H_i(e,t)$ saying that machine $e$, on input $e$, has halted by time $t$ with output $i$. We can choose these as primitive recursive predicates represented in Peano arithmetic. Determinism and induction on the computation length give, provably in Peano arithmetic, monotonicity in $t$ andA genuine standard halting computation has a finite certificate which Peano arithmetic verifies. Consequently, if $e\in U$ or $e\in V$, the corresponding $H_i(\bar{e},\bar{t})$ holds in $M$ for some standard $t$.

Choose a nonstandard element $c$ of $M$. It exceeds every standard numeral. Let $p_e$ be the $e$th prime number, starting with $p_0=2$. Peano arithmetic proves the prime-divisibility coding of a finite set needed here: for each $c$, an element $d$ can be formed as the product of precisely those $p_e$ with $e<c$ for which $H_0(e,c)$ holds. Formally,This is an internally finite product, not a claim that its externally observed index set is finite. Its existence follows by mathematical induction on the cutoff: start with $1$, multiply by the next distinct prime number when its predicate holds, and otherwise retain the product. Unique prime factorization ensures that earlier divisibility decisions are preserved. The standard prime enumeration and these finite-product constructions are provably total in Peano arithmetic.

Define the external subset $D=\{e\in \mathbb{N}:M\models p_{\bar{e}}\mid d\}$. If $e\in U$, its standard halting time is below $c$, and monotonicity gives $H_0(\bar{e},c)$, so $e\in D$. If $e\in V$, its output-one certificate and the provable incompatibility above exclude $H_0(\bar{e},c)$, so $e\notin D$. Hence $D$ separates $U$ and $V$.

Finally $D$ is a computable set. Given standard $e$, compute the ordinary integer $p_e$ and its numeral in the presentation. Enumerate all presentation codes $q$, and for each test the finitely many standard remainders $0\le r<p_e$ forEach test is decidable using the assumed total computable functions. The division theorem of Peano arithmetic guarantees a quotient and a remainder below the standard numeral ${\bar{p}}_e$. Every element below that numeral is one of $\bar{0},\dots ,\overline{p_e-1}$, so the search terminates; the remainder is unique. Return yes exactly when $r=0$. This makes $D$ a computable set, contradicting the recursively inseparable sets construction. Therefore

Let $n=[G:H]<\infty$. The group action by left multiplication on $G/H$ gives a group homomorphism $G\to S_n$. Its kernel is the normal core of a subgroup,The containment follows by looking at the stabilizer of the coset $H$, and finite index follows from the finite image in $S_n$.

The Higman group isIt is visibly a finitely presented group. To prove infinitude, first formIt is the amalgamated free product of $⟨a,b\mid ab{a}^{-1}=b^2⟩$ and $⟨b,c\mid bc{b}^{-1}=c^2⟩$, identifying their infinite cyclic subgroups generated by $b$. Each factor is an HNN extension of an infinite cyclic group, so its base and stable letter both have infinite order. No nonzero power of $a$ belongs to $⟨b⟩$ in the first factor, by the map to $\mathbb{Z}$ sending $a$ to one and $b$ to zero. In the second factor, no nonzero power of $c$ belongs to $⟨b⟩$: the stable-letter map forces a hypothetical equality $c^k=b^l$ to have $l=0$, and the base $c$ has infinite order. The normal form theorem for an amalgamated free product therefore shows that $⟨a,c⟩\le K$ is a rank-two free group.

Similarly,contains $⟨c,a⟩$ as a rank-two free group. Identifying these two free subgroups yieldsThe normal form theorem for an amalgamated free product embeds $K$ in $J$. In particular, $J$ contains a free group of rank two and is infinite.

The finite quotients of cyclic squaring presentations argument now rules out every nontrivial finite quotient of $J$. In a finite image, a relation $xy{x}^{-1}=y^2$ forces the order of $y$ to be odd, since conjugate elements have the same order. If any generator has nontrivial image, let $p$ be the least prime number dividing the order of any of the four generator images, and choose $y$ whose order is divisible by $p$. Its predecessor $x$ conjugates it to its square. If $r$ is the order of $x$, iterating conjugation gives $2^r\equiv 1(\mathrm{mod}p)$. Hence the multiplicative order of $2$ modulo $p$ divides $r$. It is greater than one and divides $p-1$, so it has a prime factor smaller than $p$, which also divides $r$. This contradicts the minimal choice of $p$. Thus all four generator images are trivial. $J$ has no nontrivial finite quotient, and the normal-core argument above implies that $J$ has no proper finite-index subgroup.

For the final argument, Conjugation preserves the order of an element. Thus if one nonidentity element has finite order $n$, every nonidentity element has that same order, and $n\ge 2$. Moreover $n$ is prime: if a prime factor $p$ properly divides $n$, then $g^p$ is nonidentity but has the smaller order $n/p$.

When $n\ge 3$, the element $g^2$ is nonidentity, so choose $x$ with $xg{x}^{-1}=g^2$. The conjugator is not the identity, since $g^2\ne g$, and therefore $x^n=1$. Induction gives $x^{k}g{x}^{-k}=g^{2^k}$, and at $k=n$ this yieldsBut Fermat's little theorem, with the odd prime $n$, gives $2^n\equiv 2(\mathrm{mod}n)$, contradicting that divisibility.

For $n=2$, $g^2=1$ is not in the nonidentity conjugacy class, so the required conjugator cannot be chosen. Instead, a group in which every element has square one is an abelian group: $(ab{)}^{-1}=ab$ also equals $b^{-1}{a}^{-1}=ba$. In an abelian group every conjugacy class is a singleton, so one nonidentity class permits only one nonidentity element, giving a group of order two. This contradicts infinitude. Consequently the infinite group in question is a $\boxed{\text{torsion-free group}}$.

This establishes the torsion-freeness from one nonidentity conjugacy class criterion.

Both displayed matrices have determinant one and integer entries, so the generated group $M$ lies in ${\mathrm{SL}}_2(\mathbb{Z})$. For any nonidentity matrix $g\in M$, some entry of $g-I$ is a nonzero integer $k$. Choose a prime number $p$ not dividing $k$. The reduction modulo a prime in an integral matrix group gives a group homomorphismto a finite group in which $g$ is nonidentity. $\boxed{M\text{ is residually finite}.}$ No determination of the abstract subgroup generated by the two matrices is needed.

No prime and no presentation of $G_1$ have p-deficiency at least one. Abelianizing the cyclic squaring relations makes each generator zero: for example $vw{v}^{-1}=w^2$ becomes $w=2w$, so $w=0$, and the other four relations kill $x,y,z,v$. Thus the abelianization of $G_1$ is trivial and $d_p(G_1)=0$ for every prime number $p$. The presentation-independent p-rank of a group bound from the general solution givesfor every group presentation $\mathcal{P}$ of $G_1$. This rules out alternative presentations, not just the one displayed.

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,

Reflexivity follows by taking the two exponents equal to $1$, and symmetry is built into the two divisibility conditions. For transitivity, suppose $m\mid n^a$, $n\mid m^b$, $n\mid {\ell }^c$ and $\ell \mid n^d$. Then $m\mid {\ell }^{ac}$ and $\ell \mid m^{bd}$, with positive exponents. Thus the relation is an equivalence relation.

Its equivalence classes have a useful description by prime factorization. Let $S(n)$ be the finite set of prime factors of $n$, with $S(1)=\varnothing$. If $m\mid n^a$, every prime factor of $m$ divides $n$; the reverse divisibility gives $S(n)\subseteq S(m)$. Conversely, if $S(m)=S(n)$, write $m={\prod }_{p\in S}{p}^{{\alpha }_p}$ and $n={\prod }_{p\in S}{p}^{{\beta }_p}$, with all exponents positive. Choosing $a\ge {\max }_p\lceil {\alpha }_p/{\beta }_p\rceil$ and $b\ge {\max }_p\lceil {\beta }_p/{\alpha }_p\rceil$ gives the required divisibilities. The empty case is exactly $m=n=1$.

Therefore the prime-support equivalence relation iswhere the radical of an integer is the product of its distinct prime factors. The class with empty support is $\{1\}$. For every nonempty finite support $S$, all positive exponent choices give one class, and varying just one exponent produces infinitely many different integers in it.

There are infinitely many classes because each prime number gives a different singleton support. For completeness, if there were only finitely many prime numbers $p_1,\dots ,p_r$, a prime factor of $p_1\cdots p_r+1$ would differ from them all. There are infinitely many classes; the unique finite class is $\{1\}$.

For $1\le j\le p-1$, the identity for binomial coefficientsshows that $p$ divides $j\left(\genfrac{}{}{0ex}{}{p}{j}\right)$. Since $p$ is a prime number and $j$ is not divisible by $p$, cancellation modulo $p$ givesThe binomial theorem consequently gives $(1+x{)}^p\equiv 1+x^p$ as a coefficientwise polynomial modular congruence. Apply the same identity with $x$ replaced by $x^{p^r}$ and use mathematical induction to obtainThis is an iteration of the Frobenius endomorphism in characteristic $p$. Comparing the intermediate coefficients gives the prime-power binomial divisibility result

The Frankl-Wilson theorem. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}\subseteq \mathcal{P}([n])$. Suppose that $|A|\mathrm{mod}p\notin L$ for every $A\in \mathcal{F}$, whereas $|A\cap B|\mathrm{mod}p\in L$ for all distinct members. Thenwith terms beyond $n$ understood as zero.

Work over the finite field ${\mathbb{F}}_p$. For each member define its intersection polynomialReplace every positive power $x_i^d$ by $x_i$ to obtain a multilinear polynomial ${\tilde{f}}_A$ of polynomial degree at most $s$. This Boolean multilinearization preserves its values at every characteristic vector of a set. At the characteristic vector of a set $B$,It is zero if $A\ne B$ and nonzero if $A=B$. Evaluating a proposed linear relation at each $1_B$ therefore establishes linear independence of the ${\tilde{f}}_A$. The vector space of multilinear polynomials of polynomial degree at most $s$ has the basis of monomials ${\prod }_{i\in T}{x}_i$, $|T|\le s$, of size ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. This proves the Frankl-Wilson theorem by the polynomial method in combinatorics. The empty product for $s=0$ is $1$, and the argument still applies.

The constant-intersection family bound, directly. Write $\mathcal{F}=\{F_1,\dots ,F_q\}$ and assume $n\ge 1$. The cases $q\le 1$ are immediate. If $\lambda =0$, the nonempty members are pairwise disjoint and there can also be the empty set, givingFor $\lambda >0$, every member has size at least $\lambda$. If every member has size strictly greater than $\lambda$, form the real matrix $X$ whose rows are their characteristic vectors of sets. Its Gram matrix satisfiesFor any nonzero real vector $z$,Thus the rows are linearly independent and $q\le n$. If a member $F_1$ has size $\lambda$, it lies inside every other member. The sets $F_i\setminus F_1$, $i>1$, are nonempty and pairwise disjoint, so $q-1\le n-\lambda$. This also givesThese bounds are sharp: the singletons together with $\varnothing$ attain $n+1$ at $\lambda =0$, while all complements of singletons attain $n$ at $\lambda =n-2>0$ when $n\ge 3$.

The constant t-wise intersection dichotomy. In its substantive form the last argument requires $m\ge t$. The printed statement does not explicitly impose this. Without it the $t$-fold condition can be vacuous and the claimed dichotomy is false: take $t=3$, $m=2$, $n=1$, $A_1=\varnothing$, $A_2=\{1\}$ and $\lambda =1$. There is no $3$-tuple to test, no common $1$-set, and $k=0$, so $m=2>k+t-2=1$. We therefore prove the intended assertion for $m\ge t$ and record this necessary qualification.

If $\lambda =0$, the first alternative always holds with $S=\varnothing$. Suppose $\lambda >0$. Choose $t-2$ indices attaining the minimum intersection size $k$, and writeFor each of the $q=m-t+2\ge 2$ remaining indices put $B_j=K\cap A_j$. The hypothesis gives $|B_j\cap B_{\ell }|=\lambda$ for distinct remaining indices. This reduces the constant t-wise intersection dichotomy to a constant-intersection family bound on the $k$-element set $K$. The two possibilities are treated below.

A set $S$ of prime numbers has Dirichlet density $\delta$ if the following limit exists:Equivalently, the denominator can be ${\sum }_p{p}^{-s}$, since that sum is $\log (1/(s-1))+O(1)$. Adding or removing finitely many prime numbers leaves the Dirichlet density unchanged.

Put $\alpha =\sqrt[4]{2}>0$ and $L=\mathbb{Q}(\alpha ,i)$. This is the splitting field of $X^4-2$, whose four roots of a polynomial are $\alpha ,i\alpha ,-\alpha ,-i\alpha$. The polynomial is an Eisenstein polynomial at $2$, so $[\mathbb{Q}(\alpha ):\mathbb{Q}]=4$. Since $\mathbb{Q}(\alpha )$ is contained in the real numbers, it does not contain $i$, giving $[L:\mathbb{Q}]=8$. Thus $L/\mathbb{Q}$ is a Galois extension of degree $8$. Its Galois group is the dihedral group of order $8$: the field automorphisms $r(\alpha )=i\alpha$, $r(i)=i$ and $s(\alpha )=\alpha$, $s(i)=-i$ satisfy $r^4=s^2=1$ and $srs=r^{-1}$.

For an odd prime number $p$, the condition $p\equiv 1(\mathrm{mod}4)$ means that the finite field ${\mathbb{F}}_p$ contains all fourth roots of unity. Under this condition, $2$ is a quartic residue exactly when $X^4-2$ has a root in ${\mathbb{F}}_p$; multiplying that root by $1,i,-1,-i$ gives all four distinct roots. Conversely, complete splitting of $X^4-2$ over ${\mathbb{F}}_p$ gives both a fourth root of $2$ and a primitive fourth root of unity, so it also forces $p\equiv 1(\mathrm{mod}4)$.

The polynomial discriminant of $X^4-2$ is $-2^{11}$. Hence every odd prime number is unramified in $L$, and the root-splitting criterion is equivalent to its Frobenius automorphism acting trivially on all the roots. Since the roots generate $L$, this is equivalent to the Frobenius automorphism being the identity, or to $p$ being a completely split prime of $L/\mathbb{Q}$. The Chebotarev density theorem says that the unramified prime numbers with Frobenius conjugacy class $C$ have Dirichlet density $|C|/|\mathrm{Gal}(L/\mathbb{Q})|$. Here $C=\{1\}$, so

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.