1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Search the web for find Carmicael numbers maths.lancs.ac.uk/jameson/carfind.pdf $\endgroup$ – Ethan Bolker Nov 28 '18 at 17:04
  • $\begingroup$ 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. $\endgroup$ – Peter Nov 28 '18 at 19:00
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.