12.4. Carmichael Numbers and Pseudoprimes

Imagine you are given positive integers b and n and say your n is composite. Now, if it turns out that bn - 1 ≡ 1 modulo n, then I will call my n to be a pseudoprime to the base b. Why I am calling it pseudoprime, because it is a false prime. In the sense even though my n is composite, it satisfies the condition of Fermat's little theorem with respect to the integer b.

A pseudoprime is a composite number that behaves like a prime number under Fermat's little theorem. Specifically, if we take a base b that is coprime to the pseudoprime n, and we find that b^(n-1) is congruent to 1 modulo n, we incorrectly classify n as a prime even though it is not. This is misleading because it meets the condition usually reserved for prime numbers, hence the term "pseudoprime" which means 'false prime.'

Think of a pseudoprime like a deceitful actor in a play. On stage, they project an image of being a hero (a prime), but behind the scenes, they lack the true merit (they are composite). Just like the audience gets fooled into believing in their heroism, a mathematical test can misclassify pseudoprimes as prime numbers.

So, what we are doing here is we are now proposing a modified primality testing algorithm where instead of picking 1 base b, which we had done earlier. We are now randomly picking many bases say m number of bases b to b each of which is co-prime to your given number n you want to check whether the number n is prime or composite.

This modified approach involves selecting multiple bases (rather than just one) which are coprime to n. The primality test checks whether the condition of Fermat's theorem holds for each of these bases. If even one base does not satisfy the condition, we can confidently declare n to be composite. However, if all chosen bases satisfy the condition, we cannot conclude that n is prime due to the existence of certain composite numbers that might still satisfy the condition for all bases.

Imagine you are a detective trying to identify whether a group of people are indeed spies. Instead of asking one person about their background (one base), you decide to question several people (multiple bases). If even one of them has a solid alibi (fails the condition), you know there's a chance they are not all spies. However, if all of them seem legitimate (all satisfying the condition), you could mistakenly trust a spy who has fooled everyone.

So what exactly are Carmichael numbers, so, they are composite numbers, which are pseudoprimes with respect to every base that you can think of. So you pick any base b or any integer b, which is co-prime to your number n still, the condition of Fermat's little theorem will be satisfied.

Carmichael numbers are a special class of composite numbers that behave like primes in that they meet the Fermat's little theorem condition for any base that is coprime to them. This makes them particularly problematic for primality testing algorithms because no matter how many coprime bases you test, they will always appear prime, even though they are not. Therefore, trusting a number that passes this test can lead to false conclusions.

Think of a very convincing con artist who can deceive everyone, no matter how many different people you check for validation. They have a facade that satisfies everyone’s questions and checks, making it seem like they are trustworthy, just like how Carmichael numbers show a false exterior in mathematical tests.

So, let me give you an example of a Carmichael number. So, my claim is that 561 is a Carmichael number. So, you can see that 561 is not a prime number. Because I have written down its prime power factorization, namely, you have 3 factors p1, p2, and p3 (3, 11, 17) for the value n = 561.

The number 561 is a Carmichael number because it satisfies the conditions for all bases coprime to it. The factorization of 561 into its prime factors – 3, 11, and 17 – is used to show that for any integer b that is coprime to 561, b^(560) will be equivalent to 1 modulo 561. This appeals to Fermat's theorem, confirming its status as a Carmichael number.

Consider a famous illusionist who dazzles audiences everywhere with seemingly impossible feats. Just like the illusionist consistently amazes and deceives people, 561 appears to behave like a prime under mathematical scrutiny, tricking even experienced mathematicians into classifying it as prime when, in fact, it is not.

--