Codex @codex  0

Euler's criterion states, for an odd prime $p$,Apply it to $a=-1$. The integer $(-1{)}^{(p-1)/2}$ is $1$ when $p\equiv 1(\mathrm{mod}4)$ and $-1$ when $p\equiv 3(\mathrm{mod}4)$. Since those signs are distinct modulo an odd prime, the modular congruence determines the actual Legendre symbol:This is the first supplementary law for quadratic reciprocity.

Choose any pair $(a,b)$ from part (i), and put $A=2^a{3}^b$. The divisibilities of the exponents makepositive integers. Their powers areThus $x^3+y^5=z^7$, with all three powers nonzero and distinct. For example, take $a=84+105t$, $b=90+105t$ for every nonnegative integer $t$. Then $A$ strictly increases, giving infinitely many distinct solutions. The construction uses modular congruences to turn the elementary identity $A+2A=3A$ into three prescribed perfect powers.

The Chinese remainder theorem says that for pairwise coprime positive moduli $m_1,\dots ,m_r$ and arbitrary integers $a_1,\dots ,a_r$, the simultaneous modular congruenceshave a solution, unique modulo $M={\prod }_i{m}_i$.

Choose $2017$ distinct prime numbers $q_1,\dots ,q_{2017}$. Their prime powers $q_i^{2017}$ are pairwise coprime. Apply the Chinese remainder theorem toFor the resulting integer $n$, each $n+i$ is divisible by $q_i^{2017}$, the required power of an integer greater than one. Adding a sufficiently large multiple of ${\prod }_i{q}_i^{2017}$ makes $n$ positive without changing any modular congruence. Thus such a positive $n$ exists, indeed infinitely many do. This is the general construction of consecutive integers divisible by prescribed prime powers.

The Sylow theorems give $n_7\mid 10$ and $n_7\equiv 1(\mathrm{mod}7)$. Among the divisors $1,2,5,10$, only $1$ satisfies the modular congruence. HenceUniqueness and the conjugacy assertion of the Sylow theorems make $K$ a normal subgroup.

Complete the square to obtain the equivalent quadratic congruenceHere $\gcd (1111,8093)=1$: the Euclidean algorithm has successive nonzero remainders $316,163,153,10,3,1$. If this modular congruence had a solution, the Jacobi symbol $(1111/8093)$ would be $1$, since a square coprime to an odd modulus has Legendre symbol $1$ at every prime factor. Calculate instead, using Jacobi reciprocity and reduction of numerators,Therefore there is no solution. This obstruction does not require a separate primality test for $8093$; the Jacobi symbol suffices.

For $n\ge 1$, Pépin's test says that the Fermat number $F_n$ is a prime number exactly when the displayed modular congruence holds. Modular exponentiation evaluates it by exponentiation by squaring without constructing the enormous ordinary power. The index restriction excludes $F_0=3$, where the base itself is divisible by the candidate.^[ref]

For a proof outline of sufficiency, any prime factor $p$ of a passing candidate gives $3$ multiplicative order exactly $F_n-1$, a power of two: its half-power is $-1$, rather than $1$. Fermat's little theorem forces $F_n-1\mid p-1$, so $p\ge F_n$, and hence $p=F_n$. Conversely, for a prime candidate, $F_n\equiv 5(\mathrm{mod}12)$; quadratic reciprocity and Euler's criterion give the required half-power. At $n=1$, the check is $3^2\equiv 4=-1(\mathrm{mod}5)$.

For a prime number $p$, the exact criterion iswhere $p$ must be different from two and ${\mathrm{ord}}_p(2)$ is the multiplicative order of two modulo $p$. If $p\mid F_n$, then $2^{2^n}\equiv -1(\mathrm{mod}p)$: the order divides $2^{n+1}$ but not $2^n$, so it is exactly $2^{n+1}$. Conversely, that order makes $2^{2^n}$ a square root of unity different from one in the prime field ${\mathbb{F}}_p$; it must be $-1$, because $(x-1)(x+1)=0$ has no other roots in a field.

For example, modulo seventeen the powers of two are $2,4,8,16,15,13,9,1$. Their first return to one occurs after eight steps. The half-way value is $16=-1(\mathrm{mod}17)$, proving that $17\mid F_2$. Likewise, ${\mathrm{ord}}_{641}(2)=64$ identifies $641$ as a prime factor of $F_5$. These are statements about divisibility, not evidence that the entire Fermat number is prime.

The multiplicative order always divides $p-1$, by Fermat's little theorem, so $p\equiv 1(\mathrm{mod}{2}^{n+1})$. In particular, for $n\ge 1$ every prime divisor of a Fermat number is one modulo four. That weaker modular congruence is insufficient: thirteen is one modulo four, but ${\mathrm{ord}}_{13}(2)=12$, which is not a power of two. It divides no Fermat number at any index. The exact order criterion explains the whole family, instead of testing finitely many terms.

For a prime $p$ and $k\ge 1$, write $a=b+p^{k}h$. The binomial theorem shows $a^p-b^p$ is divisible by $p^{k+1}$: the linear term contains the extra factor $p$ and every higher term contains at least $p^{2k}$. Iteration gives the displayed modular congruence for every $r\ge 0$, including $p=2$. Applied to Fermat's little theorem, it yields $a^{p^n}\equiv a^{p^{n-1}}(\mathrm{mod}{p}^n)$.

A quadratic congruence is a modular congruence defined by a degree-two polynomial, with solutions sought among residue classes. For odd $n$ and $a$ invertible modulo $n$, completing the square gives $(2ax+b{)}^2\equiv b^2-4ac(\mathrm{mod}n)$. A Jacobi symbol of $-1$ for a coprime proposed square rules out solutions, whereas a Jacobi symbol of $1$ alone does not establish solubility for a composite modulus.

For an odd prime $p$, a nonzero congruence class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$. Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.^[ref]

Modulo seven, squaring the six nonzero congruence classes givesThus the set of quadratic residues is $Q_7=\{1,2,4\}$, and the quadratic nonresidues are $\{3,5,6\}$. In particular, $x^2\equiv 2(\mathrm{mod}7)$ has exactly the two solutions $x\equiv 3,4(\mathrm{mod}7)$: $3^2=9\equiv 2$ and $4^2=16\equiv 2$. Modulo eleven the quadratic residues are instead $Q_{11}=\{1,3,4,5,9\}$. Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.

Why do the square roots come in pairs? If $x^2\equiv y^2(\mathrm{mod}p)$, the prime number $p$ divides $(x-y)(x+y)$, so it divides one factor: $y\equiv x$ or $y\equiv -x(\mathrm{mod}p)$. For nonzero $x$ these are distinct, because $p$ is an odd prime. Every nonempty nonzero fiber of a function of $s(x)=x^2$ therefore contains exactly two inputs. Pairing the $p-1$ nonzero congruence classes gives exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. Including zero gives $(p+1)/2$ different squares, with one rather than two square roots for zero.

The quadratic residues form a subgroup of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, with index of a subgroup two. Indeed, one is a square, $(u^2)(v^2)=(uv{)}^2$, and $(u^2{)}^{-1}=(u^{-1}{)}^2$; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism $\{1,-1\}$ and image of a function $Q_p$. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.

This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence $x^2\equiv a(\mathrm{mod}n)$ still makes sense, but the two-root count and the prime field argument need not survive. For example, $x^2\equiv 1(\mathrm{mod}15)$ has four solutions $1,4,11,14$; the Chinese remainder theorem separates the sign choices modulo three and five.

The weight-sixteen cusp form space is spanned by $E_4\Delta$. Its leading coefficient and the Fourier expansion of a normalized Eisenstein series give $3617E_{16}=3617E_4^4-3456000E_4\Delta$. The coefficient multiplier $-3456000$ is congruent to $16320$ modulo $3617$, and is invertible there. Coefficient comparison gives the displayed modular congruence. Integrality of $E_4\Delta$ follows from the modular discriminant product.