= Solution
Put $e=(N-1)/2$. The odd integer $N$ is an <Euler pseudoprime> to the <coprime> base $b$ when
$$
b^e\equiv\left(\frac bN\right)\pmod N,
$$
where $(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 witness>[Euler witnesses] that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ <injective function>[injectively] into $W$: indeed, if $b\in E$ and $bb_0$ also lay in $E$, then the <multiplicativity of the Jacobi symbol> would give
$$
b^eb_0^e\equiv\left(\frac bN\right)\left(\frac {b_0}N\right)\pmod N.
$$
Cancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\geq |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 integer>[squarefree], choose an odd <prime number> $p$ with $p^2\mid N$. The <Chinese remainder theorem> gives a unit $b$ such that $b\equiv1+p\pmod {p^a}$ for the full power $p^a\mid N$ and $b\equiv1$ modulo every other prime-power factor. The <binomial theorem> gives
$$
b^e\equiv(1+p)^e\equiv1+ep\pmod {p^2}.
$$
Since $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\equiv1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv1\pmod q$, so the Euler congruence again fails. This proves the <existence of an Euler witness for every odd composite integer>.
Back to article page
