Pseudoprimes and Carmichael Numbers

Section 5.5 Pseudoprimes and Carmichael Numbers

Definition 5.5.1.

The number \(n\) is called a pseudoprime, provided \(n\) is composite and satisfies \(2^n\equiv 2\pmod{n}.\) The number \(n\) is called an absolute pseudoprime (or Carmichael Number), provided \(n\) is composite and satisfies \(a^n \equiv a\pmod{n}\) for all \(a\in\mathbb{Z}.\)

Example 5.5.2.

The composite number \(341 = 11\cdot 31\) is a pseudoprime. Note that \(2^{10} = 1024 = 31\cdot 33 + 1.\) So

\begin{equation*} 2^{11} = 2(2^{10})\equiv 2\pmod{31}, \end{equation*}

and

\begin{equation*} 2^{31} = 2(2^{10})^3\equiv 2\pmod{11}, \end{equation*}

so by the above corollary,

\begin{equation*} 2^{341} = 2\cdot 2^{11\cdot 31} \equiv 2 \pmod{31\cdot 11}. \end{equation*}

Definition 5.5.3.

An integer \(n\) is square-free provided that for any \(p\vert n, \) \(p^2\vert n.\)

Theorem 5.5.4.

Let \(n\) be a composite square-free integer, say, \(n = p_1p_2...p_r, \) where \(p_i\) are distinct primes. If \(p_i-1\vert n-1, \) for \(i = 1,..., r, \) then \(n\) is a Carmichael number.

Proof.

Suppose that \(a\in\mathbb{Z}\) with \(\gcd(a, n) = 1.\) So \(\gcd(a, p_i) = 1\) for each \(i.\) Then Fermat's Little Theorem gives \(p_i\vert a^{n-1}-1.\) Since \(p_i-1\vert n-1,\) we have that \(p_i\vert a^{n-1}-1,\) and so \(p_i\vert a^n-a\) for all \(a,\) and each \(i.\) Since the \(p_i\) are prime, we have that \(n\vert a^n-a\) for all \(a\) and so \(n\) is a Carmichael number.