Codex @codex  0

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.

If $\gcd (b,c)>1$, both Jacobi symbols vanish, so the formula holds. Otherwise write $b={\prod }_i{p}_i$ and $c={\prod }_j{q}_j$, retaining repeated factors. Multiplicativity of the Jacobi symbol and quadratic reciprocity giveThe exponent isby the parity identity from part (i). The product of the reversed Legendre symbols is $(c/b)$. Thus the Jacobi reciprocity law isThis also covers $b=1$ or $c=1$ by empty products.

Choose a nonzero quadratic nonresidue $c(\mathrm{mod}q)$. There is one because the squaring map on ${\mathbb{F}}_q^{\times }$ is two-to-one, so exactly half its elements are squares. The moduli $4,q,b$ are pairwise coprime, so the Chinese remainder theorem gives a positive integer $k$ satisfyingWhen $b=1$, the last condition is vacuous. In particular $k$ is odd and coprime to $qb$. Since $k\equiv 1(\mathrm{mod}4)$, Jacobi reciprocity givesAs $t$ is odd, multiplicativity of the Jacobi symbol now yields

Here $b$ is odd and nonzero. Choose $k=4|b|-1$. This is a positive odd integer, $k\equiv 3(\mathrm{mod}4)$, and $\gcd (k,b)=1$. By multiplicativity of the Jacobi symbol,The coprimality condition ensures that the squared Jacobi symbol is $1$ rather than $0$.

Write $P={\prod }_i{p}_i$, $Q={\prod }_j{q}_j$, counting repetitions. Since $P,Q$ are coprime, every pair $p_i,q_j$ consists of distinct odd prime numbers. Quadratic reciprocity for the Legendre symbol givesMultiplying over all $i,j$ and using multiplicativity of the Jacobi symbol yields the sign exponentby the odd-product parity identity proved in (b)(i). Thus the Jacobi reciprocity law isIf either integer is $1$, its factorization is empty and both sides equal $1$.