[proofplan]
The strategy is to package the Euler pseudoprime condition as membership in a subgroup $H$ of the multiplicative group $(\mathbb{Z}/N\mathbb{Z})^\times$, then invoke Lagrange's theorem on the order of a subgroup. The hypothesis that some base fails the Euler test means $H$ is a proper subgroup, so its order divides $\varphi(N)$ strictly; for a subgroup of prime-power index in a group of order $\varphi(N)$ this forces $|H| \leq \varphi(N)/2$. The complement — the set of bases that detect compositeness — therefore has size at least $\varphi(N)/2$.
[/proofplan]
[step:Fix the ambient group and the candidate subgroup $H$]
Let $N > 1$ be odd and composite. The group of units modulo $N$ is
\begin{align*}
G &:= (\mathbb{Z}/N\mathbb{Z})^\times, \qquad |G| = \varphi(N),
\end{align*}
where $\varphi$ is Euler's totient function. For each unit $b \in G$ the Jacobi symbol $\left(\frac{b}{N}\right) \in \{\pm 1\}$ and the power $b^{(N-1)/2} \in G$ are both well defined. Define
\begin{align*}
H: G &\to \{0, 1\} \\
b &\mapsto \mathbb{1}\!\left[ b^{(N-1)/2} \equiv \left(\tfrac{b}{N}\right) \pmod{N} \right],
\end{align*}
and write
\begin{align*}
H &:= \left\{ b \in G : b^{(N-1)/2} \equiv \left(\tfrac{b}{N}\right) \pmod{N} \right\}
\end{align*}
for the set of bases to which $N$ is an Euler pseudoprime.
[/step]
[step:Verify that $H$ is a subgroup of $G$]
We check the subgroup axioms for $H \subseteq G$.
*Identity.* The unit $1 \in G$ satisfies $1^{(N-1)/2} = 1$ and $\left(\frac{1}{N}\right) = 1$, so $1 \in H$.
*Closure under multiplication.* Let $b_1, b_2 \in H$. The Jacobi symbol is completely multiplicative in the numerator (see [Properties of the Jacobi Symbol](/theorems/???)), so $\left(\frac{b_1 b_2}{N}\right) = \left(\frac{b_1}{N}\right)\left(\frac{b_2}{N}\right)$. Using multiplicativity of exponentiation in the abelian group $G$,
\begin{align*}
(b_1 b_2)^{(N-1)/2} &= b_1^{(N-1)/2} \, b_2^{(N-1)/2} \equiv \left(\tfrac{b_1}{N}\right)\left(\tfrac{b_2}{N}\right) = \left(\tfrac{b_1 b_2}{N}\right) \pmod{N},
\end{align*}
so $b_1 b_2 \in H$.
*Closure under inverses.* Let $b \in H$. The Jacobi symbol takes values in $\{\pm 1\}$, so $\left(\frac{b}{N}\right)^{-1} = \left(\frac{b}{N}\right)$, and $\left(\frac{b^{-1}}{N}\right) = \left(\frac{b}{N}\right)^{-1} = \left(\frac{b}{N}\right)$ by multiplicativity applied to $b \cdot b^{-1} = 1$. Raising the defining congruence $b^{(N-1)/2} \equiv \left(\frac{b}{N}\right)$ to the power $-1$ in $G$ gives
\begin{align*}
(b^{-1})^{(N-1)/2} &= (b^{(N-1)/2})^{-1} \equiv \left(\tfrac{b}{N}\right)^{-1} = \left(\tfrac{b^{-1}}{N}\right) \pmod{N},
\end{align*}
so $b^{-1} \in H$.
Hence $H \leq G$.
[guided]
To apply Lagrange's theorem we must first identify the relevant subgroup inside $G = (\mathbb{Z}/N\mathbb{Z})^\times$. The condition defining an Euler pseudoprime — namely $b^{(N-1)/2} \equiv \left(\tfrac{b}{N}\right) \pmod N$ — is an equation that pairs an exponentiation with a Jacobi symbol, and we check that it is preserved under the group operations.
*Identity.* The element $1 \in G$ satisfies $1^{(N-1)/2} = 1$, and the Jacobi symbol evaluates $\left(\frac{1}{N}\right) = 1$ by definition. So $1 \in H$.
*Multiplication.* Given $b_1, b_2 \in H$, we verify $b_1 b_2 \in H$. The key tool is that both sides of the defining congruence are multiplicative in $b$:
\begin{align*}
(b_1 b_2)^{(N-1)/2} &= b_1^{(N-1)/2}\, b_2^{(N-1)/2} \pmod{N}
\end{align*}
by commutativity in the abelian group $G$, and
\begin{align*}
\left(\tfrac{b_1 b_2}{N}\right) &= \left(\tfrac{b_1}{N}\right)\left(\tfrac{b_2}{N}\right)
\end{align*}
by complete multiplicativity of the Jacobi symbol in its numerator (see [Properties of the Jacobi Symbol](/theorems/???)). Multiplying the two defining congruences for $b_1, b_2$:
\begin{align*}
(b_1 b_2)^{(N-1)/2} &\equiv \left(\tfrac{b_1}{N}\right)\left(\tfrac{b_2}{N}\right) = \left(\tfrac{b_1 b_2}{N}\right) \pmod{N},
\end{align*}
so $b_1 b_2 \in H$.
*Inverses.* For $b \in H$, the values $\left(\frac{b}{N}\right), b^{(N-1)/2}$ are self-inverse in the respective multiplicative sense — the Jacobi symbol lies in $\{\pm 1\}$ (both of which are self-inverse), and inverting the congruence $b^{(N-1)/2} \equiv \left(\frac{b}{N}\right)$ in $G$ gives
\begin{align*}
(b^{-1})^{(N-1)/2} &\equiv \left(\tfrac{b}{N}\right)^{-1} = \left(\tfrac{b^{-1}}{N}\right) \pmod{N},
\end{align*}
using $\left(\frac{b^{-1}}{N}\right) = \left(\frac{b}{N}\right)^{-1}$. Hence $b^{-1} \in H$.
The three subgroup axioms hold, so $H \leq G$.
[/guided]
[/step]
[step:Use the hypothesis to conclude $H$ is a proper subgroup]
By hypothesis, there exists some $b_0 \in G$ with $b_0 \notin H$, i.e.
\begin{align*}
b_0^{(N-1)/2} &\not\equiv \left(\tfrac{b_0}{N}\right) \pmod{N}.
\end{align*}
Hence $H \subsetneq G$.
[/step]
[step:Apply Lagrange's theorem to bound $|H|$]
Since $H \leq G$ is a subgroup of the finite group $G$, by [Lagrange's Theorem](/theorems/???) the order $|H|$ divides $|G| = \varphi(N)$. Writing $|G| = [G : H] \cdot |H|$, the index $[G : H] = |G|/|H|$ is a positive integer. Because $H$ is proper (Step 3), $[G : H] \geq 2$, hence
\begin{align*}
|H| &= \frac{|G|}{[G : H]} \leq \frac{\varphi(N)}{2}.
\end{align*}
[guided]
We have established that $H \leq G$ and $H \neq G$. The quantitative content we want is an upper bound on $|H|$.
[Lagrange's Theorem](/theorems/???) applies to any subgroup of a finite group: it asserts that $|H|$ divides $|G|$. The hypotheses — that $G$ is finite and $H$ is a subgroup — are both in force: $G = (\mathbb{Z}/N\mathbb{Z})^\times$ has $\varphi(N) < \infty$ elements, and $H \leq G$ was verified in Step 2.
The divisibility $|H| \mid \varphi(N)$ means $\varphi(N)/|H|$ is a positive integer, the index $[G : H]$. Because $H$ is a *proper* subgroup (Step 3), $[G : H] \geq 2$, so
\begin{align*}
|H| &\leq \frac{\varphi(N)}{2}.
\end{align*}
This is the divisor-of-a-positive-integer argument: the only way $|H|$ can fail to equal $\varphi(N)$ while still dividing it is to be at most half of it. If $|H|$ were strictly between $\varphi(N)/2$ and $\varphi(N)$, it could not divide $\varphi(N)$.
[/guided]
[/step]
[step:Conclude that at least half the bases detect $N$ as composite]
The set of bases for which $N$ is *not* an Euler pseudoprime is
\begin{align*}
G \setminus H &= \{ b \in G : b^{(N-1)/2} \not\equiv \left(\tfrac{b}{N}\right) \pmod{N} \},
\end{align*}
which has cardinality
\begin{align*}
|G \setminus H| &= |G| - |H| \geq \varphi(N) - \frac{\varphi(N)}{2} = \frac{\varphi(N)}{2}.
\end{align*}
In words: at least $\varphi(N)/2$ of the bases $b$ coprime to $N$ reveal $N$ as composite via the Euler test. This completes the proof.
[/step]
