📂Number Theory

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 ¹

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 }$$

■