Codex @codex  0

The Dedekind factorization theorem says that, when a rational prime $p$ does not divide the index of an order $\mathbb{Z}[\theta ]\subseteq {\mathcal{O}}_K$, a factorizationof the minimal polynomial modulo $p$ gives

Let $K=\mathbb{Q}(\sqrt{d})$ with square-free $d$, and let $p$ be odd. The resulting splitting of rational primes in a quadratic field is:

Finally suppose $d>0$ and
$\alpha =A/C+(B/C)\sqrt{d}$ has norm $-1$, with integers
$A,B,C$ chosen coprime. ThenIf an odd $p\equiv 3(\mathrm{mod}4)$ ramified, then $p\mid d$. Reduction modulo $p$ gives
$A^2\equiv -C^2(\mathrm{mod}p)$. Since $-1$ is not a square modulo such a prime, $p\mid A,C$. Dividing the equation's divisibility shows $p\mid B$ as well (use that square-free $d$ has $p$-adic valuation one), contradicting coprimality. Hence no prime $p\equiv 3(\mathrm{mod}4)$ ramifies.

Letbe a primitive polynomial. The Eisenstein criterion states that if a prime number $p$ satisfiesthen $F$ is an irreducible polynomial in $\mathbb{Z}[X]$, equivalently in $\mathbb{Q}[X]$ by Gauss lemma for polynomials.

To prove it, suppose that $F=GH$ with $G,H\in \mathbb{Z}[X]$ of positive degree. Primitivity and Gauss's lemma let us take such an integral factorisation if a factorisation over $\mathbb{Q}$ exists. Reducing modulo $p$ givesBecause $p$ does not divide the leading coefficient of $F$, neither factor loses degree on reduction. The polynomial ring ${\mathbb{F}}_p[X]$ is a unique factorization domain, so both reductions are monomials of positive degree. In particular, $p$ divides both constant terms $G(0)$ and $H(0)$. It follows that $p^2$ dividesa contradiction. This proves the criterion.

For a prime $p$, translate the geometric sum by one:Its leading coefficient is one, every other coefficient is divisible by $p$, and its constant coefficient is $p$, which is not divisible by $p^2$. It is therefore Eisenstein at $p$. Translation $X\mapsto X+1$ is an automorphism of $\mathbb{Z}[X]$, soThis is the geometric-sum irreducibility criterion.

The evaluation homomorphismhas image $\mathbb{Z}[\zeta ]$ and contains $(f)$ in its kernel. Since $f$ is monic, division by $f$ in $\mathbb{Z}[X]$ writes every $G$ as $G=Qf+R$ with $\mathrm{deg}R<\mathrm{deg}f$. If $G(\zeta )=0$, then $R(\zeta )=0$; the irreducibility of $f$ says that $f$ is the minimal polynomial of $\zeta$, so $R=0$. Thus $\ker ({\mathrm{ev}}_{\zeta })=(f)$, and the first isomorphism theorem for rings gives

Now take $p=3$. Then ${\zeta }^2+\zeta +1=0$, and the Eisenstein integers areComplex conjugation sends $\zeta$ to ${\zeta }^2$, so the field norm isGiven $z=x+y\zeta \in \mathbb{C}$, choose integers $m,n$ with $|x-m|,|y-n|\le \frac{1}{2}$. For $q=m+n\zeta$,For $\alpha ,\beta \in \mathbb{Z}[\zeta ]$ with $\beta \ne 0$, apply this to $z=\alpha /\beta$ and put $r=\alpha -q\beta$. ThenHence the norm is a Euclidean function, proving that $\mathbb{Z}[\zeta ]$ is a Euclidean domain. This is the Euclidean norm on the Eisenstein integers.

Finally suppose $A\in {\mathrm{GL}}_n(\mathbb{Z})$ satisfies $A^2+A+I=0$. Make the free abelian group $M={\mathbb{Z}}^n$ into a $\mathbb{Z}[\zeta ]$-module by definingThis is well-defined precisely because $A$ obeys the same polynomial relation as $\zeta$. The module is finitely generated. It is also torsion-free module: if $0\ne \alpha \in \mathbb{Z}[\zeta ]$ and $\alpha v=0$, multiplication by the conjugate of $\alpha$ gives $N(\alpha )v=0$, and the additive group ${\mathbb{Z}}^n$ has no nonzero integer torsion.

A Euclidean domain is a principal ideal domain, and the structure theorem for finitely generated modules over a principal ideal domain says that a finitely generated torsion-free module over one is free. Thusfor some $m$. Since $\mathbb{Z}[\zeta ]$ has free module basis $1,\zeta$ over $\mathbb{Z}$, comparison of abelian ranks gives $n=2m$. There can consequently be no such matrix when $n$ is odd.

If $n=2m$, choose a $\mathbb{Z}[\zeta ]$-basis $v_1,\dots ,v_m$. Thenis a $\mathbb{Z}$-basis, and $A^2{v}_i=-v_i-A{v}_i$. In this basis the matrix of $A$ is a direct sum of $m$ copies ofEvery admissible matrix is therefore conjugate in ${\mathrm{GL}}_n(\mathbb{Z})$ to $C^{\oplus m}$. Hence there is exactly one conjugacy class for even $n$, and none for odd $n$. This is the classification of integral matrices satisfying the third cyclotomic polynomial.

False. For a prime number $p$, the Prüfer p-group $C_{p^{\infty }}$ is an Artinian $\mathbb{Z}$-module: every proper subgroup is a finite cyclic group, so no infinite strictly descending chain of subgroups exists. It is not Noetherian because its cyclic subgroups form the strict ascending chain

Let $A$ be a rational matrix with columns $a_1,\dots ,a_n$. It is a partition regular matrix when every finite coloring of the positive integers has a monochromatic vector $x$ with $Ax=0$. It has the columns property when the column indices have an ordered partition $B_1,\dots ,B_r$ such thatand, for every $s>1$,Rado's theorem states that $A$ is partition regular if and only if it has the columns property.

First suppose $A$ is partition regular, and clear its denominators. For a prime number $p$, apply the last nonzero digit coloring in base $p$: if $x=p^{v_p(x)}u$ with $p\nmid u$, its color is $u\mathrm{mod}p$. Choose a monochromatic solution and group its coordinates into blocks $B_1,\dots ,B_r$ of equal $p$-adic valuation, in increasing order of valuation. Only finitely many ordered partitions are possible, so one partition occurs for infinitely many primes.

For any such prime, divide ${\sum }_i{x}_i{a}_i=0$ by the lowest power of $p$ and reduce modulo $p$. All coordinates in $B_1$ have the same nonzero leading digit $d$, while later blocks vanish, soThe integer vector ${\sum }_{i\in B_1}{a}_i$ is divisible by infinitely many primes and therefore equals zero.

Now fix $s>1$, and let $t$ be the common valuation on $B_s$. Reduction modulo $p^{t+1}$ givesIf the first sum of columns were outside the rational linear span of the earlier columns, an integer linear functional would vanish on every earlier column but not on that sum. Applying it to the congruence would say that infinitely many primes divide one fixed nonzero integer, a contradiction. Thus the displayed partition has the columns property.

Conversely, suppose $A$ has the columns property. For $s>1$, choose rational numbers $q_{is}$ such thatLet $d_{is}$ equal $1$ for $i\in B_s$, equal $-q_{is}$ in the earlier blocks, and equal zero in the later blocks. For $s=1$, let $d_{i1}$ be the indicator of $B_1$. Thenfor every $s$. Choose a positive integer $c$ clearing all denominators and a positive integer $p$ with $|c{d}_{is}|\le p$ whenever $s$ is later than the block containing $i$.

By the monochromatic m-p-c set theorem, the coloring contains a monochromatic $(r,p,c)$-set with generators $z_1,\dots ,z_r$. DefineIf $i\in B_t$, thenso every $y_i$ lies in that one monochromatic M-p-c set. Moreover,Thus $A$ is partition regular, proving Rado's theorem.

For the equation $4x+3y-6z=0$, a monochromatic solution in the last nonzero base-$p$ digit coloring would, at the least $p$-adic valuation among $x,y,z$, force a nonempty subset sum of $4,3,-6$ to vanish modulo $p$. The seven possible sums areNone is divisible by $5$, so base $5$ gives no monochromatic solution. The smaller primes do admit solutions: $(x,y,z)=(3,2,3)$ works for base $2$, whose coloring has one color, and $(3,4,4)$ is monochromatic in base $3$. Hence the smallest prime is

For $x+2y-7z=0$, use the last nonzero base-$11$ digit itself. The nonempty subset sums of $1,2,-7$ arenone zero modulo $11$. This is the required $10$-coloring.

For a $5$-coloring, identify each nonzero residue $d$ modulo $11$ with $-d$, giving the five colorsIf a monochromatic solution existed, reduction at the least $11$-adic valuation would give a signed nonempty subset sum of $1,2,-7$ equal to zero modulo $11$. Singles have absolute residues $1,2,7$; pairs have absolute residues $1,3,5,6,8,9$; and triples have absolute residues $4,6,8,10$. None is zero modulo $11$, which proves that this $5$-coloring works.

Use the injective group homomorphism $F_2\hookrightarrow {\mathrm{SL}}_2(\mathbb{Z})$ from part (a). If $1\ne g\in F_2$, its image is an integral matrix $M\ne I$. Choose a prime number $p$ that does not divide one nonzero entry of $M-I$. The reduction modulo a prime in an integral matrix group homomorphismthen sends $M$ to a nonidentity element. Its target is a finite group, so the composite map separates $g$ from the identity. Hence $F_2$ is a residually finite group.

Suppose for a contradiction that $b_0\ne 0$. The Eisenstein series in the question has constant term $2\zeta (k)$, sohas zero constant term and is therefore a level-one cusp form of weight $k$. Part (b) gives the coefficient bound $[q^n]h=O(n^{k/2})$. Since $b_n=O(n^{k/2})$ as well, the displayed Fourier expansion of $G_k$ would imply

Take $n=\ell$ through the primes. Thenwhich cannot be $O({\ell }^{k/2})$ because $k-1>k/2$ for $k\ge 4$. Therefore $b_0=0$, so $g$ vanishes at the only cusp of $\Gamma (1)$ and belongs to $S_k(\Gamma (1))$. This is the Fourier coefficient growth criterion for a level-one cusp form.

Write $\chi ={\chi }^{\lambda }$. By the Hook-length formula,Suppose the order of a group element $g$ did not divide this product. Then for some prime number $p$, the highest prime power $p^a$ dividing $|g|$ would not divide the hook product. One cycle of $g$ has length divisible by $p^a$, whereas no hook length of $\lambda$ is divisible by $p^a$. In particular there is no removable rim hook having that cycle length. Applying the Murnaghan–Nakayama rule first to this cycle gives $\chi (g)=0$, a contradiction. This is the symmetric-group character co-degree vanishing criterion, and its contrapositive proves

The Lagrange root bound over a field says that a nonzero polynomial of degree $r$ over a field has at most $r$ roots. In particular, a polynomial modular congruence of degree $r$ modulo a prime number has at most $r$ incongruent solutions unless all its coefficients vanish modulo that prime.

Suppose that $d$ is good and that the positive integer divisor $e$ divides $d$. The $d$ roots of $X^d-1$ form a finite multiplicative subgroup $H$ of ${\mathbb{F}}_p^{\times }$. By the fact that every finite multiplicative subgroup of a field is cyclic, $H=⟨g⟩$ is a cyclic group of order $d$. The solutions in $H$ of $x^e=1$ areso there are at least $e$ of them. The Lagrange root bound over a field gives at most $e$ roots in all of ${\mathbb{F}}_p$, hence exactly $e$. Thus every divisor of a good number is good.

Now put $n=pq$. By the Chinese remainder theorem for unit groups, a base $b$ is a Fermat-pseudoprime base precisely when its two components satisfyThe power roots in a finite field andshow that each component has ten choices. Therefore there areFermat-pseudoprime bases.

To impose the strong pseudoprime condition, write $n-1=2^{s}m$ with $m$ odd. Since $10\mid n-1$, we have $5\mid m$. In each cyclic group of ten Fermat components, raising to the $m$th power sends five elements to $1$ and five elements to $-1$. A pair of components passes the strong test exactly when their signs agree: the pair $(1,1)$ satisfies the first alternative, and $(-1,-1)$ satisfies the second at $j=0$. Components of opposite sign become $(1,1)$ after squaring and can never jointly equal $-1$. Hence the number of strong-pseudoprime bases is

The binomial theorem givesThe central binomial coefficient is the largest of these $2n+1$ nonnegative binomial coefficients, so

For the upper bound, fix a prime number $p\le 2n$. By Legendre formula,Each summand is either zero or one. Hence the P-adic valuation satisfiesIf $p\le \sqrt{2n}$, this impliesThere are at most $\sqrt{2n}$ such prime numbers. If instead $p>\sqrt{2n}$, then $p^2>2n$, so the P-adic valuation is at most one. Multiplying the prime-power contributions therefore yields

Suppose that the positive integer $n$ is a decisive number. For every prime number $p<\sqrt{n}$, the composite number $p^2$ satisfies $1<p^2<n$. It therefore cannot be coprime to $n$, so $p\mid n$.

The product of all prime numbers below $\sqrt{n}$ consequently divides $n$. Taking natural logarithms givesChanging the strict endpoint can remove at most one prime term. By part b, for every sufficiently large $n$ the right-hand side is at least, for example, $\sqrt{n}/13$. This is impossible for sufficiently large $n$, sinceThus every decisive number lies below one fixed bound, and only finitely many integers can do so.

Fix a prime number $p>r$. Distinct members of an intersecting $r$-uniform family have intersection size inwhereas every member has size $r\notin L$ modulo $p$. The Frankl-Wilson theorem with $|L|=r-1$ therefore givesFor fixed $r$,This is the asserted asymptotic weakening of the Erdős-Ko-Rado theorem.

No. It is enough to take the prime number $t=2$. By the monochromatic sums-and-products obstruction, there is a finite coloring $\chi$ of $\mathbb{N}$ for which no infinite set has all its pairwise sums and pairwise products in one color. Refine $\chi$ by also recording the parity of the 2-adic valuation.

If a sequence $(x_i)$ made both requested families monochromatic, put $y_i=x_i^2$. If the set of distinct $y_i$ were infinite, an injective subsequence would make all pairwise sums $y_i+y_j$ and products $y_i{y}_j$ monochromatic under $\chi$, a contradiction. Otherwise some $y=x_i^2$ occurs infinitely often. Two occurrences give the sum $2y$ and the product $y^2$, butbecause $v_2(y)$ is even. The refining colors differ, another contradiction.

Let $c_1,\dots ,c_n$ be the columns of the rational partition regular matrix $A$, and clear denominators so that they are integer vectors. We use the P-adic columns lemma. For a large prime number $p$, color each positive integer by a sufficiently long initial block of the unit part of its P-adic valuation, together with its valuation modulo the block length. Partition regularity supplies a monochromatic $x=(x_1,\dots ,x_n)$ withGroup the indices according to the successive $p$-adic orders of the $x_i$. At the lowest order, division by the common power of $p$ and reduction modulo the chosen large power showsComparing the next nonzero blocks of base-$p$ digits shows successively thatFor completeness, these congruences may be made exact by taking the digit block longer than every determinant and coordinate formed from the fixed columns: a nonzero such integer cannot be divisible by the resulting power of $p$. There are only finitely many ordered partitions of $[n]$, so passing through arbitrarily long blocks leaves one partition satisfying all the displayed identities. This is precisely the columns property.

Let $K$ be a number field. Its places consist of its real embeddings, conjugate pairs of complex embeddings, and the finite places associated with nonzero prime ideals $\mathfrak{p}$ of its ring of integers of a number field. At a real or complex place use the usual absolute value. If $\mathfrak{p}$ lies over the prime number $p$ with ramification index $e_{\mathfrak{p}}$, normalize its absolute value byThese normalizations extend the standard absolute values on $\mathbb{Q}$.

Write $d_v=[K_v:{\mathbb{Q}}_v]$ for the local degree of a place. Thus $d_v$ is $1$ at a real place, $2$ at a complex place, and $e_v{f}_v$ at a finite place. The Absolute multiplicative Weil height isThe product formula shows that this is unchanged when $K$ is replaced by a larger number field containing $\alpha$.

Choose distinct prime numbers $p,q$ so large that $pq>C(p+q)$, and setThe fraction $(p+q)/(pq)$ is reduced, because neither $p$ nor $q$ divides $p+q$. The height of a rational number therefore givesThe choice of $p,q$ proves the required strict inequality.

For each prime number $p\nmid a$, the congruence $an+1\equiv 0(\mathrm{mod}p)$ removes exactly one residue class of $n$ modulo $p$; for $p\mid a$, it removes none. The dimension-one upper-bound sieve therefore givesSeparating the primes that divide $a$ bounds the product byThe ratio form of Mertens theorem says that the first product is $\ll \log w/\log z$. Hence

Fix a finite set $S$ of primes. We prove that only finitely many denominators $q_n$ can be S-smooth number. This is the standard finite-place corollary of the Schmidt subspace theorem for best approximations of the first kind; the reduction is recalled here because the target $\alpha$ need not be algebraic.

Apply the Dirichlet approximation theorem at each cutoff between two successive record denominators. Its approximant can be replaced by the last record without increasing the error. Apply the finite-place Schmidt subspace theorem to the resulting pairs of primitive vectors, using $X-\alpha Y,Y$ at the real place only after eliminating $\alpha$ between two successive pairs, and $X,Y$ at every place belonging to $S$. The factorsfor an $S$-smooth denominator supply the required height saving. If infinitely many such records existed, one fixed rational subspace would contain infinitely many of the paired vectors. Eliminating its rational linear relation has two possible outcomes: either all sufficiently late records represent one rational number, which contradicts the irrationality of $\alpha$, or $\alpha$ is algebraic and, for some $\eta >0$, infinitely many of the records satisfyThe latter alternative contradicts the Roth theorem. Thus only finitely many $q_n$ are $S$-smooth.

If the largest prime factor of $q_n$ did not tend to infinity, some bound $B$ would contain the largest prime factor for infinitely many $n$. Taking $S$ to be the finite set of primes at most $B$ would make those denominators $S$-smooth, contrary to the preceding conclusion. Therefore $P^{+}(q_n)\to \infty$.

For a group presentation $\mathcal{P}=⟨X\mid R⟩$ with finitely many generators and a prime number $p$, defineThis uses the unshifted convention. Identity relators have zero weight, and a divergent sum gives value $-\infty$. Some literature subtracts one instead; inequalities must be shifted accordingly. Taking roots in the free group matters: roots appearing only after passing to the quotient do not change the relator weight. The p-rank of a group bounds this quantity above, and the index-p rewriting bound for p-deficiency gives the infinitude criterion p-deficiency at least one implies infinitude.