Carmichael Number/Examples/41,041

From ProofWiki
Jump to navigation Jump to search

Example of Carmichael Number

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


Proof

We have that:

$41,041 = 7 \times 11 \times 13 \times 41$

and so:

\(\ds 7^2 \times 827 + 28\) \(=\) \(\ds 41 \, 041\)
\(\ds \leadsto \ \ \) \(\ds 7^2\) \(\nmid\) \(\ds 41 \, 041\)
\(\ds 11^2 \times 339 + 22\) \(=\) \(\ds 41 \, 041\)
\(\ds \leadsto \ \ \) \(\ds 11^2\) \(\nmid\) \(\ds 41 \, 041\)
\(\ds 13^2 \times 242 + 143\) \(=\) \(\ds 41 \, 041\)
\(\ds \leadsto \ \ \) \(\ds 13^2\) \(\nmid\) \(\ds 41 \, 041\)
\(\ds 41^2 \times 24 + 697\) \(=\) \(\ds 41 \, 041\)
\(\ds \leadsto \ \ \) \(\ds 41^2\) \(\nmid\) \(\ds 41 \, 041\)


We also have that:

\(\ds 41 \, 040\) \(=\) \(\ds 6840 \times \paren {7 - 1}\)
\(\ds \) \(=\) \(\ds 4104 \times \paren {11 - 1}\)
\(\ds \) \(=\) \(\ds 3420 \times \paren {13 - 1}\)
\(\ds \) \(=\) \(\ds 1026 \times \paren {41 - 1}\)

The result follows by Korselt's Theorem.

$\blacksquare$