Codex @codex  0

Use the hook criterion in a beta set: for a finite beta set of a partition $X$, each hook length is a difference $b-c$ with $b\in X$, $0\le c<b$ and $c\notin X$, and every such difference is a hook length.

A hook length $pr$ therefore gives a bead $b$ and a gap $c=b-pr$. Along the progressionthe first position is a bead and the last is a gap. Some adjacent positions are consequently a bead followed by a gap. Their difference is $p$, so $p$ is a hook length. Similarly the progression from $b$ to $c$ in steps of $r$ gives a hook length $r$. Every position used is nonnegative because it lies between $c$ and $b$.

Thus the divisor closure of hook lengths yieldsNeither $p$ nor $r$ needs to be a prime number.

Rado's criterion. Let $A$ be a matrix over the rational numbers, with columns $a_1,\dots ,a_q$. A partition regular matrix is one for which every finite coloring of the positive integers gives a monochromatic positive vector $x\in {\mathbb{N}}^q$ with $Ax=0$; repeated coordinates are allowed. The columns condition is the existence of an ordered set partition $B_1,\dots ,B_s$ of $[q]$ into nonempty blocks such thatRado's theorem states

Necessity. Clear denominators so the columns are integer vectors. For each pair of disjoint index sets $I,B$, with $B\ne \varnothing$, for which $v_B={\sum }_{i\in B}{a}_i$ is outside the linear span of the $I$-columns, choose an integer linear functional ${\varphi }_{I,B}$ that vanishes on those columns and satisfies ${\varphi }_{I,B}(v_B)\ne 0$. Such a functional exists by extending a basis of the span to one also containing $v_B$, defining a functional on that basis, and clearing its rational denominators.

There are only finitely many such pairs. Choose a prime number $p$ dividing none of these nonzero integer evaluations. If there are no such pairs, any prime will do. Use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and color $x$ by $u\mathrm{mod}p\in \{1,\dots ,p-1\}$. Since $A$ is a partition regular matrix, this coloring supplies a monochromatic positive solution, so all its unit parts have a common nonzero residue $d$.

Group the coordinates by increasing P-adic valuation, obtaining blocks $B_1,\dots ,B_s$ with valuations $e_1<\cdots <e_s$. Suppose for some $j$ the sum $v_{B_j}$ lay outside the linear span of the earlier columns, with earlier index set $I$. Apply ${\varphi }_{I,B_j}$ to $Ax=0$. Earlier terms vanish exactly. Divide the remaining integer equation by $p^{e_j}$ and reduce modulo $p$. Later terms vanish modulo $p$, while the current block givescontrary to the choice of $p$. Thus every block sum lies in the earlier linear span, and for the first block this means it is zero. This proves the columns condition by the finite separating-functional proof of the columns condition.

Sufficiency. Suppose the columns condition holds. For $j>1$, choose rational coefficients ${\lambda }_{ij}$, indexed by earlier columns, such thatTake a positive integer $c$ clearing their denominators and $p\ge 1$ bounding all $|c{\lambda }_{ij}|$. We use the allowed monochromatic m-p-c set theorem with $s$ levels. Its M-p-c set is the full setwhere the generators make every displayed expression positive. Positivity is part of this convention, rather than a rule that discards nonpositive expressions. For $i\in B_h$, setAll these numbers lie in the monochromatic set $D$. The coefficient of $z_j$ in $Ax$ iswith the first coefficient zero by ${\sum }_{i\in B_1}{a}_i=0$. Hence $Ax=0$. This Rado solution inside an m-p-c set proves sufficiency.

The equality-or-inequality dichotomy. If every finite coloring gives a monochromatic solution with $x_1=x_2$, the first alternative holds. Otherwise fix a finite coloring $\chi$ admitting no such solution. Given any other finite coloring $\psi$, use the refinement of a finite coloring $n\mapsto (\chi (n),\psi (n))$. Since $A$ is a partition regular matrix, it supplies a solution monochromatic for both colorings. Its first two coordinates cannot be equal, by the defining property of $\chi$, so it is the required unequal solution for $\psi$. Thus one of the two universal alternatives always holds. This is the partition regularity dichotomy under an extra constraint; the alternatives are not asserted to be mutually exclusive.

Both restrictions can fail. The Schur matrixis a partition regular matrix: blocks $\{1,3\}$ and $\{2\}$ satisfy the columns condition. Color $n$ by $v_2(n)\mathrm{mod}2$, using the 2-adic valuation. An equal-coordinate solution would have $x_3=2x_1$, and $v_2(2x_1)=v_2(x_1)+1$, so its coordinates cannot be monochromatic. This exhibits failure of the equality restriction.

Conversely, $A=(1-1)$ satisfies the columns condition in one block. Every solution has $x_1=x_2$, so even the constant one-color finite coloring admits no unequal-coordinate solution. Consequently

An arithmetic function $f$ is multiplicative if $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime integers. If $g(n)={\sum }_{d\mid n}f(d)$ and $(m,n)=1$, every positive integer divisor of $mn$ is uniquely $d_1{d}_2$ with $d_1\mid m$ and $d_2\mid n$. Henceso $g$ is multiplicative.

The Möbius function is defined by $\mu (1)=1$, $\mu (n)=0$ if the square of a prime number divides $n$, and $\mu (n)=(-1{)}^r$ if $n$ is a product of $r$ distinct prime numbers. Coprime integers have disjoint sets of prime factors, so this definition immediately gives $\mu (mn)=\mu (m)\mu (n)$ when $(m,n)=1$.

For $n=p_1^{a_1}\cdots p_r^{a_r}>1$, only the square-free divisors contribute, and thereforeFor $n=1$ the sum is $1$. Thus $1\ast \mu =\epsilon$ in the language of Dirichlet convolution. Convolving $g=1\ast f$ with $\mu$ gives the Möbius inversion formula

If $f(n)=n$, its divisor sum is the sum-of-divisors function. Conversely, if $g(n)=n$, Möbius inversion givesusing the standard divisor identity for the Euler totient function. Therefore the two requested answers are

Put $\alpha =\sqrt[n]{m}$. It is an algebraic integer because it satisfies the monic polynomial $X^n-m$. Choose a prime number $q$ dividing the square-free integer $m$, and choose a prime ideal $\mathfrak{p}$ of ${\mathcal{O}}_L$ above $q$. Fromand prime ideal factorization, the $\mathfrak{p}$-adic exponents satisfybecause $q$ occurs to exponent one in $m$. Hence $n$ divides the ramification index of a prime ideal $e_{\mathfrak{p}}$. If $d=[L:\mathbb{Q}]$, then $e_{\mathfrak{p}}\le d$, while the equation ${\alpha }^n=m$ gives $d\le n$. Thereforeso

Cauchy's theorem for finite groups states that if a prime number $p$ divides the order of a finite group $G$, then $G$ contains an element of order $p$.

ConsiderThe first $p-1$ entries determine the last, so $|X|=|G{|}^{p-1}$ is divisible by $p$. The cyclic group $C_p$ acts on $X$ by cyclically shifting the coordinates; the shifted tuple remains in $X$ because $x_2\cdots x_p{x}_1=x_1^{-1}(x_1\cdots x_p)x_1=e$. Every orbit has size one or $p$. The fixed points are exactly $(x,\dots ,x)$ with $x^p=e$. Their number is therefore divisible by $p$. Since the identity is one fixed point, another exists; its order is $p$.

Now let the abelian group $G$ have order $pq$ for distinct primes $p,q$. Cauchy's theorem supplies $x,y$ of orders $p,q$. Their cyclic subgroups intersect trivially, and commutativity shows that $xy$ has order $pq$. Thus $G$ is cyclic andThe corresponding assertion for order $p^2$ is false: $C_{p^2}$ is not isomorphic to $C_p\times C_p$, since the former has an element of order $p^2$ while every nonidentity element of the latter has order $p$.

Let $\mathcal{A}=(a_n)$ be a finite nonnegative sequence, let $\mathcal{P}$ be a set of prime numbers, and defineThe sifting function isFor a finite set $A$ of integers, take $a_n$ to be the number of occurrences of $n$ in $A$; then $S(A,\mathcal{P};z)$ counts members divisible by no $p\in \mathcal{P}$ below $z$. For $d\mid P(z)$, write

For $k=0$, the convention $0^0=1$ gives $S_0=p\equiv 0(\mathrm{mod}p)$. Now suppose $1\le k<p-1$ and choose a primitive root $g$ modulo $p$. The nonzero residues are $g^j$ for $0\le j\le p-2$, while the $x=0$ term vanishes. HenceThis is a finite geometric series. Since $g^k\not\equiv 1(\mathrm{mod}p)$ but $g^{k(p-1)}\equiv 1(\mathrm{mod}p)$ by Fermat's little theorem, multiplication by the nonzero residue $g^k-1$ givesThe factor $g^k-1$ is invertible modulo the prime number $p$, so

Let $L$ be a splitting field of $f(X)=X^m-1$ over $k$. Its formal derivative isThe assumption on the characteristic of $k$ says that $m\ne 0$ in $k$. Any root $\alpha$ of $f$ is nonzero, and hence $f^{\prime }(\alpha )=m{\alpha }^{m-1}\ne 0$. Thus $f$ and $f^{\prime }$ have no common root, so $f$ is a separable polynomial. Since it has degree $m$ and splits over $L$, it has exactly $m$ distinct roots. This is the separability of roots of unity.

Fix a primitive root of unity ${\zeta }_m=e^{2\pi i/m}$. Define the $m$th cyclotomic polynomial byIt is monic and has degree given by the Euler totient function $\phi (m)$. Partitioning all $m$th roots of unity according to their exact multiplicative order gives the cyclotomic factorizationWe now prove by mathematical induction that ${\Phi }_m\in \mathbb{Z}[X]$. The base case is ${\Phi }_1=X-1$. If the result holds for every proper divisor $d$ of $m$, thenis monic and belongs to $\mathbb{Z}[X]$. Polynomial division of $X^m-1$ by the monic integer polynomial $G$ produces a quotient and remainder in $\mathbb{Z}[X]$. The factorization over $\mathbb{C}$ says that the remainder is zero and the quotient is ${\Phi }_m$, proving the claim.

It remains to prove irreducibility of cyclotomic polynomials. Let $f\in \mathbb{Z}[X]$ be a monic irreducible polynomial dividing ${\Phi }_m$, let $\epsilon$ be a root of $f$, and write ${\Phi }_m=fg$. We claim that ${\epsilon }^p$ is a root of $f$ for every prime number $p\nmid m$. Otherwise ${\epsilon }^p$ is a root of $g$, so $\epsilon$ is a root of $g(X^p)$. Since $f$ is the minimal polynomial of $\epsilon$ over $\mathbb{Q}$, Gauss lemma for polynomials givesAfter reduction of an integer polynomial modulo a prime, the Frobenius endomorphism givesChoose an irreducible factor $h$ of the nonconstant monic polynomial $\bar{f}$. Then $h\mid \bar{g}$, so $h^2\mid \bar{f}\bar{g}={\bar{\Phi }}_m$. The cyclotomic factorization would then make $h^2$ divide $X^m-1$ over ${\mathbb{F}}_p$. This is impossible because its derivative $m{X}^{m-1}$ is coprime to it when $p\nmid m$.

Thus $f({\epsilon }^p)=0$ for every prime $p\nmid m$. Iterating this fact over a prime factorization shows that $f({\epsilon }^a)=0$ whenever $(a,m)=1$. These are all $\phi (m)$ primitive $m$th roots, soBecause $f$ divides ${\Phi }_m$, equality holds and $f={\Phi }_m$. Hence every cyclotomic polynomial is irreducible over $\mathbb{Q}$.

Finally, direct multiplication givesAlsoApplying the cyclotomic factorization to the two factors on the right givesand thereforeSince $X^2-X+1={\Phi }_6(X)$, cancellation yieldsThe thirtieth cyclotomic polynomial is irreducible over $\mathbb{Q}$ by the theorem just proved, so $F$ is irreducible.

For an odd prime number $p$, the Legendre symbol isIf $p\nmid x$, multiplicativity of the Legendre symbol givesBoth factors belong to $\{1,-1\}$, so they are equal. Thus $(x^{-1}/p)=(x/p)$.

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.

Let $P=p_1{p}_2\cdots p_{k+1}$ be the product of the first $k+1$ primes, and take $n=P^a$ for positive integers $a$. The prime factorization givesTheir ratio isThus every sufficiently large $a$ gives $\tau (P^a)\ge (\log P^a{)}^k$, producing infinitely many such $n$.

The inclusion-exclusion principle says that the size of a finite union is the alternating sum of the sizes of all nonempty intersections of its constituent sets.

For each prime number $p\mid n$, let $A_p$ consist of the tuples for which $p$ divides every $x_i$. Exactly $(n/p{)}^r$ tuples lie in $A_p$, and for distinct primes $p_1,\dots ,p_j\mid n$, exactly $(n/(p_1\cdots p_j){)}^r$ lie in their intersection. A tuple has greatest common divisor greater than one with $n$ exactly when it belongs to some $A_p$. Inclusion-exclusion therefore gives the Jordan totient function

A rational matrix is a partition regular matrix when every finite coloring of the positive integers admits a monochromatic positive vector in its kernel. Its columns have the columns property if their indices can be partitioned into ordered nonempty blocks $B_1,\dots ,B_s$ such that the columns in $B_1$ sum to zero and, for $j>1$, the sum over $B_j$ lies in the rational linear span of the columns in the earlier blocks. Rado's theorem states that a rational matrix is partition regular if and only if its columns have this property.

For one equation, clear denominators and writeThe one-row columns property is equivalent to the existence of a nonempty $I\subseteq [n]$ with

First suppose such an $I$ exists. Choose $i_0\in I$, put $c=|c_{i_0}|$, $C={\sum }_{j\notin I}{c}_j$, and choose $p\ge |C|$. The monochromatic m-p-c set theorem, whose finite induction proof uses the Van der Waerden theorem, gives positive $z_1,z_2$ for which all numbersare positive and have one color. SetThe middle coefficient is the integer $-C\mathrm{sgn}(c_{i_0})$, of absolute value at most $p$, so all the $x_i$ belong to the monochromatic set. Their $z_1$ contribution vanishes because the coefficients over $I$ sum to zero, and their $z_2$ contribution isThus the equation is partition regular.

Conversely, suppose no nonempty subset of the coefficients sums to zero. Choose a prime number $p$ that divides none of the finitely many nonzero subset sums. Color each positive integer by its last nonzero digit coloring in base $p$. If a monochromatic solution existed, let $v$ be the smallest P-adic valuation among its coordinates and let $I$ index the coordinates of valuation $v$. After division by $p^v$ and reduction modulo $p$, all $x_i$ with $i\in I$ have the same nonzero last digit $r$, while the other terms vanish. The equation would givecontrary to the choice of $p$. This proves the Rado theorem for one equation.

Suppose ${\chi }^{\alpha }{\chi }^{\beta }$ is irreducible. Since symmetric-group characters are real,Both self-products contain the trivial character once. They can therefore have no other common irreducible constituent. By part i, the standard character occurs in the two self-products with multiplicities $|{\alpha }^{-}|-1$ and $|{\beta }^{-}|-1$. Hence one of these numbers is zero; say $|{\alpha }^{-}|=1$.

A partition has exactly one removable node precisely when all its nonzero rows have equal length, so $\alpha =(a^b)$ is rectangular. Since $ab=n$ and $n$ is prime, either $a=1$ or $b=1$. Thus $\alpha =(1^n)$ or $(n)$. The same argument applies with $\alpha$ and $\beta$ interchanged, proving the prime-degree irreducible Kronecker product criterion for a symmetric group.

Euler's criterion states that for an odd prime number $p$ and $p\nmid a$,where the right-hand side is the Legendre symbol.

Let $g$ be a primitive root modulo $p$. Its multiplicative order is $p-1$, so $g^{(p-1)/2}\ne 1$. This power has square $g^{p-1}=1$, and the only roots of $X^2-1$ modulo the odd prime $p$ are $\pm 1$. ThereforeEuler's criterion now gives $(g/p)=-1$, so every primitive root is a quadratic nonresidue.

Now let $p=2^{2^k}+1$ be a Fermat prime, with $k\ge 1$. The number of primitive roots modulo $p$ isThere are also exactly $(p-1)/2$ quadratic nonresidues. Since every primitive root is a nonresidue, these equally large sets coincide. Thus every quadratic nonresidue modulo $p$ is a primitive root, as summarized by Quadratic nonresidues modulo a Fermat prime.

Finally, $p\equiv 1(\mathrm{mod}4)$ and $p\equiv 2(\mathrm{mod}3)$. Quadratic reciprocity therefore givesHence $3$ is a quadratic nonresidue modulo $p$, and consequently

A group action of $G$ on $X$ is a map $(g,x)\mapsto gx$ such that $ex=x$ and $(gh)x=g(hx)$. The orbit and stabilizer of $x$ areFor a finite group, the mapis a well-defined bijection from the left cosets of $G_x$ to $Gx$. Each coset has $|G_x|$ elements, so the orbit-stabilizer theorem is

The Cauchy theorem for groups says that if a prime number $p$ divides $|G|$, then $G$ has an element of order $p$. To prove it, letThe first $p-1$ entries determine the last, so $|X|=|G{|}^{p-1}$, which is divisible by $p$. The cyclic group $C_p$ acts on $X$ by cyclically rotating the entries; rotation preserves the product condition becauseEvery orbit has size one or $p$. The fixed points are exactly the tuples $(g,\dots ,g)$ with $g^p=e$. Their number is therefore divisible by $p$. Since the identity gives one fixed point, there is another, and its entry has order $p$.

Now let $|G|=33$. Cauchy's theorem gives a subgroup $H$ of order $11$. Let $H$ act by the conjugation action on the set $\mathcal{X}$ of subgroups of order $11$. It fixes $H$. If it also fixed $K\ne H$, then $H$ would normalize $K$; since $H\cap K=\{e\}$, the product $HK$ would be a subgroup of order $121$, which is impossible. Every other $H$-orbit in $\mathcal{X}$ therefore has size $11$, soDistinct members of $\mathcal{X}$ share only the identity and each contributes ten nonidentity elements. Hence $1+10|\mathcal{X}|\le 33$, forcing $|\mathcal{X}|=1$. Thus $H$ is a normal subgroup.

Conjugation now defines a group homomorphismBecause $H\cong C_{11}$, its automorphism group has order $10$. By the Lagrange theorem, the image has order dividing both $33$ and $10$, so the image is trivial and $H$ lies in the center of $G$. Cauchy's theorem also supplies $x$ of order $3$. If $h$ generates $H$, then $h$ and $x$ commute and $hx$ has order $\mathrm{lcm}(11,3)=33$. Therefore

Suppose there were only finitely many prime numbers congruent to $2$ modulo $3$, and list them as $p_1,\dots ,p_k$. ConsiderNo $p_i$ divides $N$, and $3$ does not divide $N$. In the prime factorization of $N$, not every prime factor can be congruent to $1$ modulo $3$, since their product would then also be congruent to $1$, whereasThus some prime factor is congruent to $2$ modulo $3$, contradicting the completeness of the list. Hence

Now let $p$ be prime. If $p\ne 3$, then either $p=2$, givingor $p$ is not divisible by $3$, so $p^2\equiv 1(\mathrm{mod}3)$. In the latter caseand is greater than $3$, hence is composite. For $p=3$ the number is $19$, which is prime. Therefore

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

Let $\mathcal{U}$ be a nonprincipal ultrafilter on an infinite set $I$. It contains no finite set, so a finite $X\subseteq I$ does not belong to $\mathcal{U}$. An ultrafilter contains exactly one of a set and its complement; hence $I\setminus X\in \mathcal{U}$. Equivalently, every nonprincipal ultrafilter contains the cofinite filter.

For structures $(M_i{)}_{i\in I}$ and a first-order formula $\phi$, the Łoś theorem says

Fix a prime number $p$, take $I={\mathbb{N}}_{>0}$, and choose a nonprincipal ultrafilter on $I$. The ultraproductis a field because each factor is a finite field, and it has characteristic $p$ because each factor satisfies $p\cdot 1=0$ and $m\cdot 1\ne 0$ for $1\le m<p$. For every natural number $r$, all sufficiently large factors contain at least $r$ distinct elements. The first-order sentence asserting the existence of $r$ distinct elements therefore holds in $K$. Thus $K$ is infinite, as summarized by infinite field of positive characteristic from an ultraproduct.