12.3. Applications in Primality Testing

Now, as I said at the beginning of the lecture Fermat's little theorem also forms the basis of very interesting primality testing algorithm. We would not be seeing the full primality testing algorithm, but we will see a part of it. This is the statement of the Fermat's little theorem, which says that if you have a number p which is prime and an integer a; if you have an integer a which is co-prime to p, then for every such integer a, the value of ap - 1 ≡ 1 modulo p.

Fermat's Little Theorem is a significant principle in number theory that applies to prime numbers. It states that for any prime number p and any integer a that is coprime to p, the equation a^(p-1) ≡ 1 (mod p) holds true. In practical terms, this means that if you take any integer that shares no common factors with a prime number (other than 1), raise it to the power of one less than that prime number, and divide by the prime, you will always get a remainder of 1. This theorem is fundamental as it paves the way for algorithms that test the primality of numbers, providing a way to check if a number is prime by testing this condition.

Think of Fermat's Little Theorem as a rule in a club where only members with a special badge (the coprime numbers) are allowed to enter. If you have this badge (a number that's coprime to a prime p), then no matter how many times you loop the door (raise it to the power of p-1), you'll always end up at the same spot (1), indicating that you belong there. This is a simple yet powerful rule that can help you quickly check if others belong (whether a number is prime or not).

So now the question is can I use the theorems statement to check whether a given number n is prime or not, of course, the number n has to be odd, because if I give you n = 2 you can easily verify, you can easily conclude that it is a prime number because that is the only even prime number. But other than that if at all n is a prime number it has to be odd. So now, you are given an odd prime number, it might be an arbitrary large prime number and you want to utilize Fermat's little theorem to verify whether the given number is prime or not.

To test if a number n is prime using Fermat's theorem, you would pick a random integer b that is coprime to n. If b^(n-1) ≡ 1 (mod n), then n might be prime. However, if this condition does not hold, n is definitely composite. This method, while useful, has limitations. A number can meet this condition even if it is not prime (like composite numbers called pseudoprimes), thus making it unreliable as a guaranteed test for primality.

Imagine you're using a simple test to check if a person is trustworthy (prime). You decide to ask them a question (use the number b) that trustworthy people (prime numbers) would answer correctly. If they give the right answer (b^(n-1) ≡ 1 mod n), they might be trustworthy, but you can't be completely sure because untrustworthy people (composite numbers) might also know the answer. Therefore, while this test is a good start, it needs more checks to be truly reliable.

However, it turns out that even if you do so, your primality testing algorithm will fail because there are some very interesting numbers which are called as pseudo primes and Carmichael numbers, which will cause your primality testing algorithm to fail for the case when your n is composite, but you are not able to detect that.

Both pseudoprimes and Carmichael numbers present significant challenges in primality testing. A pseudoprime behaves like a prime for specific bases in Fermat's theorem but is not actually prime. Carmichael numbers are worse; they pass the test for every base that is coprime to them, thus misleading any primality test based on Fermat's theorem. Therefore, simply relying on Fermat's Little Theorem can lead to incorrect conclusions about the primality of a number.

Consider a dedicated actor who can convincingly play the role of a superhero (pseudoprime), fooling the audience only certain times. Now, imagine an even more deceptive actor (Carmichael number) who always plays the role perfectly regardless of the context, making it impossible to tell they are not a hero (prime). In both scenarios, without deeper investigation, one could easily be misled into thinking that they are indeed heroes.

So now, you might be wondering, do Carmichael numbers indeed exist? And if they exist, are they finite? Or are they infinite in number? So, indeed, it turns out that we have lots of Carmichael numbers. In fact, the study of Carmichael numbers itself is a very interesting research topic in number theory.

Carmichael numbers are composite numbers that behave like primes under Fermat's Little Theorem for all bases that are coprime to them. One notable Carmichael number is 561, which can be proven to satisfy Fermat's conditions for every base. The existence of these numbers and their properties is a rich area of study in number theory, exploring how they evade simple checks for primality.

Think of Carmichael numbers as the ultimate con artist in a heist movie. They've mastered every trick and technique to appear innocent and escape detection by all investigative methods (Fermat's test). Just like the cleverest of thieves can slip through the most secure systems, these numbers can pass primality tests that are designed to catch composite numbers, showcasing the intricate challenges in verifying true identity (primality).

--