= Solution
An <Euler pseudoprime> is an odd <composite number> $N$ with $\gcd(b,N)=1$ satisfying $b^{(N-1)/2}\equiv(\frac bN)\pmod N$, where the right side is the <Jacobi symbol>. A weaker convention requires only $b^{(N-1)/2}\equiv\pm1$; it is distinguished below. A <strong pseudoprime>, with $N-1=2^s d$ and $d$ odd, satisfies $b^d\equiv1$ or $b^{2^j d}\equiv-1$ for some $0\leq j<s$.
By the <Chinese remainder theorem for unit groups>, the <unit group> modulo $65$ is $C_4\times C_{12}$. Modulo $5$, $b^{32}=1$. Thus the only possible sign in $b^{32}\equiv\pm1\pmod{65}$ is positive. Modulo $13$, writing $b=g^e$ for a <primitive root>, the condition is $12\mid32e$, equivalently $3\mid e$. Consequently $b$ has <multiplicative order> dividing $4$ in each factor. Its square is either $1$ or $-1$ in each factor, but these signs must agree: modulo $5$, the <Legendre symbol> is $1$ for square $1$ and $-1$ for square $-1$, and the same is true modulo $13$. The <Euler pseudoprime> condition additionally requires the product of those <Legendre symbols> to be $1$. Hence
$$
\boxed{65\text{ is an Euler pseudoprime to }b\iff b^2\equiv\pm1\pmod{65}.}
$$
Each sign has two roots modulo each <prime>, hence four roots modulo $65$. There are \b[eight <pseudoprime bases>] modulo $65$ under the <Jacobi symbol> convention. Under the weaker sign-only convention there are instead sixteen <pseudoprime bases>, since the two signs of the squares need not agree; the stated equivalence therefore specifically uses the <Jacobi symbol> convention.
For the <strong pseudoprime> condition, $s=6,d=1$. Since the <unit group> has <exponent of a finite group> $12$, the only possibilities are $b=\pm1$ or $b^2=-1$. The six <pseudoprime bases> are $1,8,18,47,57,64$. For example $8^2=18^2\equiv-1$, while $8\cdot18\equiv14$ has $14^2\equiv1$ but $14\not\equiv\pm1$. Thus \b[the strong-pseudoprime <pseudoprime bases> are not a <subgroup>].
Back to article page
