12.1. Discrete Mathematics

Hello everyone, welcome to this lecture, so the plan for this lecture is as follows: in this lecture, we will discuss about Fermat's little theorem, and we will see its application to primality testing, and we will also discuss about Carmichael numbers.

The introduction establishes the main topics of the lecture: Fermat's Little Theorem, its role in testing for prime numbers (primality testing), and the exploration of Carmichael numbers, which are special composite numbers that can mislead primality tests.

Think of a cooking class where the chef introduces the three main dishes (topics) that they will prepare together. Just as knowing what you will make helps you understand the cooking process, knowing these concepts prepares you for how they connect to one another.

So let us begin with Fermat's little theorem so, the theorem says that, if p is a prime number and if a is an integer such that p does not divide a. So, this notation means does not divide: ∤, in other words, a is co-prime to p, then the theorem says that ap - 1 ≡ 1 modulo p.

Fermat's Little Theorem provides a relationship between a prime number p and an integer a (which is not divisible by p). The theorem states that if you raise a to the power of (p-1) and divide it by p, the remainder will be 1. This theorem is foundational in number theory and useful for computations involving large numbers.

Imagine you have a coupon that gives you a deal every time you spend in increments of $p. If you spend$a (which is not a multiple of the coupon value), after $p-1 worth of spending, you'll effectively get a 'reward' back as if you had spent$1 more, which highlights the power of Fermat's theorem in predictable outcomes.

So assume for the moment that this theorem statement is true, let us see an interesting corollary. So, the corollary is ap ≡ a modulo p for every integer a and prime p.

The corollary states that for any integer a, the result of raising a to the power of p will have the same remainder when divided by p as a itself. This broadens the applicability of Fermat's Little Theorem beyond just integers co-prime to p.

Consider borrowing a book from a library (p) with a condition that if you return it after p weeks (p), you don't owe any late fees. Even after extending your borrowing period (raising a to the power of p), you are still only charged as if you had just borrowed it (a).

We can divide the proof into cases so, the corollary is for every integer it is not only for those integers a which are co-prime to p, whereas the Fermat's little theorem is strictly for those integers a which are co-prime to p.

The proof is structured in two cases: one where p divides a, and one where it does not. When p divides a, the statement holds because both a and ap will be divisible by p, resulting in the same remainder of 0. In the other case, we apply Fermat's theorem directly, leading to the conclusion.

Imagine checking off your list of chores. If the chore (a) is due today (p), both the chore itself and its completion (ap) relate back to today (0 remainder). If you finish ahead of schedule, you still relate back to your original list, satisfying the theorem's claim.

Now, as I said at the beginning of the lecture Fermat's little theorem also forms the basis of very interesting primality testing algorithm.

Fermat's Little Theorem is applied in algorithms to test for prime numbers. By choosing a base a, we can determine if a number n is likely prime based on whether an equation derived from the theorem holds true.

Think of a detective examining a suspect (n). If evidence (a) corroborates that the suspect behaves as a prime character (shows expected traits), we might be led to believe they are innocent (prime). But absence of evidence could very well confirm guilt (composite).

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.

Primality tests based on Fermat's theorem can fail because of special composite numbers known as Carmichael numbers. Despite meeting the conditions of the theorem, these numbers can mislead tests, making them appear prime.

Imagine a well-made disguise that allows someone to trick you into thinking they are royalty (prime). The disguise may look perfect under certain lighting or angles, but upon closer inspection, the truth reveals they are just an actor (composite).

So, what exactly are Carmichael numbers, so, they are composite numbers, which are pseudo primes with respect to every base that you can think of.

Carmichael numbers are composite numbers that satisfy Fermat's Little Theorem for every integer a that is co-prime to the number. They behave like primes in that they confirm the theorem's condition, yet they are not actually prime.

Imagine a magician performing tricks that consistently fool the audience into believing he is a powerful wizard (prime). Despite his powerful appearances and illusions, he is just a skilled performer hiding the truth of his identity (composite).

So my claim is that 561 is a Carmichael number. So, you can see that 561 is not a prime number.

561 is indeed a Carmichael number, confirmed through its ability to meet the congruence relation specified by Fermat's theorem for all bases that are co-prime to it. Testing any such base will yield the result consistent with a prime even though it is not.

Imagine a known actor visiting schools to impart 'wisdom' (Carmichael), earning everyone's trust for their insights, although behind the scenes, they are merely reading from prepared notes without true knowledge (composite).

--