Codex @codex  0

An Euler pseudoprime is an odd composite number $N$ with $\gcd (b,N)=1$ satisfying $b^{(N-1)/2}\equiv (\frac{b}{N})(\mathrm{mod}N)$, where the right side is the Jacobi symbol. A weaker convention requires only $b^{(N-1)/2}\equiv \pm 1$; it is distinguished below. A strong pseudoprime, with $N-1=2^{s}d$ and $d$ odd, satisfies $b^d\equiv 1$ or $b^{2^{j}d}\equiv -1$ for some $0\le 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 \pm 1(\mathrm{mod}65)$ is positive. Modulo $13$, writing $b=g^e$ for a primitive root, the condition is $12\mid 32e$, 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$. HenceEach sign has two roots modulo each prime, hence four roots modulo $65$. There are 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=\pm 1$ 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\cdot 18\equiv 14$ has $14^2\equiv 1$ but $14\not\equiv \pm 1$. Thus the strong-pseudoprime pseudoprime bases are not a subgroup.

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.

For an odd composite $N$ and a unit $b$ modulo $N$, $N$ is a Fermat pseudoprime to base $b$ whenIt is an Euler pseudoprime to base $b$ whenwhere the right side is the Jacobi symbol.

By the Chinese remainder theorem,and $\phi (105)=2\cdot 4\cdot 6=48$. The condition $b^{104}=1$ is automatic modulo $3$ and $5$. Modulo $7$ it hassolutions. Thus there are $2\cdot 4\cdot 2=16$ Fermat bases, giving proportion

For the Euler condition, $b^{52}=1$ modulo $3$, so the Jacobi symbol must be $+1$. The power condition is automatic modulo $5$, while modulo $7$ it again restricts $b$ to the two solutions of $b^2=1$. For each of those two residues, exactly half of the $2\cdot 4$ choices modulo $3$ and $5$ have Jacobi symbol $+1$. Hence there are $2\cdot 4=8$ Euler bases and proportion