Definition:Carmichael Number

From ProofWiki
Jump to navigation Jump to search

Definition

An integer $n > 0$ is a Carmichael number if and only if:

$(1): \quad n$ is composite
$(2): \quad \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 $n$ which satisfies $a^n \equiv a \pmod n$ for all integers $a$ which are coprime to it.


Sequence

The sequence of Carmichael numbers begins:

$561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, \ldots$


Examples

$561$ is a Carmichael Number

$\forall a \in \Z: a \perp 561: a^{561} \equiv a \pmod {561}$

while $561$ is composite.


$1105$ is a Carmichael Number

$\forall a \in \Z: a \perp 1105: a^{1105} \equiv a \pmod {1105}$

while $1105$ is composite.


$1729$ is a Carmichael Number

$\forall a \in \Z: a \perp 1729: a^{1729} \equiv a \pmod {1729}$

while $1729$ is composite.


$2465$ is a Carmichael Number

$\forall a \in \Z: a \perp 2465: a^{2465} \equiv a \pmod {2465}$

while $2465$ is composite.


$41 \, 041$ is a Carmichael Number

$\forall a \in \Z: a \perp 41 \, 041: a^{41 \, 041} \equiv a \pmod {41 \, 041}$

while $41 \, 041$ is composite.


$294 \, 409$ is a Carmichael Number

$\forall a \in \Z: a \perp 294 \, 409: a^{294 \, 409} \equiv a \pmod {294 \, 409}$

while $294 \, 409$ is composite.


$509 \, 033 \, 161$ is a Carmichael Number

$\forall a \in \Z: a \perp 509 \, 033 \, 161: a^{509 \, 033 \, 161} \equiv a \pmod {509 \, 033 \, 161}$

while $509 \, 033 \, 161$ is composite.


Also:

$509 \, 033 \, 161 = 1729 \times 294 \, 409$

while both $1729$ and $294 \, 409$ are themselves Carmichael numbers.


Also defined as

Some sources define a Carmichael number with the stipulation that $n$ is odd.

However, this follows from Korselt's Theorem so it is not necessary to state this.


Also known as

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.

Because this property holds for all $a$ coprime to $n$, it is also referred to as an absolute pseudoprime.


Also see

  • Results about Carmichael numbers can be found here.


Source of Name

This entry was named for Robert Daniel Carmichael.


Historical Note

The first Carmichael number ($561$) was found by Robert Daniel Carmichael in $1910$.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Carmichael_Number&oldid=652742"