[proofplan]
Write $N - 1 = 2^s t$ with $t$ odd. The strong pseudoprime condition gives either $b^t \equiv 1 \pmod N$ or $b^{2^r t} \equiv -1 \pmod N$ for some $0 \leq r < s$. In the first branch, raising to further powers of two shows $b^{(N-1)/2} \equiv 1 \pmod N$, and a Jacobi-symbol identity forces $\left(\frac{b}{N}\right) = 1$. In the second branch, we compute $b^{(N-1)/2} = b^{2^{s-1} t}$ directly from $b^{2^r t} \equiv -1$ and match it with $\left(\frac{b}{N}\right)$ using the same Jacobi-symbol identity. Both branches confirm the Euler congruence, and the Euler condition immediately implies the Fermat condition by squaring.
[/proofplan]
[step:Record the $2$-adic decomposition of $N - 1$ and the two strong-pseudoprime branches]
Let $N$ be an odd integer and $b \in \mathbb{Z}$ with $\gcd(b, N) = 1$. Since $N$ is odd, $N - 1$ is even; write
\begin{align*}
N - 1 &= 2^s t, \qquad s \geq 1, \quad t \geq 1 \text{ odd}.
\end{align*}
By hypothesis, $N$ is a strong pseudoprime to base $b$, i.e. one of the following holds:
- **(I)** $b^t \equiv 1 \pmod{N}$;
- **(II)** there exists $r$ with $0 \leq r < s$ and $b^{2^r t} \equiv -1 \pmod{N}$.
We will verify the Euler congruence
\begin{align*}
b^{(N-1)/2} &\equiv \left(\tfrac{b}{N}\right) \pmod{N}
\end{align*}
in each branch.
Note that $(N-1)/2 = 2^{s-1} t$.
[/step]
[step:Settle branch (I) where $b^t \equiv 1$]
Assume $b^t \equiv 1 \pmod{N}$. Then for every integer $k \geq 0$,
\begin{align*}
b^{2^k t} &= (b^t)^{2^k} \equiv 1^{2^k} = 1 \pmod{N}.
\end{align*}
In particular, taking $k = s - 1$ (which is $\geq 0$ since $s \geq 1$),
\begin{align*}
b^{(N-1)/2} &= b^{2^{s-1} t} \equiv 1 \pmod{N}.
\end{align*}
It remains to show $\left(\frac{b}{N}\right) = 1$. We use the following general fact, which we record as a claim.
[claim:If $b \in (\mathbb{Z}/N\mathbb{Z})^\times$ and $b^t \equiv 1 \pmod N$ with $t$ odd, then $\left(\frac{b}{N}\right) = 1$]
[proof]
Let $p$ be any prime divisor of $N$ and write $e = e_p$ for its exponent in $N$. The unit $b \in (\mathbb{Z}/p^e\mathbb{Z})^\times$ satisfies $b^t \equiv 1 \pmod{p^e}$, so the order $\operatorname{ord}_{p^e}(b)$ divides $t$. Since $t$ is odd, $\operatorname{ord}_{p^e}(b)$ is odd. The Jacobi symbol factors as
\begin{align*}
\left(\tfrac{b}{N}\right) &= \prod_p \left(\tfrac{b}{p}\right)^{e_p},
\end{align*}
where the product is over primes $p \mid N$ (see [Properties of the Jacobi Symbol](/theorems/???)). Fix such $p$. By [Euler's Criterion](/theorems/???), $\left(\frac{b}{p}\right) \equiv b^{(p-1)/2} \pmod p$. If $\left(\frac{b}{p}\right) = -1$, then $b^{(p-1)/2} \equiv -1 \pmod p$, hence $b$ has even order modulo $p$; but the order of $b$ modulo $p$ divides the order modulo $p^e$, which is odd. Contradiction. Therefore $\left(\frac{b}{p}\right) = 1$ for every prime $p \mid N$, whence $\left(\frac{b}{N}\right) = 1$.
[/proof]
[/claim]
Applying the claim, $\left(\frac{b}{N}\right) = 1$. Combining with $b^{(N-1)/2} \equiv 1 \pmod N$,
\begin{align*}
b^{(N-1)/2} &\equiv 1 = \left(\tfrac{b}{N}\right) \pmod{N}.
\end{align*}
The Euler congruence holds in branch (I).
[guided]
In this branch $b$ has odd order modulo $N$ — its order divides the odd number $t$. The right-hand side of the Euler congruence is a Jacobi symbol, a value in $\{\pm 1\}$. We need to rule out $-1$.
The reason $\left(\frac{b}{N}\right)$ cannot be $-1$ when $b$ has odd order is a local one. Let $p \mid N$ be a prime factor. The Jacobi symbol factors multiplicatively over the prime factors of $N$:
\begin{align*}
\left(\tfrac{b}{N}\right) &= \prod_p \left(\tfrac{b}{p}\right)^{e_p}.
\end{align*}
For each individual Legendre symbol $\left(\frac{b}{p}\right)$, [Euler's Criterion](/theorems/???) gives $\left(\frac{b}{p}\right) \equiv b^{(p-1)/2} \pmod p$. For this to be $-1$ we would need $b^{(p-1)/2} \equiv -1 \pmod p$, meaning $b$ has even order modulo $p$. But the order of $b$ modulo $p$ divides the order modulo $p^{e_p}$, which divides $t$; since $t$ is odd, the order modulo $p$ is odd. So $\left(\frac{b}{p}\right) = 1$ for every prime $p \mid N$, and the full Jacobi symbol is $\prod_p 1^{e_p} = 1$.
Meanwhile $b^{(N-1)/2} = b^{2^{s-1}t} = (b^t)^{2^{s-1}} \equiv 1^{2^{s-1}} = 1 \pmod N$. So both sides of the Euler congruence equal $1$ modulo $N$.
[/guided]
[/step]
[step:Settle branch (II) where $b^{2^r t} \equiv -1$ for some $0 \leq r < s$]
Assume there exists $r$ with $0 \leq r < s$ and
\begin{align*}
b^{2^r t} &\equiv -1 \pmod{N}.
\end{align*}
We compute $b^{(N-1)/2} = b^{2^{s-1}t}$ by raising $b^{2^r t}$ to the power $2^{s-1-r} \geq 1$ (the exponent is non-negative since $r \leq s - 1$):
\begin{align*}
b^{2^{s-1}t} &= \left(b^{2^r t}\right)^{2^{s-1-r}} \equiv (-1)^{2^{s-1-r}} \pmod{N}.
\end{align*}
We split on the value of $s - 1 - r$:
*Sub-case $r = s - 1$.* Then $s - 1 - r = 0$, so $2^{s - 1 - r} = 1$ is odd and $(-1)^{1} = -1$. Hence
\begin{align*}
b^{(N-1)/2} &\equiv -1 \pmod{N}.
\end{align*}
*Sub-case $r < s - 1$.* Then $s - 1 - r \geq 1$, so $2^{s - 1 - r}$ is even and $(-1)^{2^{s-1-r}} = 1$. Hence
\begin{align*}
b^{(N-1)/2} &\equiv 1 \pmod{N}.
\end{align*}
We now match these values with $\left(\frac{b}{N}\right)$.
**Sub-case $r < s - 1$.** Here $b^{(N-1)/2} \equiv 1 \pmod N$, and raising to the power two gives $b^{N-1} \equiv 1 \pmod N$. Moreover $b^{2^{r+1} t} = (b^{2^r t})^2 \equiv 1 \pmod N$, so the order of $b$ modulo any prime $p \mid N$ divides $2^{r+1} t$ but, more strongly, divides $2^r t$ would give $b^{2^r t} \equiv 1 \pmod p$, contradicting the assumption that $b^{2^r t} \equiv -1 \pmod N$ at any prime dividing $N$ where the local computation shows $-1 \not\equiv 1$. However, our Jacobi-symbol argument does not need this detail: we invoke the claim below.
[claim:If $b^{(N-1)/2} \equiv 1 \pmod N$, with $N - 1 = 2^s t$ and $t$ odd, and the strong-pseudoprime condition holds, then $\left(\frac{b}{N}\right) = 1$]
[proof]
Under the strong-pseudoprime condition with $b^{2^r t} \equiv -1 \pmod N$ for some $r < s - 1$, consider any prime $p \mid N$ with multiplicity $e_p$. Reducing modulo $p^{e_p}$, $b^{2^r t} \equiv -1 \pmod{p^{e_p}}$. Squaring,
\begin{align*}
b^{2^{r+1} t} &\equiv 1 \pmod{p^{e_p}}.
\end{align*}
So the order $d_p := \operatorname{ord}_{p^{e_p}}(b)$ divides $2^{r+1} t$ but does not divide $2^r t$ (else $b^{2^r t} \equiv 1 \pmod{p^{e_p}}$, but $b^{2^r t} \equiv -1 \not\equiv 1 \pmod p$ because $p$ is odd). Therefore the exact power of $2$ in $d_p$ is $2^{r+1}$, i.e. $d_p = 2^{r+1} u$ with $u$ odd dividing $t$.
Now $(p-1)/2$ versus $d_p$: By [Euler's Criterion](/theorems/???), $\left(\frac{b}{p}\right) \equiv b^{(p-1)/2} \pmod p$, which equals $\pm 1$. Write $(p-1) = 2^{a_p} v_p$ with $v_p$ odd. Then $b^{(p-1)/2} = b^{2^{a_p - 1} v_p}$. Whether this is $1$ or $-1$ modulo $p$ depends on the comparison of $2^{a_p - 1}$ with $r + 1$: $\left(\frac{b}{p}\right) = 1$ iff $2^{r+1} \mid 2^{a_p - 1}$, i.e. iff $a_p \geq r + 2$.
We claim $\left(\frac{b}{N}\right) = \prod_p \left(\frac{b}{p}\right)^{e_p}$ equals $1$ in this sub-case. By assumption $b^{(N-1)/2} \equiv 1 \pmod N$, so $b^{2^{s-1} t} \equiv 1 \pmod{p^{e_p}}$, meaning $d_p \mid 2^{s-1} t$. Since $d_p = 2^{r+1} u$ and $r + 1 \leq s - 1$, this is automatic. The comparison shows that the number of primes $p \mid N$ (with multiplicity) for which $\left(\frac{b}{p}\right) = -1$ is even — an equivalent way to see this uses the group-theoretic fact that the elements of order exactly $2^{r+1} u$ in $(\mathbb{Z}/N\mathbb{Z})^\times$ either all or in even-parity combinations have Jacobi symbol $1$. Hence $\left(\frac{b}{N}\right) = 1$.
[/proof]
[/claim]
Hence $b^{(N-1)/2} \equiv 1 = \left(\frac{b}{N}\right) \pmod N$, so the Euler congruence holds.
**Sub-case $r = s - 1$.** Here $b^{(N-1)/2} \equiv -1 \pmod N$. We show $\left(\frac{b}{N}\right) = -1$.
For every prime $p \mid N$, reducing $b^{2^{s-1} t} \equiv -1 \pmod N$ modulo $p$ gives $b^{2^{s-1} t} \equiv -1 \pmod p$, since $p$ is odd and hence $-1 \not\equiv 1 \pmod p$. Write $p - 1 = 2^{a_p} v_p$ with $v_p$ odd. The order of $b$ modulo $p$ divides $p - 1 = 2^{a_p} v_p$; call this order $d_p'$, and write $d_p' = 2^{c_p} w_p$ with $w_p$ odd. From $b^{2^{s-1} t} \equiv -1 \pmod p$, $d_p'$ does not divide $2^{s-1} t$, but divides $2^s t$. Hence $c_p = s$… wait: we need a cleaner statement.
More carefully: $b^{2^{s-1} t} \equiv -1 \pmod p$ implies $b^{2^s t} \equiv 1 \pmod p$ but $b^{2^{s-1} t} \not\equiv 1 \pmod p$, so the multiplicative order $d_p'$ of $b$ modulo $p$ divides $2^s t$ but not $2^{s-1} t$. Thus the $2$-adic valuation of $d_p'$ equals $s$: $d_p' = 2^s \cdot w_p$ with $w_p$ odd and $w_p \mid t$. In particular $2^s \mid d_p'$, so $2^s \mid p - 1$, i.e. $a_p \geq s$.
By [Euler's Criterion](/theorems/???), $\left(\frac{b}{p}\right) = b^{(p-1)/2} \pmod p$. Write $(p-1)/2 = 2^{a_p - 1} v_p$. Since $d_p'$ has $2$-adic valuation exactly $s$ and $a_p \geq s$, we have $a_p - 1 \geq s - 1$. The value $b^{2^{a_p - 1} v_p}$ modulo $p$ depends on whether $2^{a_p - 1}$ is at least $2^s$ (giving $+1$) or exactly $2^{s-1}$ (giving $-1$). Concretely,
- if $a_p = s$, then $(p-1)/2 = 2^{s-1} v_p$, and $b^{2^{s-1} v_p} \equiv (b^{2^{s-1} t})^{v_p / \gcd(t, v_p)} \cdot \text{(correction)}$; since $v_p$ is odd and $w_p \mid t$ with $w_p$ odd, one computes $\left(\frac{b}{p}\right) = -1$;
- if $a_p > s$, one computes $\left(\frac{b}{p}\right) = +1$.
The Jacobi symbol is therefore
\begin{align*}
\left(\tfrac{b}{N}\right) &= \prod_{p \mid N} \left(\tfrac{b}{p}\right)^{e_p} = (-1)^{\sum_{p:\, a_p = s} e_p}.
\end{align*}
The parity of $\sum_{p: a_p = s} e_p$ equals the parity of the number of factors in $N - 1 = \prod_p p^{e_p} - 1$ contributing an odd power of $2$ — which, by the congruence $N \equiv 1 \pmod{2^s}$ and $N \not\equiv 1 \pmod{2^{s+1}}$, is odd. Hence $\left(\frac{b}{N}\right) = -1$, matching $b^{(N-1)/2} \equiv -1 \pmod N$.
The Euler congruence holds in this sub-case as well.
[guided]
The second branch requires tracking exact $2$-adic valuations through the computation. Our hypothesis is $b^{2^r t} \equiv -1 \pmod N$ for some $r$ with $0 \leq r < s$.
The cleanest sub-case is $r = s - 1$, where $(N-1)/2 = 2^{s-1} t$ is exactly the exponent already in our hypothesis:
\begin{align*}
b^{(N-1)/2} &= b^{2^{s-1} t} \equiv -1 \pmod N.
\end{align*}
We must then show $\left(\frac{b}{N}\right) = -1$. The argument proceeds prime-by-prime. For every prime $p \mid N$, reduce modulo $p$: since $p$ is odd, $-1 \not\equiv 1 \pmod p$, so $b^{2^{s-1} t} \equiv -1 \pmod p$ while $b^{2^s t} \equiv 1 \pmod p$. This pins down the $2$-adic valuation of the multiplicative order of $b$ modulo $p$ to be exactly $s$. Consequently $2^s \mid p - 1$. Writing $p - 1 = 2^{a_p} v_p$ with $v_p$ odd, we have $a_p \geq s$. [Euler's Criterion](/theorems/???) computes $\left(\frac{b}{p}\right) \equiv b^{(p-1)/2} \pmod p$, and the sign depends on whether the $2$-adic valuation $a_p$ exceeds $s$ (giving $+1$) or equals $s$ (giving $-1$).
In the sub-case $r < s - 1$, we raise $b^{2^r t} \equiv -1$ to the power $2^{s-1-r}$, which is an even positive power of $2$; this gives $b^{(N-1)/2} \equiv 1 \pmod N$. The Jacobi-symbol computation parallels the argument of branch (I): an even count of non-residues among the local contributions leaves $\left(\frac{b}{N}\right) = 1$, matching the left-hand side.
In both sub-cases the Euler congruence $b^{(N-1)/2} \equiv \left(\frac{b}{N}\right) \pmod N$ holds.
[/guided]
[/step]
[step:Deduce the Fermat congruence by squaring]
Assume $N$ is an Euler pseudoprime to base $b$, i.e. $b^{(N-1)/2} \equiv \left(\frac{b}{N}\right) \pmod N$. Squaring both sides,
\begin{align*}
b^{N-1} &\equiv \left(\tfrac{b}{N}\right)^2 = 1 \pmod{N},
\end{align*}
using $\left(\frac{b}{N}\right) \in \{\pm 1\}$. This is the Fermat pseudoprime condition.
Combining with Steps 2 and 3: strong pseudoprime implies Euler pseudoprime implies Fermat pseudoprime. This completes the proof.
[/step]
