= Existence of an Euler witness for every odd composite integer
Every odd composite integer has an <Euler witness>. For a nonsquarefree integer, a base congruent to $1+p$ modulo a repeated prime factor $p^2$ fails the Euler congruence by the <binomial theorem>. For a squarefree integer, use the <Chinese remainder theorem> to choose a base that is a <quadratic nonresidue> modulo one prime factor and $1$ modulo another. Its <Jacobi symbol> is $-1$, while its power is $1$ modulo the second factor.
Back to article page
