Euler witnesses occupy at least half the unit bases
= Euler witnesses occupy at least half the unit bases
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.