Carmichael Number/Examples/294,409

From ProofWiki
Jump to navigation Jump to search

Example of Carmichael Number

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


Proof

We have that:

$294 \, 409 = 37 \times 73 \times 109$


First note that $294 \, 409$ is square-free.

Hence the square of none of its prime factors is a divisor of $294 \, 409$:

$\forall p \divides 294 \, 409: p^2 \nmid 294 \, 409$


We also see that:

\(\displaystyle 294 \, 408\) \(=\) \(\displaystyle 2^3 \times 3^3 \times 29 \times 47\)
\(\displaystyle \) \(=\) \(\displaystyle 8178 \times 36\)
\(\displaystyle \) \(=\) \(\displaystyle 4089 \times 72\)
\(\displaystyle \) \(=\) \(\displaystyle 2726 \times 108\)

Thus $294 \, 409$ is a Carmichael number by Korselt's Theorem.

$\blacksquare$


Sources