Coset Decision Method
Overview
The theorem, which serves as a necessary and sufficient condition for determining if a number is a Carmichael number, can also be usefully applied.
Theorem 1
Let an odd composite number be $n$.
$n$ is a Carmichael number satisfying $\iff$ $p \mid n$ for all primes $p$ such that $p^2 \nmid n$ and $(p-1) \mid (n-1)$.
Proof
Definition of Carmichael Numbers: A natural number $n$ is called a Carmichael number if it satisfies $a^{n} \equiv a \pmod{n}$ for all $1 \le a \le n$.
$( \implies )$
A Carmichael number can be expressed as $n = p_{1} \cdots p_{m}$ for different primes $p_{1} , \cdots , p_{m}$, excluding $2$, and therefore must satisfy $p_{i}^2 \nmid n$.
Since $n$ is a Carmichael number, it follows that $a^{n-1} \equiv 1 \pmod{n}$ and for any $k$, $$ a^{n-1} = n \cdot k + 1 = p_{i} \cdot \left( {{n} \over {p_{i}}} k \right) + 1 $$ therefore $a^{n-1} \equiv 1 \pmod{p_{i}}$.
Properties of Order: For a prime $p$, if $\gcd (a,p)=1$ and $a^{n} \equiv 1 \pmod{p}$ then $\text{ord}_{p} (a) \mid n$
According to the properties of order, $\text{ord}_{p_{i} } (a) $ divides $(n-1)$, and by the Primitive Root Theorem, having at least $1$ primitive roots, for some $a_{i}$, $$ \text{ord}_{p_{i} } (a_{i}) = p_{i} - 1 $$ Therefore, for all $p_{1} , \cdots , p_{m}$, $(p_{i}-1) \mid (n-1)$ must hold.
$( \impliedby )$
Let’s assume $n := p_{1} \cdots p_{m}$.
For all primes $p_{1} , \cdots , p_{m}$ dividing $n$, since $p^2 \nmid n$, $p_{1} , \cdots , p_{m}$ are distinct.
Since $(p-1) \mid (n-1)$, for some integer $k_{i}$, $$ (n-1 ) = ( p_{i} - 1) k_{i} $$ Now, consider $1 \le a \le n$ and whether it divides or does not divide $p_{i}$.
- Case 1. $p_{i} \mid a$
Obviously, $a^{n} \equiv 0 \equiv a \pmod{p_{i}}$ holds. - Case 2. $p_{i} \nmid a$
By Fermat’s Little Theorem, $$ \begin{align*} a^{n} =& a^{ ( p_{i} - 1) k_{i} +1 } \\ =& a^{ ( p_{i} - 1) k_{i} } \cdot a \\ \equiv& 1^{k_{i}} \cdot a \pmod{p_{i}} \\ \equiv& a \pmod{p_{i}} \end{align*} $$
Therefore, in any case, $$ ( a^{n} - a ) \equiv 0 \pmod{ p_{i} } $$ which means that $( a^{n} - a )$ is divisible by $p_{1}, \cdots , p_{m}$. In other words, $( a^{n} - a )$ is divisible by $n= p_{1} \cdots p_{m}$, summarizing we obtain the following. $$ ( a^{n} - a ) \equiv 0 \pmod{ n } $$
■
Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p135. ↩︎