[proofplan]
The set of bases $H := \{b \in (\mathbb{Z}/N\mathbb{Z})^\times : b^{N-1} \equiv 1 \pmod{N}\}$ is a subgroup of $(\mathbb{Z}/N\mathbb{Z})^\times$ because the map $b \mapsto b^{N-1}$ is a group homomorphism whose kernel $H$ is automatically a subgroup. By hypothesis there exists at least one $b_0 \in (\mathbb{Z}/N\mathbb{Z})^\times$ with $b_0 \notin H$, so $H$ is a proper subgroup. Lagrange's theorem then forces $|H|$ to divide $\varphi(N) = |(\mathbb{Z}/N\mathbb{Z})^\times|$ and be strictly smaller, hence $|H| \leq \varphi(N)/2$. Consequently the complement — the bases for which the Fermat test detects $N$ as composite — has cardinality at least $\varphi(N)/2$.
[/proofplan]
[step:Define the set $H$ of Fermat liars in $(\mathbb{Z}/N\mathbb{Z})^\times$]
Fix an odd composite $N > 1$. Denote by $(\mathbb{Z}/N\mathbb{Z})^\times$ the group of units modulo $N$, which consists of the $\varphi(N)$ residue classes coprime to $N$. Define
\begin{align*}
H &:= \{ b + N\mathbb{Z} \in (\mathbb{Z}/N\mathbb{Z})^\times : b^{N-1} \equiv 1 \pmod{N} \}.
\end{align*}
An integer $b$ with $1 \leq b < N$ and $\gcd(b, N) = 1$ is said to be a *Fermat liar* for $N$ if $b + N\mathbb{Z} \in H$; equivalently, $N$ is a Fermat pseudoprime to the base $b$.
[/step]
[step:Show that $H$ is a subgroup of $(\mathbb{Z}/N\mathbb{Z})^\times$]
Consider the map
\begin{align*}
\psi_{N-1}: (\mathbb{Z}/N\mathbb{Z})^\times &\to (\mathbb{Z}/N\mathbb{Z})^\times \\
x &\mapsto x^{N-1}.
\end{align*}
Because $(\mathbb{Z}/N\mathbb{Z})^\times$ is an abelian group (under multiplication modulo $N$), the $(N-1)$-th power map is a group homomorphism: for $x, y \in (\mathbb{Z}/N\mathbb{Z})^\times$,
\begin{align*}
\psi_{N-1}(xy) &= (xy)^{N-1} = x^{N-1} y^{N-1} = \psi_{N-1}(x)\, \psi_{N-1}(y),
\end{align*}
using commutativity to collect like factors. The kernel of $\psi_{N-1}$ is
\begin{align*}
\ker \psi_{N-1} &= \{ x \in (\mathbb{Z}/N\mathbb{Z})^\times : x^{N-1} = 1 \} = H.
\end{align*}
The kernel of a group homomorphism is a subgroup of the domain, so $H \leq (\mathbb{Z}/N\mathbb{Z})^\times$.
[/step]
[step:Use the hypothesis to show $H$ is a proper subgroup]
The hypothesis states that $N$ is not a Fermat pseudoprime to some base. Unpacking the definition: there exists $b_0 \in \mathbb{Z}$ with $1 \leq b_0 < N$, $\gcd(b_0, N) = 1$, and $b_0^{N-1} \not\equiv 1 \pmod{N}$. Hence $b_0 + N\mathbb{Z} \in (\mathbb{Z}/N\mathbb{Z})^\times \setminus H$, so
\begin{align*}
H &\subsetneq (\mathbb{Z}/N\mathbb{Z})^\times.
\end{align*}
[/step]
[step:Apply Lagrange's theorem to bound $|H|$]
By [Lagrange's Theorem](/theorems/???), the order of any subgroup of a finite group divides the order of the group:
\begin{align*}
|H| \mid |(\mathbb{Z}/N\mathbb{Z})^\times| = \varphi(N).
\end{align*}
We verify the hypotheses: $(\mathbb{Z}/N\mathbb{Z})^\times$ is a finite group (of order $\varphi(N) < N$), and $H$ is a subgroup by Step 2. Hence the divisibility conclusion applies.
Since $H \subsetneq (\mathbb{Z}/N\mathbb{Z})^\times$ by Step 3, the index $[(\mathbb{Z}/N\mathbb{Z})^\times : H] = \varphi(N)/|H|$ is a positive integer strictly greater than $1$; in particular, $\varphi(N)/|H| \geq 2$, equivalently,
\begin{align*}
|H| &\leq \frac{\varphi(N)}{2}.
\end{align*}
[guided]
We have just applied [Lagrange's Theorem](/theorems/???), which states: for a subgroup $K$ of a finite group $G$, the order $|K|$ divides $|G|$. Our setting: $G = (\mathbb{Z}/N\mathbb{Z})^\times$ (a finite abelian group of order $\varphi(N)$) and $K = H$ (a subgroup by Step 2). Both hypotheses — $G$ finite and $K \leq G$ — are satisfied, so $|H|$ divides $\varphi(N)$.
Divisibility alone gives $|H| \in \{1, 2, \ldots, \varphi(N)\}$, but we want a sharper statement: $|H| \leq \varphi(N)/2$. Where does the factor of $2$ come from? It is the combination of divisibility with properness. The index $[G : H] = |G|/|H| = \varphi(N)/|H|$ is a positive integer because $|H|$ divides $\varphi(N)$. Because $H \subsetneq G$ (Step 3), we have $|H| < |G|$, so $[G : H] > 1$, which for positive integers means $[G : H] \geq 2$, equivalently
\begin{align*}
|H| &\leq \frac{|G|}{2} = \frac{\varphi(N)}{2}.
\end{align*}
This is the best uniform bound available from Lagrange; the factor of $2$ is tight and would be achieved if $H$ had index exactly $2$.
[/guided]
[/step]
[step:Conclude that at least $\varphi(N)/2$ bases detect $N$ as composite]
The set of bases $b \in \{1 \leq b < N : \gcd(b, N) = 1\}$ to which $N$ is *not* a Fermat pseudoprime corresponds bijectively to
\begin{align*}
(\mathbb{Z}/N\mathbb{Z})^\times \setminus H.
\end{align*}
Its cardinality is
\begin{align*}
|(\mathbb{Z}/N\mathbb{Z})^\times| - |H| &= \varphi(N) - |H| \geq \varphi(N) - \frac{\varphi(N)}{2} = \frac{\varphi(N)}{2}.
\end{align*}
Since the total number of bases in $\{1 \leq b < N : \gcd(b, N) = 1\}$ is $\varphi(N)$, the fraction of bases that detect $N$ as composite is at least $\frac{1}{2}$. This is the claimed statement.
[/step]
