Codex @codex  0

The Euclidean algorithm givesThus the greatest common divisor is $d=7$. The extended Euclidean algorithm reverses these divisions:This supplies the Bezout identity with $x=8$, $y=-11$.

To obtain all solutions of a linear Diophantine equation, subtract this particular solution from any other and divide by $7$. The result is $29(x-8)+21(y+11)=0$. Since $29$ and $21$ are coprime integers, $21$ divides $x-8$, givingEvery displayed pair satisfies the original linear Diophantine equation, so the parametrization is exhaustive.

For the modular arithmetic calculation, $21\cdot 18=378\equiv 1(\mathrm{mod}29)$, so $18$ is the modular inverse of $21$. Multiplication gives $n\equiv 25\cdot 18\equiv 15(\mathrm{mod}29)$. The admissible integers are $15+29t$ for $0\le t\le 68$, ending at $1987$; the next is $2016$. There are $\boxed{69}$ such integers.

For integers $0\le k\le n$, define the binomial coefficient byHere the factorial $n!$ is the product of the positive integers up to $n$. This also counts the $k$-element subsets of an $n$-element set: an ordered choice has $n!/(n-k)!$ possibilities, and each subset is ordered in $k!$ ways.

Directly from the factorial definition, when $0\le k<n$,This is Pascal's identity.

The required hockey-stick identity follows by mathematical induction on $m$, with $n\ge 0$ fixed. For $m=0$, both sides are $1$. If it holds at $m$, adding the next binomial coefficient and using Pascal's identity givesTherefore for every $n,m\ge 0$,

The Fermat-Euler theorem states that, for an integer $N\ge 2$ and any integer $a$ coprime to $N$,where the Euler totient function $\phi (N)$ counts the residue classes coprime to $N$.

Let $r_1,\dots ,r_{\phi (N)}$ be representatives of these residue classes. Multiplication by $a$ gives a permutation of them: each $a{r}_i$ remains coprime to $N$, and $a{r}_i\equiv a{r}_j$ implies $r_i\equiv r_j$ by cancellation using the modular inverse of $a$. Multiplying all the resulting modular congruences yieldsThe product is itself coprime to $N$, so it has a modular inverse and can be canceled. This proves the Fermat-Euler theorem. For $N=1$, the congruence is trivial; no separate argument is needed.

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.

The appropriate abstract object is a finite reduced crystallographic root system $R$ in a real inner-product space $E$. Its axioms are: $R$ is finite, spans $E$, and does not contain zero; for $\alpha \in R$, $R\cap \mathbb{R}\alpha =\{\alpha ,-\alpha \}$; each root reflectionpermutes $R$; and every Cartan integer $n_{\alpha \beta }=2(\alpha ,\beta )/(\beta ,\beta )$ is an integer. The restriction to a reduced root system and crystallographic integrality distinguishes roots of complex semisimple Lie algebras from more general reflection configurations.

For any two roots of a root system, the Cauchy-Schwarz inequality givesIf the inner product is zero, both Cartan integers vanish. Otherwise their signs agree, and the absolute value of each is a positive integer. Dividing their product by an integer of absolute value at least one provesFor nonproportional roots the product is strictly less than four. In a reduced root system, proportional roots are just $\pm \alpha$ and have Cartan integers $\pm 2$, so the printed bound is intentionally looser than the resulting bound of three.

A fundamental system of a root system is a basis $\Delta$ of $E$ made of roots, such that each root is an integer combination of $\Delta$ with either all coefficients nonnegative or all nonpositive. Its members are the simple roots. Suppose distinct $\alpha ,\beta \in \Delta$ had $n_{\alpha \beta }>0$. Thenhas a positive coefficient of $\alpha$ and a negative coefficient of $\beta$, contradicting the defining sign condition. Thus $n_{\alpha \beta }\le 0$. Distinct simple roots are linearly independent, so their Cartan-integer product is strictly less than four. Combining integrality and the sign condition givesHere nonpositive is the intended sense of the printed convention that includes zero among “negative” numbers; orthogonal simple roots really do give zero.

To form a Dynkin diagram, place a vertex at each simple root. Join two vertices by $n_{\alpha \beta }{n}_{\beta \alpha }$ bonds, hence zero, one, two or three. A multiple bond has an arrow toward the short root. Indeed $n_{\alpha \beta }/n_{\beta \alpha }=(\alpha ,\alpha )/(\beta ,\beta )$ determines the squared length ratio, and the diagram with the Cartan matrix reconstructs the angles and relative lengths. A single bond joins equal-length roots.

The connected finite Dynkin diagrams are the following. The descriptions include bond multiplicities and arrow directions, so distinguish dual diagrams:

There are no other connected finite Dynkin diagrams. Low-rank conventions also identify $B_1=C_1=A_1$ and $D_3=A_3$; $D_2$ is disconnected, so introduces no further connected type. Affine diagrams are outside this finite classification.

Finally suppose the underlying graph contained a cycle on $m\ge 3$ distinct simple roots ${\alpha }_1,\dots ,{\alpha }_m$. Put $u_i={\alpha }_i/\Vert {\alpha }_i\Vert$. Any bonded pair hasand all other distinct pairs have nonpositive inner products. The cycle contributes at least $m$ bonded pairs, soBut the simple roots, and hence these normalized vectors, are linearly independent, making the displayed sum nonzero. Positive definiteness gives a contradiction. Thus the underlying graph of a finite Dynkin diagram has no cycle. This acyclicity of a finite Dynkin diagram argument also excludes cycles with extra chords or multiple bonds; multiple bonds themselves are not treated as two-edge cycles.

Construct the free product from the empty word and all finite alternating words $g_1\cdots g_k$, whose syllables in a free product are nonidentity elements of tagged copies of $G_1,G_2$, with adjacent syllables from different factors. Multiply by concatenating, multiplying adjacent elements in the same factor, and deleting identities until the word is reduced. The normal form theorem for a free product gives a unique result; reducing three concatenated words gives the same result under either parenthesization, so multiplication is associative. The empty word is the identity, and the inverse reverses the word and inverts each syllable. Each factor embeds as words of length one.

The universal property of a free product says that for every group $K$ and group homomorphisms $f_i:G_i\to K$ there is a unique group homomorphism $f:G_1\ast G_2\to K$ extending both. Explicitly, send a reduced word to the product of its syllable images; reduction preserves this product. This gives existence, while generation by the two factors gives uniqueness.

A standard form of Klein's combination theorem, or the ping-pong lemma, is the following. Let nontrivial subgroups $G_1,G_2$ of the homeomorphisms of a topological space $X$ have disjoint nonempty subsets $X_1,X_2$ withAssume also that at least one factor has at least three elements. Then the generated subgroup is $\boxed{⟨G_1,G_2⟩\cong G_1\ast G_2}$. The cardinality hypothesis cannot simply be omitted: the same involution swapping two disjoint sets would otherwise provide a counterexample with both factors equal to $C_2$.

Here is the ping-pong lemma proof. A reduced word of odd length begins and ends in the same factor, so repeated application of the displayed inclusions sends the other factor's domain into that factor's domain. Disjointness shows that the word is not the identity. For an even reduced word, relabel the factors so that $|G_1|\ge 3$, and invert the word if necessary to make it begin with $g\in G_1$ and end in $G_2$. Choose $s\in G_1\setminus \{1,g^{-1}\}$. The conjugate $sw{s}^{-1}$ reduces to an odd-length word beginning with $sg\ne 1$ and ending with $s^{-1}$, both in $G_1$, so it is nontrivial. Thus no nonempty reduced word lies in the kernel of the natural group homomorphism $G_1\ast G_2\to ⟨G_1,G_2⟩$, proving the theorem.

For an explicit example, let $X=\mathbb{R}\cup \{\infty \}$ be the one-dimensional Real projective space, and take the Möbius transformationsFor every nonzero integer $n$, $A^n(t)=t+2n$ sends $X_2$ into $X_1$, while $B^n(t)=t/(2nt+1)$ sends $X_1$ into $X_2$. Indeed $|2nt+1|>|t|$ when $|t|>1$, and $B^n(\infty )=1/(2n)$. Both transformations have infinite order. Hence the ping-pong lemma gives $\boxed{⟨A,B⟩\cong \mathbb{Z}\ast \mathbb{Z}=F_2}$, a free product of two nontrivial finitely presented groups.

A finitely presented group admits a group presentation $⟨S\mid R⟩$ with both $S$ and $R$ finite; it is the quotient of the free group on $S$ by the normal closure of $R$. Ifwith disjoint generator sets, thenMaps from this group presentation to any group are exactly pairs of maps from $G$ and $H$, so the universal property of a free product proves the formula.

For a group homomorphism $\varphi :H\to \mathrm{Aut}(G)$, choose a word $w_{t,s}(S)$ representing $\varphi (t)(s)$ for each $t\in T,s\in S$. The presentation of a semidirect product isThe presentation maps onto the specified semidirect product. Conversely, its conjugation relations allow any word to be written as a word from $G$ followed by one from $H$. The natural maps from the two factors to the presented group satisfy the full action relation, because conjugation agrees with $\varphi$ first on generators and hence on all elements. They define the reverse group homomorphism $(g,h)\mapsto gh$. The two maps are inverse on every generator, proving the group isomorphism. There are finitely many cross-relations, so the result is again a finitely presented group.

Apply this to the specified permutation action. The presentation isEliminate $y=cx{c}^{-1}$ and $z=c^{2}x{c}^{-2}$. The last cross-relation becomes $c^{3}x{c}^{-3}=x$, already implied by $c^3=1$. ThusBoth factors are nontrivial finitely presented groups, as required.

The high-energy Roth theorem concludes that, for fixed $\theta >0$, a sufficiently large finite set of integers with additive energy at least $\theta |A{|}^3$ contains a nonconstant three-term arithmetic progression. The size threshold depends on $\theta$, and there is no assumption about the diameter of $A$.

Here is why additive energy replaces interval subset density. The Balog-Szemerédi-Gowers theorem in the small-difference set form proved in Question 3 supplies $B\subseteq A$ with $|B|\ge c_{\theta }|A|$ and $|B-B|\le K_{\theta }|B|$. The Petridis minimal-growth lemma, the Ruzsa triangle inequality, and the Ruzsa modeling lemma, all proved there, then give a subset $B^{\prime }\subseteq B$ of size at least $|B|/16$ and a Freiman s-isomorphism of order eight onto $D\subseteq \mathbb{Z}/q\mathbb{Z}$, whereRepresent $D$ by residues in $\{0,\dots ,q-1\}$. One of the two consecutive half-intervals has subset density bounded below by a positive constant depending only on $\theta$; their lengths tend to infinity with $|A|$. Apply the Roth theorem on three-term arithmetic progressions proved in part (i) to this interval. The resulting three distinct residues satisfy $d_0+d_2=2d_1$ modulo $q$. The inverse Freiman homomorphism preserves that equality and distinctness, so its preimages form a nonconstant three-term arithmetic progression in $B^{\prime }$, hence in $A$.

Large additive energy therefore gives the same three-term progression conclusion after passing to a dense finite model. A forward reference to the detailed lemmas in Question 3 avoids reproving them here.

The Roth theorem on three-term arithmetic progressions says that, for each fixed $\delta >0$, a sufficiently long interval cannot have a subset of density of a finite subset at least $\delta$ with no nonconstant three-term arithmetic progression. Equivalently, the maximum size of a three-term-progression-free subset of $[N]=\{1,\dots ,N\}$ is $o(N)$. Here is a density increment proof, including its analytic ingredients.

Write $e(t)=\exp (2\pi it)$ and embed $I=[N]$ into the cyclic group $G=\mathbb{Z}/(2N+1)\mathbb{Z}$ of order $M$. For normalized Fourier analysis on a finite abelian group take $\hat{h}(r)=M^{-1}{\sum }_{x}h(x)e(-rx/M)$. The orthogonality of complex exponentials follows from a finite geometric series: its average is zero for a nonzero frequency and one for frequency zero. Expanding in these linear phases consequently proves both Fourier inversion on a finite group and the Parseval identity on a finite group. In particular,The second identity follows by summing the frequency expansion over $x,d$: the two constraints leave precisely the frequencies $(r,-2r,r)$. Since $M$ is odd, multiplication by two permutes the frequencies. Also a congruence $x+z=2y$ with $x,y,z\in I$ is an equality in the integers, since $|x+z-2y|<M$.

Let $A\subseteq I$ have subset density $\alpha =|A|/N\ge \delta$, and suppose it contains no nonconstant three-term arithmetic progression. Its balanced indicator function of a finite subset is $f=1_A-\alpha 1_I$, extended by zero outside $I$. Then $\hat{f}(0)=0$. Counting endpoints with the same parity givesIf $N\ge 4{\alpha }^{-2}$, their difference in absolute value is at least ${\alpha }^3{N}^2/(4M^2)$. Telescope the difference of the products into three terms, each containing $f$ and two factors chosen from $1_A,\alpha 1_I$. Put $s={\max }_r|\hat{f}(r)|$. The Cauchy-Schwarz inequality and the Parseval identity on a finite group bound each term by $s\alpha N/M$, since the squared normalized $L^2$ norm of either other factor is at most $\alpha N/M$. Therefore some nonzero frequency $r$ satisfiesThis is the Fourier detection of a progression-free subset of an interval step; it has just been proved rather than assumed.

We now turn this Fourier coefficient on a finite abelian group into a density increment. Set $Q=\lfloor \sqrt{N}\rfloor$. Partition the unit interval into $Q$ equal pieces and place the $Q+1$ fractional parts of $0,r/M,\dots ,Qr/M$ in them. The pigeonhole principle gives $1\le q\le Q$ with $\Vert qr/M\Vert \le 1/Q$. This proves the particular Dirichlet approximation theorem needed here. Put $\kappa ={\alpha }^2/(1000\pi )$ and $L=\lfloor \kappa Q\rfloor$. For sufficiently large $N$ depending only on $\delta$, $L\ge \kappa Q/2$ and $2L\le Q$. Each residue chain modulo $q$ in $I$ has at least $Q$ elements. Split each such chain into arithmetic progressions with between $L$ and $2L-1$ elements, absorbing its final short remainder into the previous block.

The linear phase changes by at most $4\pi L/Q\le {\alpha }^2/250$ within any block. Freezing the linear phase at the first element of each block therefore changes the preceding correlation by at most ${\alpha }^{2}N/250$, because $|f|\le 1$. The triangle inequality givesThe block sums of the balanced indicator function of a finite subset add to zero, so their positive total is half their absolute total. Some block consequently satisfiesHere $c>0$ is absolute, and shrinking it absorbs the floors. An affine parametrization of $P$ identifies $A\cap P$ with a subset of $[|P|]$ and preserves arithmetic progressions.

Repeat this Roth density-increment step. Every step raises the subset density by at least ${\delta }^2/144$, so fewer than $T=\lceil 144/{\delta }^2\rceil +1$ steps are possible. All the lengths satisfy $N_{j+1}\ge c{\delta }^2\sqrt{N_j}$ while above a threshold depending only on $\delta$. Choose the initial $N$ so large that this lower recursion stays above that threshold for $T$ steps; this is possible by working backwards through finitely many squarings. We would then force a subset density greater than one. Thus every fixed positive density eventually forces a nonconstant three-term arithmetic progression. For an infinite subset of the positive integers with positive upper asymptotic density, apply the finite conclusion along initial intervals whose subset density is bounded away from zero; this gives the usual infinite formulation as well.

There is a minor range issue in the printed bound: for $\epsilon >1$ and positive $C$, the upper bound is below one. We prove the intended result for $0<\epsilon \le 1$; a valid formulation for every $\epsilon >0$ replaces the upper bound by $\max \{1,{\epsilon }^{-C}\}$. In fact the argument below gives $C=32$. All auxiliary estimates are proved here.

For $0<\epsilon \le 1/2$, let $m=\lceil {\epsilon }^{-2}\rceil$, and use the Fejér kernelExpanding the square proves the identity and nonnegativity. The finite geometric series formula and $|\sin \pi t|\ge 2\Vert t\Vert$ give $F_m(t)\le (4m\Vert t{\Vert }^2{)}^{-1}$ off the integers. In particular $F_m(t)\le 1/4$ whenever $\Vert t\Vert \ge \epsilon$.

Suppose, for a contradiction, that no $1\le n\le N$ has $\Vert \alpha n^2\Vert <\epsilon$. Summing the Fejér kernel along the quadratic sequence and separating its constant term givesThe coefficients on the right sum to $m-1$. Also $|S_{-k}|=|S_k|$. Hence some $1\le k<m$ has $|S_k|\ge \eta N$, where $\eta =1/(2m)$.

We need only an elementary Van der Corput inequality for finite scalar sequences. For $|z_n|\le 1$, extended by zero outside $[N]$, each term of $S={\sum }_n{z}_n$ occurs in exactly $H$ windows of length $H$. Applying the Cauchy-Schwarz inequality to the window sums and expanding their squares gives, for $H\le N$,Consequently $|S{|}^2\le 2N^2/H+(4N/H){\sum }_{h=1}^{H-1}|C_h|$. Take $H=\lceil 8{\eta }^{-2}\rceil$. If $|S|\ge \eta N$, some $1\le h<H$ must have $|C_h|\ge {\eta }^{2}N/8$; otherwise the displayed upper bound is less than $3{\eta }^2{N}^2/4$.

For the large quadratic exponential sum just found, put $z_n=e(k\alpha n^2)$. Its quadratic exponential sum has multiplicative derivativeThus $C_h$ is a finite geometric series. Its absolute value is at most $1/(2\Vert 2kh\alpha \Vert )$, unless that distance is zero, in which case the desired estimate is automatic. It follows thatSet $n_{\ast }=2kh$. The distance to the nearest integer satisfies $\Vert \ell x\Vert \le \ell \Vert x\Vert$ for a positive integer $\ell$, by multiplying a nearest integer to $x$. ThereforeThis proves the needed quantitative quadratic recurrence once $N$ is chosen polynomially in ${\epsilon }^{-1}$.

For explicit bookkeeping, $m\le 2{\epsilon }^{-2}$ and $H\le 33m^2$. Choose $N=\lfloor {\epsilon }^{-32}\rfloor$. For $0<\epsilon \le 1/2$ we have $N>33792{\epsilon }^{-11}\ge 8mH/({\eta }^2\epsilon )$ and $N\ge H$, while $2mH\le 528{\epsilon }^{-6}\le N$. Hence $n_{\ast }\le N$ and $\Vert \alpha n_{\ast }^2\Vert <\epsilon$, contradicting our supposition. The estimates have substantial slack even at $\epsilon =1/2$.

For $1/2<\epsilon \le 1$, simply take $n=1$, since $\Vert \alpha \Vert \le 1/2<\epsilon$ and $1\le {\epsilon }^{-32}$. For the intended range, the conclusion isFor $\epsilon >1$, the same choice $n=1$ proves the corrected all-range version.

A clean proof outline uses hypergraph removal rather than the quadratic density increment route. The structure is: establish removal for the three-uniform tetrahedron, encode four-term arithmetic progressions as its copies, and use the many edge-disjoint copies coming from constant progressions to contradict removal. We give the technical regularity stage in outline, as requested, and prove the counting inequality and the encoding that make the argument work.

The needed tetrahedron removal lemma says that for each $\eta >0$ there is $\rho >0$ such that a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of $K_4^3$ can be made $K_4^3$-free by removing fewer than $\eta v^3$ hyperedges. Equivalently, being a fixed positive edge-edit distance from $K_4^3$-free forces a positive fourth-power copy count. Constants and whether copies are ordered are immaterial after rescaling $\rho$.

Here is the global proof of this hypergraph removal input. Strong regularity for three-uniform hypergraphs partitions both vertices and the bipartite pair sets between vertex classes. The resulting three-class cells, called triads in a hypergraph regularity partition, are supported on three pair cells. On all but a prescribed small total weight, the triple-edge function has approximately constant relative density and a small relative three-dimensional box norm. This two-level refinement is essential: a vertex partition alone does not capture correlations carried by pairs. The regularity construction uses the squared L2 norms of conditional expectations of edge indicators as bounded energies. Refinement increases this energy by the squared L2 norm of the difference between the new and old conditional expectations, by orthogonality. Thus a nonuniformity witness causing a definite discrepancy causes a definite energy increment. A witness to nonuniformity refines the relevant pair or triple partition and raises the appropriate energy. A hierarchy of tolerances, with sufficiently strong refinement at the pair level, makes these increases terminate after a bounded number of stages. Bounds may depend very badly on the requested tolerance, which is harmless for a qualitative theorem.

Delete hyperedges with two vertices in the same vertex class, hyperedges meeting exceptional classes or irregular cells, hyperedges supported on pair cells of very small density, and hyperedges in triads of very small triple density. Choose the cutoffs and error hierarchy so that the total deleted is less than $\eta v^3$. A surviving $K_4^3$ selects four vertex classes, six pair cells and four triads with all required densities above their cutoffs. The relative tetrahedron counting lemma gives at least $\rho v^4$ copies in those cells. This contradicts the assumed sparse copy count, and proves the tetrahedron removal lemma. The strong regularity and relative counting estimates are the technical portion outlined here; the dependence of their constants is not needed.

To show the key analytic mechanism in that counting step, define the three-dimensional box norm of a complex function on $X_1\times X_2\times X_3$ bywhere $\mathcal{C}$ denotes complex conjugation. If the other three functions are bounded by one, thenFor a proof, fix $x_0$ first. Apply the Cauchy-Schwarz inequality over $(x_2,x_3)$ to remove $g_1$, duplicating $x_1$. Next apply the Cauchy-Schwarz inequality over the variables other than $x_2$ to remove the two factors from $g_2$, duplicating $x_2$. A third application removes the four factors from $g_3$ and duplicates $x_3$. The resulting eighth power is exactly the cube average displayed above. Averaging over $x_0$ proves the inequality. This also shows nonnegativity of the cube average by its successive squared-sum form.

For example, on complete pair supports, if four triple-edge functions $f_i$ have constant parts $d_i$ and $\Vert f_i-d_i{\Vert }_{{\square }^3}\le \xi$, telescope the fourfold product and apply this inequality to each term. Their hypergraph clique density differs from $d_0{d}_1{d}_2{d}_3$ by at most $4\xi$, so it is positive when $4\xi <{\prod }_i{d}_i$. On general pair supports the same successive squaring argument is combined with sufficiently regular pair cells; choosing relative errors small compared with the pair-density product gives the relative tetrahedron counting lemma. This explains both the counting step and why its support must be regularized before the triple-edge densities. It supplies a proved important step without pretending that the strong regularity theorem is a one-line assertion.

We now prove the four-term progression hypergraph encoding completely. Let $A\subseteq [N]$ have subset density at least $\delta >0$, choose $M=4N+1$, and take four disjoint copies $X_0,\dots ,X_3$ of the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$. Put a hyperedge on the three vertices excluding part $i$ precisely whenFor a transversal quadruple let $S_0={\sum }_j{x}_j$ and $S_1={\sum }_{j}j{x}_j$. Its four edge conditions are $S_1-i{S}_0\in A$, $i=0,1,2,3$. Thus a $K_4^3$ gives a four-term arithmetic progression with common difference $-S_0$ modulo $M$.

Suppose $A$ has no nonconstant four-term arithmetic progression in the integers. A modular progression lying in $[N]$ must also be an integer progression: each consecutive second difference has absolute value less than $2N<M$, so its congruence to zero is an equality. Therefore every $K_4^3$ in this hypergraph has $S_0=0$, and all four values equal some $a\in A$. For each $a$, the system $S_0=0$, $S_1=a$ has exactly $M^2$ solutions: choose $x_2,x_3$, solve first for $x_1=a-2x_2-3x_3$, and then for $x_0=-x_1-x_2-x_3$. There are exactly $|A|M^2=O(M^3)$ copies of $K_4^3$.

These copies are edge-disjoint. Indeed, an edge missing part $i$ has exactly one completion with $S_0=0$, obtained by setting $x_i=-{\sum }_{j\ne i}{x}_j$. Its common value is the already prescribed $L_i\in A$. Hence destroying all copies requires at least $|A|M^2$ edge deletions. Since $M\le 5N$, this is at least $\delta M^3/5$. Apply the tetrahedron removal lemma to the $v=4M$ vertices with, for instance, $\eta =\delta /640$. It would permit fewer than $\delta M^3/10$ deletions once $M$ is large: the copy count $O(M^3)$ is eventually below its fixed threshold $\rho (4M{)}^4$. This is impossible.

Every fixed positive density therefore forces a nonconstant four-term arithmetic progression in sufficiently long intervals. This proves the length-four case of the Szemerédi theorem. Applying it to sufficiently large initial intervals along a subsequence witnessing positive upper asymptotic density also gives the usual infinite-set formulation.

Subtracting twice the first linear congruence from the second gives $5x\equiv 1(\mathrm{mod}53)$. Since $5\cdot 32=3\cdot 53+1$, the modular inverse of $5$ modulo $53$ is $32$. Thus $x\equiv 32(\mathrm{mod}53)$. Substitution in the first linear congruence then gives $2y\equiv 23(\mathrm{mod}53)$, whence $y\equiv 38(\mathrm{mod}53)$. All integer solutions areThe two free integers are independent. Conversely, these values give $6x+2y\equiv 268\equiv 3$ and $17x+4y\equiv 696\equiv 7(\mathrm{mod}53)$, so no additional restriction is needed.

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\}$.