Proof. From the congruence $n \equiv 3(\bmod 4)$, we know that $n-1=2^{2} \cdot t$ where $t=(n-1) / 2$ is odd. Since $n$ is an Euler pseudoprime to the base $b$, it follows that
$$b^{t}=b^{(n-1) / 2} \equiv\left(\frac{b}{n}\right)(\bmod n)$$

Since $\quad\left(\frac{b}{n}\right)= \pm 1, \quad$ we know that either $\quad b^{t} \equiv 1(\bmod n) \quad$ or $b^{t} \equiv-1(\bmod n)$. Hence, one of the congruences in the definition of a strong pseudoprime to the base $b$ must hold. Consequently, $n$ is a strong pseudoprime to the base $b$.