Proof. Assume that for all positive integers not exceeding $n$ and relatively prime to $n$, that
$$b^{(n-1) / 2} \equiv\left(\frac{b}{n}\right)(\bmod n)$$

Squaring both sides of this congruence tells us that
$$b^{n-1} \equiv\left(\frac{b}{n}\right)^{2} \equiv( \pm 1)^{2}=1(\bmod n)$$
if $(b, n)=1$. Hence, $n$ must be a Carmichael number. Therefore, from Theorem 8.21, we know that $n=q_{1} q_{2} \cdots q_{r}$, where $q_{1}, q_{2}, \ldots, q_{r}$ are distinct odd primes.

We will now show that
$$b^{(n-1) / 2} \equiv 1(\bmod n)$$
for all integers $b$ with $1 \leqslant b \leqslant n$ and $(b, n)=1$. Suppose that $b$ is an integer such that
$$b^{(n-1) / 2} \equiv-1(\bmod n)$$

We use the Chinese remainder theorem to find an integer $a$ with $1<a<n,(a, n)=1$, and
$$\begin{aligned} a & \equiv b\left(\bmod q_{1}\right) \\ a & \equiv 1\left(\bmod q_{2} q_{3} \cdots q_{r}\right) \end{aligned}$$

Then, we observe that
$$a^{(n-1) / 2} \equiv b^{(n-1) / 2} \equiv-1\left(\bmod q_{1}\right)$$
while
$$a^{(n-1) / 2} \equiv 1\left(\bmod q_{2} q_{3} \cdots q_{r}\right)$$

From congruences (9.12) and (9.13), we see that
$$a^{(n-1) / 2} \not \equiv \pm 1(\bmod n)$$
contradicting congruence (9.11). Hence, we must have
$$b^{(n-1) / 2} \equiv 1(\bmod n)$$
for all $b$ with $1 \leqslant b \leqslant n$ and $(b, n)=1$. Consequently, from the definition of an Euler pseudoprime, we know that
$$b^{(n-1) / 2} \equiv\left(\frac{b}{n}\right)=1(\bmod n)$$
for all $b$ with $1 \leqslant b \leqslant n$ and $(b, n)=1$. However, Lemma 9.3 tells us that this is impossible. Hence, the original assumption is false. There must be at least one integer $b$ with $1<b<n,(b, n)=1$, and
$$b^{(n-1) / 2} \not \equiv\left(\frac{b}{n}\right)(\bmod n)$$