# Fermat's Little Theorem and Carmichael Numbers

Fermat's little theorem states that if $$p$$ is a prime number and $$a$$ is a positive integer, then $$p|a^p-a$$.

However, the converse is false, that is, for integers $$a$$ and $$p$$, if $$p|a^p-a$$, then $$a$$ is a prime number, is a false statement. For instant, $$561|a^{561}-a$$ for some integer $$a$$, but $$561$$ is actually a composite number, and such numbers are called "Carmichael numbers".

In other words, a Carmichael number is a composite integer, say $$k$$, such that $$k|a^k-a$$ for all integers $$a$$.

This is what I know, am I right or I misunderstand something?

and

Do we have a way to find Carmichael numbers?

• Search the web for find Carmicael numbers maths.lancs.ac.uk/jameson/carfind.pdf Nov 28 '18 at 17:04
• There is a nice criterion for a squarefree odd composite $N>1$ : $N$ is a Carmichael number if and only if $p-1\mid N-1$ holds for every prime $p\mid N$. If $N$ is not squarefree odd and composite, it cannot be a Carmichael number. Moreover, it can be shown that $N$ must have at least three prime factors. Nov 28 '18 at 19:00

Numbers of the form $$(6k+1)(12k+1)(18k+1)$$ are Carmichael numbers if each of the three factors is prime. This gives some examples - already $$k=1$$ works. Actually, the sequence A046025 gives more values, e.g.,
$$k=1, 6, 35, 45, 51, 55, 56, 100, 121, 195, 206, 216, 255, 276, 370, 380, 426, 506, 510, 511, 710, 741, 800, 825, 871, 930, 975, 1025, 1060, 1115, 1140, 1161, 1270, 1280, 1281, 1311, 1336, 1361, 1365, 1381, 1420, 1421, 1441, 1490, 1515, 1696, 1805, 1875, 1885$$