Carmichael number

In number theory a Carmichael number is a composite positive integer <math>n</math>, which satisfies the congruence <math>b^{n-1}\equiv 1\pmod{n}</math> for all integers <math>b</math> which are relatively prime to <math>n</math>. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after Robert Carmichael.

All prime numbers <math>p</math> satisfy <math>b^{p-1}\equiv 1\pmod{p}</math> for all integers <math>b</math> which are relatively prime to <math>p</math>. This has been proven by the famous mathematician Pierre de Fermat. In most cases if a number <math>n</math> is composite, it does not satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number.