Codex @codex  0

An odd composite $N$ coprime to $b$ is a Fermat pseudoprime to base $b$ when $b^{N-1}\equiv 1(\mathrm{mod}N)$. It is a Carmichael number when this congruence holds for every $b$ coprime to $N$.

Suppose a Carmichael number has $p^a\Vert N$ with $a\ge 2$. The group $(\mathbb{Z}/p^a\mathbb{Z}{)}^{\ast }$ is cyclic, so choose a residue of orderBy the Chinese remainder theorem, extend it to an integer $b$ that is congruent to $1$ modulo every other prime-power factor of $N$. Then $\gcd (b,N)=1$, and the Carmichael congruence forces the order of $b$ modulo $p^a$ to divide $N-1$. In particular $p\mid N-1$, contradicting $p\mid N$. Therefore every Carmichael number is square-free.

Now assume $N$ is square-free. If $p-1\mid N-1$ for every $p\mid N$, then for every $b$ coprime to $N$, Fermat little theorem givesfor each $p\mid N$. The Chinese remainder theorem then gives the congruence modulo $N$, so $N$ is Carmichael.

Conversely, if $N$ is Carmichael, fix $p\mid N$. Choose a primitive root $g$ modulo $p$ and use the Chinese remainder theorem to choose $b\equiv g(\mathrm{mod}p)$ and $b\equiv 1(\mathrm{mod}N/p)$. Then $b^{N-1}\equiv 1(\mathrm{mod}p)$, so the order $p-1$ of $g$ divides $N-1$. This proves the Korselt criterion in the required form:

A Carmichael number cannot have one prime factor because it is composite. If $N=pq$ with distinct primes $p<q$, the condition $q-1\mid pq-1$ implies $q-1\mid p-1$, which is impossible. Hence every Carmichael number has at least three prime factors.

An odd composite number $N$ with $\gcd (b,N)=1$ is a Fermat pseudoprime to base $b$ whenFor $N=35$, the Chinese remainder theorem for unit groups reduces this condition to congruences modulo $5$ and $7$. Modulo $5$, Fermat's little theorem givesso $b^{34}\equiv 1(\mathrm{mod}5)$ exactly when $b\equiv \pm 1(\mathrm{mod}5)$. Modulo $7$, the unit group has order $6$, soThe equation $b^4=1$ in the cyclic group $(\mathbb{Z}/7\mathbb{Z}{)}^{\times }$ has $\gcd (4,6)=2$ solutions, namely $b\equiv \pm 1(\mathrm{mod}7)$.

Combining the two independent sign choices by the Chinese remainder theorem givesand hence

$N$ is a Fermat pseudoprime to base $b$ when it is composite, coprime to $b$, and $b^{N-1}\equiv 1(\mathrm{mod}N)$. Here $N\mid b^k-1$ gives coprimality and $k\mid N-1$, so $b^{N-1}=(b^k{)}^{(N-1)/k}\equiv 1(\mathrm{mod}N)$.

Suppose first that $b$ is not primitive modulo $p^2$. Since it is primitive modulo $p$, its order modulo $p^2$ is then $p-1$, soBecause $p-1$ divides $p^2-1$, the composite number $p^2$ satisfiesit is a Fermat pseudoprime to base $b$ and is divisible by $p^2$. Thus (iii) fails.

Conversely, suppose $b$ is primitive modulo $p^2$ and a base-$b$ pseudoprime $N$ is divisible by $p^a$ with $a\ge 2$. By part (i),The pseudoprime congruence forces this order to divide $N-1$, so in particular $p\mid N-1$. But $p\mid N$, a contradiction. Hence no such pseudoprime exists. This proves (i)$\iff$(iii), and all three statements are equivalent.

The Lagrange root bound over a field says that a nonzero polynomial of degree $r$ over a field has at most $r$ roots. In particular, a polynomial modular congruence of degree $r$ modulo a prime number has at most $r$ incongruent solutions unless all its coefficients vanish modulo that prime.

Suppose that $d$ is good and that the positive integer divisor $e$ divides $d$. The $d$ roots of $X^d-1$ form a finite multiplicative subgroup $H$ of ${\mathbb{F}}_p^{\times }$. By the fact that every finite multiplicative subgroup of a field is cyclic, $H=⟨g⟩$ is a cyclic group of order $d$. The solutions in $H$ of $x^e=1$ areso there are at least $e$ of them. The Lagrange root bound over a field gives at most $e$ roots in all of ${\mathbb{F}}_p$, hence exactly $e$. Thus every divisor of a good number is good.

Now put $n=pq$. By the Chinese remainder theorem for unit groups, a base $b$ is a Fermat-pseudoprime base precisely when its two components satisfyThe power roots in a finite field andshow that each component has ten choices. Therefore there areFermat-pseudoprime bases.

To impose the strong pseudoprime condition, write $n-1=2^{s}m$ with $m$ odd. Since $10\mid n-1$, we have $5\mid m$. In each cyclic group of ten Fermat components, raising to the $m$th power sends five elements to $1$ and five elements to $-1$. A pair of components passes the strong test exactly when their signs agree: the pair $(1,1)$ satisfies the first alternative, and $(-1,-1)$ satisfies the second at $j=0$. Components of opposite sign become $(1,1)$ after squaring and can never jointly equal $-1$. Hence the number of strong-pseudoprime bases is

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

Let $N=pq$ for distinct odd prime numbers $p,q$ with $\gcd (p-1,q-1)=10$. Exactly $100$ unit bases make $N$ a Fermat pseudoprime, and exactly $50$ of these make it a strong pseudoprime. The Fermat bases form $C_{10}\times C_{10}$ under the Chinese remainder theorem for unit groups. If $N-1=2^{s}m$, then $5\mid m$ and $m$ is odd, so the $m$th-power map sends five elements of each $C_{10}$ to $1$ and five to $-1$. The strong condition requires equal signs in both components, giving $5^2+5^2=50$.