= 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\geq2$ and $(p,m)=1$. Choose $z\equiv1+p^{e-1}\pmod{p^e}$ and $z\equiv1\pmod m$. The <Chinese remainder theorem> supplies $z$. The binomial theorem gives $z^p\equiv1\pmod{p^e}$, since every nonconstant term is divisible by $p^e$; also $z^p\equiv1\pmod m$. Thus $z^p\equiv1\pmod n$, whereas $z\not\equiv1\pmod 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> is
$$
\boxed{(u/v)=(-1)^{(u-1)(v-1)/4}(v/u).}
$$
Factor $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\pmod2$, 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\equiv1\pmod n$. This supplies a unit failing the proposed test.
Finally the passing units form the <kernel> of the <homomorphism>
$$
F:(\mathbb Z/n\mathbb Z)^\times\longrightarrow(\mathbb Z/n\mathbb Z)^\times,
\qquad F(a)=a^{(n-1)/2}(a/n)^{-1}.
$$
Multiplicativity makes this a <homomorphism>, and the failing unit shows its <kernel> is proper. A proper <subgroup> has index at least two. Hence \b[the test fails on at least half the units modulo $n$].
Back to article page
