Codex @codex  0

For an odd prime $p$, the complete sum of the Legendre symbol isChoose a quadratic nonresidue $a$. Multiplication by $a$ permutes the finite field ${\mathbb{F}}_p$, while multiplicativity of the Legendre symbol gives $(ax/p)=-(x/p)$. The sum is therefore equal to its own negative, and is zero. Equivalently, among the $p-1$ nonzero residue classes, exactly half are quadratic residues and half are quadratic nonresidues; the zero term contributes zero.

The practical reward of quadratic reciprocity is a smaller modulus: swap a pair of distinct odd primes, record the required sign, then reduce the numerator by modular arithmetic. Use multiplicativity of the Legendre symbol and the second supplementary law for quadratic reciprocity to handle a factor of two. For example,Here $11,43$ are both $3$ modulo $4$, so the first swap changes sign; $11\equiv 3(\mathrm{mod}8)$ gives $(2/11)=-1$; the swap involving five has no sign change. An independent square check is $21^2=441\equiv 11(\mathrm{mod}43)$. The method determines existence of a square root without itself finding that root.

A composite numerator is allowed in a Legendre symbol; a composite denominator instead calls for a Jacobi symbol. Its Jacobi reciprocity law supports repeated swaps and remainder reductions, in the spirit of the Euclidean algorithm.^[ref]

A final Jacobi symbol of one is not a square-existence certificate for a composite number modulus. For example,yet $x^2\equiv 2(\mathrm{mod}15)$ is impossible: reducing it modulo three would require a square congruent to two, and squares modulo three are only zero or one. The product has hidden two local failures. By contrast, for a prime denominator, a Legendre symbol of one does certify a quadratic residue.

Let $p$ be an odd prime and let $a,b,c$ be integers with $p\nmid a$. The quadratic congruencehas a solution exactly when its discriminant $\Delta =b^2-4ac$ is zero or a quadratic residue modulo $p$.

Indeed, completing the square gives the equivalent equationMultiplication by $2a$ and translation by $b$ give a bijection of the residue classes, because $2a$ is invertible modulo $p$. Each square root $r$ of $\Delta$ therefore gives exactly one solution $X\equiv (r-b)(2a{)}^{-1}(\mathrm{mod}p)$.

Consequently the number of distinct solutions is $1+(\Delta /p)$, using the Legendre symbol: one for zero discriminant, two for a nonzero quadratic residue, and none for a quadratic nonresidue. The hypotheses matter: if $p\mid a$ the equation can become linear, while at $p=2$ division by $2a$ is unavailable.

Let $p$ be an odd prime and let $D$ be an integer congruent to zero or one modulo four. Some integral binary quadratic form of discriminant of a binary quadratic form $D$ represents $p$ if and only if $D$ is a square modulo $p$.

For necessity, a representing vector $(x,y)$ must have $\gcd (x,y)=1$, since a common divisor greater than one would make its square divide $p$. Bézout's identity completes this vector to the first column of a determinant-one integer matrix. Under that proper equivalence, the leading polynomial coefficient becomes $p$, so the transformed form is $[p,b,c]$. Its discriminant gives $D=b^2-4pc\equiv b^2(\mathrm{mod}p)$.

Conversely, choose a root $b$ modulo $p$ and adjust its parity so $b^2\equiv D(\mathrm{mod}4)$. Adding $p$ changes parity because $p$ is odd. Thenhas integer polynomial coefficients, discriminant $D$ and value $p$ at $(1,0)$. If $D<0$, it is positive definite. If $p\nmid D$, it is also a primitive binary quadratic form: a common divisor of its coefficients would have to be $p$, contradicting $p\nmid D$.

The conclusion concerns some form, not every form of that discriminant. For $D=-20,p=3$, the construction gives $[3,2,2]$, which represents three. The same-discriminant form $[1,0,5]$ does not represent three. Deciding the particular form requires the proper equivalence classes, not only the local square test. When $p\mid D$, imprimitive forms can occur, so primitiveness must be checked separately.

Suppose that $q_1,\dots ,q_r$ listed all prime numbers congruent to seven modulo eight. Put $m=q_1\cdots q_r$, with the empty product equal to one, and defineIf an odd prime $\ell$ divides $N$, then $(8m{)}^2\equiv 2(\mathrm{mod}\ell )$, so the second supplementary law for quadratic reciprocity forces $\ell \equiv 1$ or $7(\mathrm{mod}8)$. Since $N$ is seven modulo eight, at least one of its prime factors is seven modulo eight. But $N\equiv -1(\mathrm{mod}{q}_i)$ for every listed prime, so this prime factor is new. The contradiction proves infinitude.

An odd integer $N$ that is a composite number is an Euler pseudoprime to a base $b$ coprime to $N$ whenwhere the right-hand side is the Jacobi symbol. Here this term refers to the Euler-Jacobi condition, rather than merely requiring the left side to be one of $\pm 1$.

Every odd prime satisfies this congruence by Euler's criterion, because its Jacobi symbol is the Legendre symbol. A composite passing it is therefore a false positive for that base in the Solovay-Strassen primality test. For example, $N=561$ and $b=2$ pass: $2^{40}\equiv 1(\mathrm{mod}561)$ gives $2^{280}\equiv 1$, and $(2/561)=1$. A failed congruence instead supplies an Euler witness.

For an odd prime $p$ and $p\nmid a$, Euler's criterion identifies the Legendre symbol by modular exponentiation:

Thus a quadratic residue gives one and a quadratic nonresidue gives minus one, represented by $p-1$ if a nonnegative remainder is used. The formula also holds when $p\mid a$, because $(p-1)/2>0$ and both sides are zero modulo $p$.^[ref]

For example, modulo seven the exponent is three: $2^3\equiv 1$ confirms that two is a quadratic residue, while $3^3\equiv 6\equiv -1$ confirms that three is a quadratic nonresidue. Modulo eleven the exponent is five, and $2^5=32\equiv 10\equiv -1$ confirms that two is a quadratic nonresidue. The test answers whether a square root exists; it does not itself return the roots $3,4$ of $x^2\equiv 2(\mathrm{mod}7)$.

A short proof needs only Fermat's little theorem and the root bound for a polynomial. Put $m=(p-1)/2$. If $a=x^2\ne 0$ in the prime field, then $a^m=x^{p-1}=1$. There are already $m$ such quadratic residues. The nonzero polynomial $T^m-1$ has polynomial degree $m$, so it has no other polynomial roots. Finally, for every nonzero $a$, Fermat's little theorem gives $(a^m{)}^2=a^{p-1}=1$. Factoring $(a^m-1)(a^m+1)=0$ in the field shows $a^m\in \{1,-1\}$; every quadratic nonresidue must take the remaining value $-1$. This proves the criterion without first finding a primitive root.

For a larger original example, decide whether seven is a quadratic residue modulo the prime number $101$. Exponentiation by squaring computes the required power without listing fifty squares:Therefore $(7/101)=-1$ and $x^2\equiv 7(\mathrm{mod}101)$ has no solution. Each intermediate product is reduced modulo $101$, as in modular exponentiation. The advantage is that exponentiation by squaring uses a number of multiplications proportional to the binary digit length of the exponent rather than testing every potential square root.

The odd prime hypothesis is essential. For the composite modulus nine, $2^{(9-1)/2}=2^4\equiv 7(\mathrm{mod}9)$, which is neither one nor minus one. Although four is a nonzero square modulo nine, $4^4\equiv 4(\mathrm{mod}9)$, so even the square-to-one implication fails. The Jacobi symbol and Euler pseudoprime discuss different questions for odd composite moduli; they do not make this a universal square test.

For an odd integer $N>1$ and a base $b$ coprime to $N$, an Euler witness is a base for whichBy Euler's criterion, this failure cannot occur for an odd prime, so it certifies that $N$ is a composite number.

For example, take $N=15$ and $b=2$. Then $2^7\equiv 8(\mathrm{mod}15)$, while the Jacobi symbol is $(2/15)=(2/3)(2/5)=(-1)(-1)=1$. Thus the base two witnesses the compositeness of fifteen without supplying its factors. If instead $1<\gcd (b,N)<N$, the greatest common divisor already gives a proper divisor, so a primality test can reject before computing this congruence.

Let $p$ be an odd prime and $a$ an integer with $p\nmid a$. Reduceto their least positive residue classes modulo $p$. If exactly $N$ of these representatives exceed $p/2$, Gauss's lemma statesThe symbol on the left is the Legendre symbol. For example, $p=7$ and $a=3$ give representatives $3,6,2$. Exactly one exceeds $7/2$, so $3$ is a quadratic nonresidue modulo $7$.

For a proof, replace every representative above $p/2$ by its negative modulo $p$, obtaining numbers $s_1,\dots ,s_m$ in $\{1,\dots ,m\}$. These numbers are distinct: equality would give $ai\equiv \pm aj(\mathrm{mod}p)$, forcing $i=j$ because $1\le i,j\le m$. They therefore form a permutation of $1,\dots ,m$. Multiplying the signed representatives givesThe factorial is invertible modulo $p$. Cancelling it and applying the Euler criterion proves the lemma. Counting signs can thus replace a potentially large modular exponentiation.

Fix an integer $a>1$ and an odd prime $p$ not dividing $a^2-1$. Thenis a composite number that is a Fermat pseudoprime to base $a$.

For compositeness, factorBoth factors are integers because $p$ is odd, and both exceed one for $a>1$ and $p\ge 3$. Also $N\equiv 1(\mathrm{mod}a)$, so $a$ is coprime to $N$.

By Fermat's little theorem, $a^{2p}\equiv a^2(\mathrm{mod}p)$. Since $a^2-1$ is invertible modulo $p$, this gives $N\equiv 1(\mathrm{mod}p)$. The displayed sum is odd for either parity of $a$, so $2p\mid N-1$. Finally $a^{2p}\equiv 1(\mathrm{mod}N)$, and raising this identity to the integer power $(N-1)/(2p)$ proves $a^{N-1}\equiv 1(\mathrm{mod}N)$.

For $a=2$ and $p=5$, this produces $N=341=11\cdot 31$ and $2^{340}=(2^{10}{)}^{34}\equiv 1(\mathrm{mod}341)$. The explicit restriction on $p$ matters: $a=2,p=3$ instead gives $21$, which fails the base-two test.

A short proof outline connects Gauss's lemma to counting points with integer coordinates. For distinct odd primes $p,q$, define the two floor function sumsThe parity form of Gauss's lemma gives $(q/p)=(-1{)}^M$ and $(p/q)=(-1{)}^N$. In the open rectangle $0<x<p/2$, $0<y<q/2$, the line $y=qx/p$ separates $M$ points below it from $N$ points above it. None lies on the line, because $py=qx$ and coprimality would force $p\mid x$. The total is therefore $(p-1)(q-1)/4$. Combining that count with the parity identities gives quadratic reciprocity.^[ref]

For an odd prime $p$, the least quadratic nonresidue $n(p)$ is the smallest positive integer whose nonzero residue class is a quadratic nonresidue modulo $p$. For example, the nonzero quadratic residues modulo seven are $1,2,4$, so $n(7)=3$.

The least quadratic nonresidue is itself a prime number. Otherwise it has a factorization $n(p)=ab$ with $1<a,b<n(p)$. By minimality, both residue classes are quadratic residues, so $a\equiv u^2$ and $b\equiv v^2(\mathrm{mod}p)$ would give $n(p)\equiv (uv{)}^2(\mathrm{mod}p)$, a contradiction. This illustrates why multiplicative information can constrain a least exceptional integer.

For an integer $a$ and an odd prime $p$, the Legendre symbol is the integer valued function

Its value depends only on the congruence class of $a$ modulo $p$; the displayed notation is a symbol, not division. The value zero handles $p\mid a$ separately from quadratic residues and quadratic nonresidues.^[ref]

For example, $(2/7)=1$, $(3/7)=-1$, $(14/7)=0$, and $(2/11)=-1$. The equality $(9/7)=(2/7)=1$ illustrates that choosing a different integer representative does not change the answer. An arbitrary odd composite denominator uses the Jacobi symbol, not the Legendre symbol. For instance,but two is not a square modulo fifteen: any such square root would also give a square root modulo three, where the only nonzero square is one. A Jacobi symbol of one therefore cannot replace the Legendre symbol's square test.

The Legendre symbol also counts square roots compactly. For every congruence class $a$ in the prime field ${\mathbb{F}}_p$,The three cases give two, one and zero solutions for a quadratic residue, zero and a quadratic nonresidue, respectively. This is useful when counting solutions of modular congruences involving polynomials: a solvability question becomes a sum of Legendre symbols, as in the complete Legendre-symbol sum and quadratic Legendre-symbol correlation.

Let $p$ be an odd prime and $b$ a primitive root modulo $p$. Then $b$ is a primitive root modulo every prime power $p^m$ if and only if it is a primitive root modulo $p^2$. In that caseThe condition at $p^2$ says $b^{p-1}=1+pc$ with $p\nmid c$. The odd-prime case of the lifting-the-exponent lemma, obtained here by repeated use of the binomial theorem and then raising to an exponent not divisible by $p$, givesHere $v_p$ is the prime valuation. To see the induction step, the first term in $(1+p^{r}u{)}^p-1$ has prime valuation $r+1$, while every later term has strictly greater prime valuation when $p$ is odd and $p\nmid u$.

Any return $b^k\equiv 1(\mathrm{mod}{p}^m)$ must have $p-1\mid k$, by its order modulo $p$. Writing $k=(p-1)t$, the displayed valuation forces $p^{m-1}\mid t$, with equality giving a return. This proves the claimed multiplicative order. The reverse implication follows by taking $m=2$.

For an odd prime $p$ and any integers $a,b$, the Legendre symbol obeysIn particular, if $p\nmid a$, then $(a^{-1}/p)=(a/p)$, where $a^{-1}$ is a modular multiplicative inverse. Multiplication by a nonzero square also leaves the Legendre symbol unchanged: $(a{r}^2/p)=(a/p)$ for $p\nmid r$.^[ref]

The subgroup and coset arguments under quadratic residue and quadratic nonresidue prove the sign rule without computing a large power: square times square is square, square times nonsquare is nonsquare, and nonsquare times nonsquare is square. If either factor is zero modulo $p$, both sides of the identity vanish. On ${\mathbb{F}}_p^{\times }$, the Legendre symbol is thus a group homomorphism to $\{1,-1\}$ whose kernel of a group homomorphism is the quadratic residue subgroup. Viewed on all integers, it is a completely multiplicative function and a Dirichlet character modulo $p$.

For an original calculation, factor the numerator $30=2\cdot 3\cdot 5$. Modulo seven, $(30/7)=(2/7)(3/7)(5/7)=1\cdot (-1)\cdot (-1)=1$, agreeing with $30\equiv 2(\mathrm{mod}7)$. Modulo eleven, the signs are instead $-1,1,1$, giving $(30/11)=-1$, agreeing with $30\equiv 8(\mathrm{mod}11)$. The same factorization can therefore certify different square behavior at different prime numbers.

Alternatively, Euler's criterion gives $(ab{)}^{(p-1)/2}\equiv a^{(p-1)/2}{b}^{(p-1)/2}$ modulo $p$. For nonzero factors both sides correspond to signs in $\{1,-1\}$. Since $p$ is odd, these signs are distinct modulo $p$, so the modular congruence proves the asserted equality of integers, not merely an equality of representatives.

For an odd prime $p$, the number of integers $z\in \{1,\dots ,p-2\}$ such that both $z$ and $z+1$ are quadratic residues modulo $p$ isFor example, modulo $11$ the quadratic residues are $1,3,4,5,9$. The qualifying pairs are $(3,4)$ and $(4,5)$, giving $(11-4+1)/4=2$.

Write $\chi$ for the Legendre symbol. On the specified range neither input is zero, so the indicator of the required event is $(1+\chi (z))(1+\chi (z+1))/4$. Expand and sum. The complete Legendre-symbol sum givesThe quadratic Legendre-symbol correlation gives ${\sum }_{z=1}^{p-2}\chi (z)\chi (z+1)=-1$: extending to the full finite field only adds the zero terms at $z=0,-1$. Thus the count is $(p-2-\chi (-1)-1-1)/4$. The first supplementary law for quadratic reciprocity identifies $\chi (-1)=(-1{)}^{(p-1)/2}$ and completes the formula.

For a prime number $p$, the nonzero residue classes form the multiplicative group of the finite field ${\mathbb{F}}_p$. Every class has a unique multiplicative inverse. A class equals its own inverse precisely when $x^2=1$, so $(x-1)(x+1)=0$ in the field and $x=1$ or $x=-1$.

For an odd prime, pair each remaining class with its distinct inverse. Each pair contributes one to the product, leavingFor $p=2$, the same congruence is $1\equiv -1(\mathrm{mod}2)$. This proves Wilson's theorem.

If $x^2\equiv -1(\mathrm{mod}p)$ with $p$ an odd prime, then $x^4\equiv 1$ but $x^2\not\equiv 1$. The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes $4\mid p-1$ necessary.

For sufficiency, suppose $p\equiv 1(\mathrm{mod}4)$ and put $r=(p-1)/2$, an even integer. Pair opposite factors in the factorial:Wilson's theorem gives $(r!{)}^2\equiv -1(\mathrm{mod}p)$, explicitly producing a square root of minus one modulo a prime. Thus

Use the standard theorem on reduction of torsion points on an elliptic curve: at a prime of good reduction, reduction is injective on torsion whose order is prime to that prime. Reduction at $2$ implies that every odd-primary part of the rational torsion subgroup has order dividing $3$. Thus its only possible odd prime is $3$, and its $3$-primary part has order at most $3$. Reduction at $5$ injects the $2$-primary part into a group of order $9$, so that part is trivial. No other primary part can occur.

Consequently the torsion subgroup has order at most three. Since $P_1$ has exact order three,This argument uses only prime-to-residue-characteristic injectivity, and therefore avoids an unjustified claim of full torsion injectivity at the prime $2$.

Begin with two points at distance one. A ruler draws the line through two known points; a compass draws a circle with a known centre and a constructible radius. New points are intersections of such lines and circles. A real number is constructible when it occurs as a coordinate of a point obtained by finitely many such operations; a complex point is constructible when both coordinates are.

If current coordinates lie in a field $K\subseteq \mathbb{R}$, a line-line intersection solves linear equations over $K$, while line-circle or circle-circle intersections reduce to a quadratic equation over $K$. Thus each step requires at most adjoining a square root. Consequently every constructible number lies in a towerConversely field sums and differences are obtained by laying off segments, products and quotients by similar triangles, and a positive square root by the geometric-mean construction in a semicircle. Hence every real number in such a tower is constructible. This proves the quadratic-tower criterion, not merely its necessity.

In particular a constructible algebraic number has degree a power of two. Degree alone is not sufficient in general; the exact criterion is containment in a quadratic tower. Equivalently the Galois group of its normal closure is a finite two-group: a tower's normal closure remains a two-extension, and a two-group admits a chain of subgroups with successive index two, yielding the converse by Galois correspondence.

The standard impossibility results follow. Doubling a unit-volume cube requires $\sqrt[3]{2}$, whose polynomial $X^3-2$ is irreducible by Eisenstein and has degree three. Trisecting an arbitrary angle would in particular trisect $60$ degrees, requiring $2\cos 20^{\circ }$, a root of $X^3-3X-1$. This cubic has no rational root and is irreducible, so this construction is impossible, although some particular angles can be trisected. Squaring the unit circle requires side length $\sqrt{\pi }$, impossible because $\pi$ is transcendental whereas constructible numbers are algebraic.

For a regular $n$-gon, constructibility is equivalent to that of $e^{2\pi i/n}$. The cyclotomic extension is Galois of degree $\phi (n)$, so it is constructible exactly when this degree is a power of two. Writing the prime factorization of $n$ shows the equivalent conditionIndeed odd prime exponents must be one, and each $p_i-1$ must be a power of two. If $2^m+1$ is prime, $m$ must itself be a power of two by factoring when $m$ has an odd divisor. Conversely this factorization makes the cyclotomic Galois group a two-group and provides a quadratic tower. This gives both positive constructions, such as the regular seventeen-gon, and obstructions, such as the regular seven-gon.