Codex @codex  0

If the positive odd integer $n$ has prime factorizationits Jacobi symbol iswhere each factor is a Legendre symbol; by convention $(a/1)=1$. Thus the symbol is zero exactly when $\gcd (a,n)>1$.

The quadratic reciprocity law for the Jacobi symbol says that for coprime positive odd integers $m,n$,To prove it, write $m={\prod }_i{p}_i^{e_i}$ and $n={\prod }_j{q}_j^{f_j}$. The quadratic reciprocity law for distinct odd primes statesMultiplying this identity over $i,j$ with multiplicities $e_i{f}_j$ gives the required product of Jacobi symbols. Its sign exponent modulo two isbecause multiplication of odd integers adds the quantities $(r-1)/2$ modulo two. This proves the law.

For the requested value, two applications of reciprocity givesince $2019\equiv 7(\mathrm{mod}503)$, $503\equiv 6(\mathrm{mod}7)$, and $6$ is a quadratic nonresidue modulo $7$.

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.

Write $N={\prod }_i{p}_i^{e_i}$ with odd primes $p_i$. The Jacobi symbol iswhere each factor on the right is a Legendre symbol. The supplementary law isFor coprime positive odd $m,n$, quadratic reciprocity givesApplying this with $m=3$ givesFinally, factor $d=2^{e}m$ with $m$ odd. The supplementary laws for $-1$ and $2$, followed by reciprocity on every odd prime factor of $m$, express $(-d/a)$ solely in terms of the residue class of the positive odd integer $a$ modulo $d$ when $d\equiv 0$ or $3(\mathrm{mod}4)$. If $a\equiv b(\mathrm{mod}d)$, all those factors, including the zero cases, agree; hence