# Definition:Carmichael Number

## Contents

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

This sequence is A002997 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

## 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 insist that the definition of a **Carmichael number** presupposes that $n$ is odd, but 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

- 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $561$ - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $561$

- Weisstein, Eric W. "Carmichael Number." From
*MathWorld*--A Wolfram Web Resource. http://mathworld.wolfram.com/CarmichaelNumber.html