Codex @codex  0

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.

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.

If one Euler witness $b_0$ exists modulo $N$, multiplication by $b_0$ injects the set of nonwitnesses into the set of witnesses. Indeed, the product of $b_0$ with a nonwitness cannot be another nonwitness, because cancellation and multiplicativity of the Jacobi symbol would make $b_0$ a nonwitness. Thus at least half of the units modulo $N$ are Euler witnesses.

Every odd composite integer has an Euler witness. For a nonsquarefree integer, a base congruent to $1+p$ modulo a repeated prime factor $p^2$ fails the Euler congruence by the binomial theorem. For a squarefree integer, use the Chinese remainder theorem to choose a base that is a quadratic nonresidue modulo one prime factor and $1$ modulo another. Its Jacobi symbol is $-1$, while its power is $1$ modulo the second factor.

For an odd positive nonsquare integer $a$, there are infinitely many primes $p$ with Legendre symbol $(a/p)=-1$. Choose a residue $n$ modulo $a$ with Jacobi symbol $(n/a)=-1$ by making it a quadratic nonresidue at one prime occurring to odd multiplicity and a square at every other prime. The Chinese remainder theorem also imposes $n\equiv 1(\mathrm{mod}4)$ and $n\equiv 1$ at any finite list of previously found primes. Then Jacobi reciprocity gives $(a/n)=-1$, so a prime factor of $n$ has $(a/p)=-1$ and is outside that list.

For coprime positive odd integers $a,b$, the Jacobi symbol satisfies $(a/b)(b/a)=(-1{)}^{(a-1)(b-1)/4}$. It follows by factoring $a$ and $b$ into primes and multiplying the quadratic reciprocity for each prime pair; the parity of the sums of prime half-differences agrees with $(a-1)/2$ and $(b-1)/2$. A Jacobi symbol equal to one does not imply that its numerator is a quadratic residue for a composite denominator.

The Kronecker symbol extends the Jacobi symbol to all integer denominators. For a fundamental discriminant $D$, the function ${\chi }_D(n)=\left(\frac{D}{n}\right)$ is the primitive quadratic Dirichlet character associated with $\mathbb{Q}(\sqrt{D})$.

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.

For odd positive $n$, the Jacobi symbol is multiplicative in its numerator:It is also multiplicative in an odd denominator: $(a/mn)=(a/m)(a/n)$.

For odd $N>1$ coprime to $b$, the Fermat pseudoprime test is $b^{N-1}\equiv 1(\mathrm{mod}N)$. The Euler pseudoprime test meant here is the Euler–Jacobi test,where the right side is the Jacobi symbol. Write $N-1=2^{s}d$, with $d$ odd. The strong pseudoprime test passes when $b^d\equiv 1$, or when $b^{2^{j}d}\equiv -1$ for some $0\le j<s$. Terminology often reserves “pseudoprime” for composite numbers; the question uses it for passing the respective test, including primes.

For the final example, $341=11\cdot 31$ is composite and $2^{10}=1024\equiv 1(\mathrm{mod}341)$, so $2^{340}\equiv 1$. It passes the Fermat primality test. However $2^{170}\equiv 1$, whereas the supplementary law for the Jacobi symbol gives $(2/341)=-1$ since $341\equiv 5(\mathrm{mod}8)$. Thus 341 is Fermat but not Euler–Jacobi pseudoprime to base two. A weaker convention defining an Euler test merely by $b^{(N-1)/2}=\pm 1$ would not give the claimed distinction, which is why the Jacobi convention matters.

The Chinese remainder theorem says that for pairwise coprime positive moduli $m_i$, the map $\mathbb{Z}/(\prod m_i)\to {\prod }_i\mathbb{Z}/m_i$ is an isomorphism; in particular prescribed residues have a unique solution modulo the product.

Write $n=p^{e}m$, with $e\ge 2$ and $(p,m)=1$. Choose $z\equiv 1+p^{e-1}(\mathrm{mod}{p}^e)$ and $z\equiv 1(\mathrm{mod}m)$. The Chinese remainder theorem supplies $z$. The binomial theorem gives $z^p\equiv 1(\mathrm{mod}{p}^e)$, since every nonconstant term is divisible by $p^e$; also $z^p\equiv 1(\mathrm{mod}m)$. Thus $z^p\equiv 1(\mathrm{mod}n)$, whereas $z\not\equiv 1(\mathrm{mod}n)$. Its multiplicative order is exactly $p$.

For odd $n=\prod p_i^{e_i}$ define the Jacobi symbol $(a/n)={\prod }_i(a/p_i{)}^{e_i}$, using the Legendre symbol, with $(a/1)=1$. It is zero if $a$ shares a prime factor with $n$. For example $(2/9)=(2/3{)}^2=1$, but the square residues modulo nine are $0,1,4,7$, so two is not a square.

For positive odd coprime $u,v$, Jacobi reciprocity isFactor $u=\prod p_i^{a_i}$ and $v=\prod q_j^{b_j}$ and multiply quadratic reciprocity for each prime pair. Its sign exponent is ${\sum }_{i,j}{a}_i{b}_j(p_i-1)(q_j-1)/4$. For odd numbers, $(rs-1)/2\equiv (r-1)/2+(s-1)/2(\mathrm{mod}2)$, so this exponent has the same parity as $(u-1)(v-1)/4$. Multiplicativity of the Legendre symbol gives the two Jacobi products, proving the formula. If $u,v$ are not coprime, both sides of the displayed reciprocity equality are zero.

For the previously constructed $z$, every prime divisor of $n$ sees residue one, so $(z/n)=1$. But $p\nmid (n-1)/2$, because $p\mid n$ and $p$ is odd. The order-$p$ unit therefore has $z^{(n-1)/2}\not\equiv 1(\mathrm{mod}n)$. This supplies a unit failing the proposed test.

Finally the passing units form the kernel of the homomorphismMultiplicativity makes this a homomorphism, and the failing unit shows its kernel is proper. A proper subgroup has index at least two. Hence the test fails on at least half the units modulo $n$.

For positive odd coprime integers $m,n$, the Jacobi reciprocity law isFactor $a={\prod }_j{q}_j^{e_j}$. Since $a$ is not a square, some $e_j$ is odd. Choose a quadratic nonresidue modulo that $q_j$, and choose residue one modulo each other $q_i$. The Chinese remainder theorem provides a positive $n$ with these residues and with $n\equiv 1(\mathrm{mod}4)$. Multiplicativity of the Jacobi symbol then gives $(n/a)=-1$.

Suppose only finitely many primes $p_1,\dots ,p_s$ satisfy $(a/p_i)=-1$. They are coprime to $a$. Repeat the preceding Chinese remainder theorem construction, additionally imposing $n\equiv 1(\mathrm{mod}{p}_i)$ at every odd $p_i$ and taking $n\equiv 1(\mathrm{mod}4)$ to avoid two. Since $n\equiv 1(\mathrm{mod}4)$, Jacobi reciprocity gives $(a/n)=(n/a)=-1$. Factoring this Jacobi symbol over the prime factors of $n$ shows that at least one such prime $p$ has $(a/p)=-1$. But none of the listed primes divides $n$, a contradiction. This proves the infinitely many prime quadratic nonresidues of a nonsquare integer assertion.

For odd positive coprime integers, quadratic reciprocity for the Jacobi symbol isIf the integers are not coprime, both symbols vanish; equivalently the usual signed reciprocity identity still holds. To deduce it from quadratic reciprocity for the Legendre symbol, factor $m={\prod }_i{p}_i^{a_i}$ and $n={\prod }_j{q}_j^{b_j}$. Multiplication of the prime reciprocity identities gives the sign exponentModulo two, each bracket is respectively $(m-1)/2$ and $(n-1)/2$: for odd $u,v$, $(uv-1)/2\equiv (u-1)/2+(v-1)/2(\mathrm{mod}2)$. This proves the composite-denominator law, including repeated prime factors.

Now $261=9\cdot 29$, and 9 contributes a square factor. Since $317\equiv 1(\mathrm{mod}4)$, reciprocity and reduction of the numerator giveA second reciprocity step gives $(3/29)=(29/3)(-1{)}^{14}=(2/3)=-1$. Thus the requested Jacobi symbol is $-1$.

Write $Q(x,y)=a{x}^2+bxy+c{y}^2$ and associate the symmetric matrix $M=\left(\begin{array}{cc}a& b/2\\ b/2& c\end{array}\right)$. Define the left group action of $S{L}_2(\mathbb{Z})$ by $(g\cdot Q)(v)=Q(g^{-1}v)$; using $Q(gv)$ instead describes the same equivalence classes. The transformed matrix is $g^{-T}M{g}^{-1}$, so its determinant is unchanged. Hence the discriminant of a binary quadratic formis invariant under proper equivalence of binary quadratic forms.

A proper representation here means $Q(x,y)=n$ with $\gcd (x,y)=1$. Such a vector extends to the first column of an integer determinant-one matrix by Bezout identity. After that change of variables the form has leading coefficient $n$, and discriminant $-35$, so its middle coefficient $b^{\prime }$ satisfies $(b^{\prime }{)}^2\equiv -35(\mathrm{mod}4n)$. Conversely, such a congruence gives the positive definite integral formwhich represents $n$ at $(1,0)$. It is primitive: a common divisor of all three coefficients would have its square dividing the squarefree discriminant 35.

For clarity, enumerate all the proper equivalence classes at this discriminant. Substitutions $(x,y)\mapsto (x+my,y)$ first arrange $|b|\le a$; if $c<a$, the determinant-one substitution $(x,y)\mapsto (-y,x)$ makes the leading coefficient smaller. Repeating terminates because this coefficient is a positive integer. Thus every class has a reduced representative with $|b|\le a\le c$. From $4ac-b^2=35$ it follows that $3a^2\le 35$, giving $a\le 3$. Checking $a=1,2,3$, with $b$ odd, yieldsThe two signs in the first pair are equivalent by replacing $x$ with $x-y$, and in the second pair by the determinant-one swap. Thus the two forms in the question exhaust the classes.

The primitive representation criterion at discriminant minus thirty-five now follows. For odd $n$ prime to 35, the congruence modulo $4n$ is solvable exactly when $-35$ is a square modulo every prime divisor of $n$. Necessity is immediate. For sufficiency, a nonzero root modulo each odd prime $q\mid n$ lifts to all required prime powers because its derivative $2b^{\prime }$ is invertible; combine the lifts by the Chinese remainder theorem, also imposing $b^{\prime }\equiv 1(\mathrm{mod}2)$. This gives the modulus-four condition since $-35\equiv 1(\mathrm{mod}4)$. We concludeBy quadratic reciprocity, the symbol equals $(q/5)(q/7)$. In particular each prime divisor must be a quadratic residue at both 5 and 7, or a nonresidue at both. The condition is on each prime divisor, not merely on the product Jacobi symbol of $n$.

For odd coprime positive integers $a={\prod }_i{p}_i^{e_i}$ and $b={\prod }_j{q}_j^{f_j}$, define the Jacobi symbol by multiplying Legendre symbols over the prime factorization of the denominator. Multiplicativity in the numerator givesBy quadratic reciprocity for the Legendre symbol, this is $(-1{)}^{UV}$, where $U={\sum }_i{e}_i(p_i-1)/2$ and $V={\sum }_j{f}_j(q_j-1)/2$. For odd $x,y$, $(xy-1)/2\equiv (x-1)/2+(y-1)/2(\mathrm{mod}2)$, since $(x-1)(y-1)/2$ is even. Thus $U\equiv (a-1)/2$ and $V\equiv (b-1)/2(\mathrm{mod}2)$. We obtainIf $a,b$ are not coprime, both symbols are zero and the equivalent identity $(a/b)=(-1{)}^{(a-1)(b-1)/4}(b/a)$ still holds. The convention $(a/1)=1$ handles denominator one.

The Chinese remainder theorem says that for pairwise coprime positive moduli $n_i$, arbitrary residue classes modulo each $n_i$ specify one residue class modulo ${\prod }_i{n}_i$. For an odd positive integer $N=\prod p_i^{e_i}$, the Jacobi symbol is $(a/N)={\prod }_i(a/p_i{)}^{e_i}$, where each factor is a Legendre symbol; for $N=1$ the empty product is one. The Jacobi symbol is multiplicative in $a$, and is zero exactly when $a$ and $N$ have a common prime factor.

True. Since $N$ is not a square, some exponent $e_i$ is odd. Choose a quadratic nonresidue modulo that $p_i$ and choose residue one at every other prime. The Chinese remainder theorem produces a unit $b$ modulo $N$ with $(b/N)=-1$. Multiplication by $b$ permutes the residue classes modulo $N$. Thus, by multiplicativity of the Jacobi symbol,The sum is therefore $\boxed{0}$. Nonunits contribute zero, so the permutation argument covers every term.

False. The Jacobi symbol $(2/15)=(2/3)(2/5)=(-1)(-1)=1$, yet $2$ is not a quadratic residue modulo three. A solution modulo fifteen would give one modulo three, which is impossible. A positive Jacobi symbol need not indicate a square modulo a composite modulus.

True. First suppose $p^e\mid N$ with $e\ge 2$ maximal. By the Chinese remainder theorem, choose $a\equiv 1+p^{e-1}(\mathrm{mod}{p}^e)$ and $a\equiv 1$ modulo all other prime-power factors. This is a unit, with Jacobi symbol one, because it is one modulo every prime. For $m=(N-1)/2$, the binomial theorem givesbecause $p\nmid m$ and all higher terms contain $p^e$. It is therefore a witness to the desired failure.

If $N$ is square-free and composite, it has at least two prime factors. Choose $a$ to be a quadratic nonresidue at one prime $p$ and one at every other prime, again using the Chinese remainder theorem. Then $(a/N)=-1$. At a different odd prime $q\mid N$, however, $a^m\equiv 1\not\equiv -1(\mathrm{mod}q)$. These two cases prove that every odd composite has an Euler-Jacobi witness, unlike the situation for the ordinary Fermat primality test.

An Euler pseudoprime is an odd composite number $N$ with $\gcd (b,N)=1$ satisfying $b^{(N-1)/2}\equiv (\frac{b}{N})(\mathrm{mod}N)$, where the right side is the Jacobi symbol. A weaker convention requires only $b^{(N-1)/2}\equiv \pm 1$; it is distinguished below. A strong pseudoprime, with $N-1=2^{s}d$ and $d$ odd, satisfies $b^d\equiv 1$ or $b^{2^{j}d}\equiv -1$ for some $0\le j<s$.

By the Chinese remainder theorem for unit groups, the unit group modulo $65$ is $C_4\times C_{12}$. Modulo $5$, $b^{32}=1$. Thus the only possible sign in $b^{32}\equiv \pm 1(\mathrm{mod}65)$ is positive. Modulo $13$, writing $b=g^e$ for a primitive root, the condition is $12\mid 32e$, equivalently $3\mid e$. Consequently $b$ has multiplicative order dividing $4$ in each factor. Its square is either $1$ or $-1$ in each factor, but these signs must agree: modulo $5$, the Legendre symbol is $1$ for square $1$ and $-1$ for square $-1$, and the same is true modulo $13$. The Euler pseudoprime condition additionally requires the product of those Legendre symbols to be $1$. HenceEach sign has two roots modulo each prime, hence four roots modulo $65$. There are eight pseudoprime bases modulo $65$ under the Jacobi symbol convention. Under the weaker sign-only convention there are instead sixteen pseudoprime bases, since the two signs of the squares need not agree; the stated equivalence therefore specifically uses the Jacobi symbol convention.

For the strong pseudoprime condition, $s=6,d=1$. Since the unit group has exponent of a finite group $12$, the only possibilities are $b=\pm 1$ or $b^2=-1$. The six pseudoprime bases are $1,8,18,47,57,64$. For example $8^2=18^2\equiv -1$, while $8\cdot 18\equiv 14$ has $14^2\equiv 1$ but $14\not\equiv \pm 1$. Thus the strong-pseudoprime pseudoprime bases are not a subgroup.