= Solution
An odd <composite number> $N$ with $\gcd(b,N)=1$ is a <Fermat pseudoprime> to base $b$ when
$$
b^{N-1}\equiv1\pmod N.
$$
For $N=35$, the <Chinese remainder theorem for unit groups> reduces this condition to congruences modulo $5$ and $7$. Modulo $5$, <Fermat's little theorem> gives
$$
b^{34}=b^{2}\pmod5,
$$
so $b^{34}\equiv1\pmod5$ exactly when $b\equiv\pm1\pmod5$. Modulo $7$, the unit group has order $6$, so
$$
b^{34}=b^4\pmod7.
$$
The equation $b^4=1$ in the cyclic group $(\mathbb Z/7\mathbb Z)^\times$ has $\gcd(4,6)=2$ solutions, namely $b\equiv\pm1\pmod7$.
Combining the two independent sign choices by the Chinese remainder theorem gives
$$
\begin{array}{c|c|c}
b\pmod5&b\pmod7&b\pmod{35}\\ \hline
1&1&1\\
1&-1&6\\
-1&1&29\\
-1&-1&34
\end{array}
$$
and hence
$$
\boxed{35\text{ is a Fermat pseudoprime to base }b
\iff b\equiv1,6,29,34\pmod{35}}.
$$
Back to article page
