 Existence of an Euler witness for every odd composite integer

Every composite number $N$ that is an odd integer has an Euler witness. There are two cases.

If $p^2$ divides $N$ for a prime number $p$, write $N=p^{e}M$ with $e\ge 2$ and $p\nmid M$. The Chinese remainder theorem chooses $b\equiv 1+p(\mathrm{mod}{p}^e)$ and $b\equiv 1(\mathrm{mod}M)$. This base is a unit modulo $N$ and has Jacobi symbol $(b/N)=1$, because it is one modulo every prime divisor. But with $h=(N-1)/2$, the binomial theorem gives $b^h\equiv 1+hp(\mathrm{mod}{p}^2)$. Since $p\nmid h$, this is not one, so the Euler congruence fails.

If $N$ is squarefree, it has at least two distinct prime factors. Choose $b$ to be a quadratic nonresidue modulo one factor and one modulo every other factor, again by the Chinese remainder theorem. Then $(b/N)=-1$, while $b^{(N-1)/2}$ is one modulo a different prime factor. It therefore cannot equal the Jacobi symbol modulo $N$.