 Solution

The Chinese remainder theorem says that for pairwise coprime positive moduli $m_i$, the map $\mathbb{Z}/(\prod m_i)\to {\prod }_i\mathbb{Z}/m_i$ is an isomorphism; in particular prescribed residues have a unique solution modulo the product.

Write $n=p^{e}m$, with $e\ge 2$ and $(p,m)=1$. Choose $z\equiv 1+p^{e-1}(\mathrm{mod}{p}^e)$ and $z\equiv 1(\mathrm{mod}m)$. The Chinese remainder theorem supplies $z$. The binomial theorem gives $z^p\equiv 1(\mathrm{mod}{p}^e)$, since every nonconstant term is divisible by $p^e$; also $z^p\equiv 1(\mathrm{mod}m)$. Thus $z^p\equiv 1(\mathrm{mod}n)$, whereas $z\not\equiv 1(\mathrm{mod}n)$. Its multiplicative order is exactly $p$.

For odd $n=\prod p_i^{e_i}$ define the Jacobi symbol $(a/n)={\prod }_i(a/p_i{)}^{e_i}$, using the Legendre symbol, with $(a/1)=1$. It is zero if $a$ shares a prime factor with $n$. For example $(2/9)=(2/3{)}^2=1$, but the square residues modulo nine are $0,1,4,7$, so two is not a square.

For positive odd coprime $u,v$, Jacobi reciprocity isFactor $u=\prod p_i^{a_i}$ and $v=\prod q_j^{b_j}$ and multiply quadratic reciprocity for each prime pair. Its sign exponent is ${\sum }_{i,j}{a}_i{b}_j(p_i-1)(q_j-1)/4$. For odd numbers, $(rs-1)/2\equiv (r-1)/2+(s-1)/2(\mathrm{mod}2)$, so this exponent has the same parity as $(u-1)(v-1)/4$. Multiplicativity of the Legendre symbol gives the two Jacobi products, proving the formula. If $u,v$ are not coprime, both sides of the displayed reciprocity equality are zero.

For the previously constructed $z$, every prime divisor of $n$ sees residue one, so $(z/n)=1$. But $p\nmid (n-1)/2$, because $p\mid n$ and $p$ is odd. The order-$p$ unit therefore has $z^{(n-1)/2}\not\equiv 1(\mathrm{mod}n)$. This supplies a unit failing the proposed test.

Finally the passing units form the kernel of the homomorphismMultiplicativity makes this a homomorphism, and the failing unit shows its kernel is proper. A proper subgroup has index at least two. Hence the test fails on at least half the units modulo $n$.