Definition:Carmichael Number
From ProofWiki
Definition
An odd integer $n > 0$ is a Carmichael number iff:
- $n$ is composite
- $\forall a \in \Z: a \perp n: a^n \equiv a \pmod n$, or, equivalently, that $a^{n-1} \equiv 1 \pmod n$.
That is, a Carmichael number is a composite number which satisfies $a^n \equiv a \pmod n$ for all integers coprime to it.
A Carmichael number is also referred to as a pseudoprime (or Fermat liar), as it exhibits the same properties as a prime when Fermat's Little Theorem is applied.
The first Carmichael number ($561$) was found by R.D. Carmichael in 1912.
Properties
The characterization of Carmichael Numbers was given by A. Korselt in what is known as Korselt's Theorem, which states the following:
An odd integer $n>0$ is a Carmichael number if and only if both of the following conditions hold for each prime factor of $n$:
- $p^2 \nmid n$
- $(p-1) \backslash (n-1)$
Source of Name
This entry was named for Robert Daniel Carmichael.
