Fermat’s HUGE little theorem, pseudoprimes and Futurama

Welcome to a special Halloween edition of Mathologer. I recently made a video about Fermat's mega famous Last Theorem. Fermat's

theorem

says that nice Pythagorean integer identities like 3 squared plus 4 squared equals 5 squared or 5 squared plus 12 squared equals 13 squared have no non-trivial counterparts if the exponent is replaced 2 times any integer greater than 2. Today I would like to talk to you about a second

theorem

associated with the great Pierre de Fermat. It is named after Fermat's

little

theorem and also deals with powers of integers. Very important, at least for people obsessed with cinematic mathematics like Marty and I, both of Fermat's theorems have appeared in The Simpsons and Futurama.

In 1995, when the proof of Fermat's last theorem was announced, Homer stumbles upon a supposed counterexample to Fermat's last theorem. A really funny math troll from the writers of The Simpsons that made millions of viewers grab their calculators. Then, in the 2014 Simpsons Futurama crossover episode, my alter ego Professor Frink discovers the equation at the core of Fermt's

little

theorem. There, in the upper left corner of the hatch on Bender's head, some of you may not be familiar with the three-stroke equal sign and the mod in parentheses. I'll explain it later, but fortunately we can also express Fermat's little theorem in simpler terms like this.

Here the vertical green line means "divides into" or "is a factor of". So what this says is that if you choose any prime number and any positive integer a, then the prime must divide the difference on the right. For a really simple example, let's choose our prime to be 3 and the integer to be 4. Fermatis' little theorem then tells us that 3 divides 4 cubed minus 4. Of course, that's easy to verify directly since 3 divides 64 minus 4. , which is equal to 60. But without doing the arithmetic and simply looking at the expression on the right it's not entirely obvious why this should be true, right?

How can we be sure that Fermat's little theorem is always true, no matter what monster-sized prime and integer we have chosen? And why should we care? Of course mathematicians care simply because that's how we are built. And in a minute I'll show you a really beautiful proof of Fermat's little theorem. But in case that's not enough incentive (although it really should be), I also promise to show you two really cool applications of Fermat's little theorem. Our first application is an unexpected and really strange way to look for prime numbers, something that is very important for things like credit card encryption schemes.

Along the way, we'll also find some of my favorite numbers, the mysterious signature of our pseudo-cousins. In a second application, I'll turn Fermat's Little Theorem into a tool you can use to solve really scary Helloween problems like this one. Oh, and we'll have more Futurama too :) But first the test. It turns out that to prove Fermat's little theorem all we have to do is count some pretty necklaces. What do necklaces have to do with all this? Don't worry, of course I'll explain it to you. Since regular viewers are probably very used to it by now, I'll focus on an example that is generic enough to illustrate the general test.

So let's again choose the integer to be 4 and show that prime 7 divides 4 to the power of 7 minus 4 in a way that will also clearly work for any prime number and positive integer. Now what we are going to do is count the number of necklaces of length 7 where each of the 7 beads can be one of 4 colors. Except not all beads can be the same color. Here you have an example... and here another. So it's okay not to use all the colors. The only thing we avoid is choosing all the beads to be the same color, so that is not allowed.

Ok, seven beads, four colors, not all the same, okay? Also important: we consider rotated versions of a necklace to count as the same necklace. So all these guys here have the same necklace. However, we consider two necklaces that are mirror images to be different as long as they cannot be rotated to match. Well, we will show that the total number of such necklaces is 4 to the power of 7 minus 4 divided by 7. Now, of course, the number of different necklaces must be an integer, right? But for that to be the case, 7 must divide 4 to the power of 7 minus 4, which is what we want to prove!

Clever huh? Ok, time to start counting necklaces. To do this, we first cut each necklace and straighten it like this. Of course there are other ways to cut the necklace giving rise to different threads. For example, cutting here results in this string here. There are 7 spaces between the beads and so there are 7 possible strands that we can cut and these seven cuts correspond to the next 7, and this is actually very important, 7 different strands of beads. Now, if we had started with all the possible necklaces and imagined cutting each of them in all possible ways, we would obviously end up with all the possible threads and the total number of threads is very easy to count.

Each strand has 7 beads and each bead can be any of 4 colors. So the total number of different strings is 4 times 4 times 4, times 7, resulting in 4 to the power of 7 strings. Now, remember, we don't start with absolutely every necklace, we skip the boring one-color ones, which also means we miss out on the boring one-color threads. How many of those are there? There are 4 of those, so our total number of strings is 4 to the power of 7 minus 4. We're almost there. Now, each necklace under consideration also gives rise to 7 different chains like in our example and that means that the number of necklaces we start with is the number down there divided by 7.

Tada, that's it. How clever and how absolutely ingenious that was! Yes, but something a little strange here, right? Do you think you have it? Yes, the peculiar thing is that at no point did I use the fact that 7 is a prime number. Hmmm, so where can our test fail if we don't use a prime number? Well, the problem is that if we replace our prime number 7 with a composite number, then not all the threads we get when cutting a necklace are necessarily different. And getting 7 different threads for each necklace was absolutely critical to our counting argument.

For example, if you use 9 beads instead of 7, a potential necklace will look like this. In this necklace things repeat every three beads, which means that when we cut this necklace every possible way we only get three different strands instead of nine and this invalidates the last step of our test. I will leave you as a first challenge to show in the comments that this type of periodic necklace cannot occur if a necklace has a prime number of beads and at least two colors. Oh, and in case you're wondering, 9 doesn't divide 4 to the power of 9 minus 4. But wait a minute, we're actually onto something very interesting, which means it's time for another t-shirt...

Tada Now As I said, 9 without dividing 4 to the power of 9 minus 4 is also interesting and leads us to our first application of Fermat's little theorem. Fermat's little theorem tells us that if 9 were prime, then 9 would divide 4 to the power of 9 minus 4. But we know that 9 does not actually divide 4 to the power of 9 minus 4, so nine cannot be prime. I know Wow, awesome, stop pressing right :) However, what this suggests is that we can investigate whether some mysterious number m is prime or not by exchanging m for 9 and checking the divisibility. And if the difference on the right is not divisible by m then m is definitely not prime.

On the other hand, what happens if the difference on the right is divisible by m? Does this guarantee that m is prime? Hmm, unfortunately the answer is "No." For example, if we prove that m is equal to 4, then the difference is definitely divisible by 4 since both terms on the right are divisible by 4. But of course, 4 is not prime. Journal. Still, 4 is a pretty special number for this setup, so maybe it's worth exploring all of this a little more. So, let's do an experiment and let Mathematica check the divisibility of the first 1000 integers. Let's see how many non-cousins ​​and perhaps cousins ​​are discovered this way.

However, before turning on the machine I will make an adjustment. Those powers here are going to get very big very quickly. There is also nothing special about using 4 in Fermat's little theorem and we could use any integer greater than 1. So let's start from the beginning and keep those powers as small as possible by replacing 4 with 2. Now we let Mathematica do its thing, which is the result of my program and as you can see at the beginning, it is perfect. All non-primes 4, 6, 8, etc. they do not pass our divisibility test and therefore Fermat's little theorem shows that they are non-prime.

In fact, only when we get to 341 do we have a non-prime that our test thinks may be prime and there are only three such numbers below 1000. But we don't have to put up with any nonsense from those three troublemakers. 2 was just one possible choice for our whole number. So let's launch 3. And that works. Using 3 identifies 341 and 645 as non-prime numbers. An annoying number is missing. Then we can throw 4 to 561 and if that doesn't work, then 5 and then 6 and 7, and so on. Something's going to work, right? Mistaken!! It turns out that 561 is infinitely annoying. None of our little proofs of Fermat's theorem will show that 561 is composite.

Numbers like 561, which Fermat's little theorem cannot distinguish from primes, are called Fermat

pseudoprimes

or Carmichael numbers, after the American mathematician Robert Daniel Carmichael. In reality, they were misnamed since Carmichael was not the first to discover these numbers nor the first to seriously investigate them. So maybe we should call them pseudo Carmichael numbers :) It seems that the real discoverer of these numbers was a Czech mathematician, Václav Šimerka. Anyway, Carmichael's numbers are very strange. Among the first billion positive integers there are more than 50 million prime numbers, but only 646 Carmichael numbers. Even so, in 1994 it was shown that, in general, there are infinitely many Carmichael numbers, something really complicated.

Really knowing these numbers and the fact that they are relatively rare is also of practical importance. Being able to easily generate very large prime numbers that are longer than a thousand binary digits is vitally important for all types of encryption algorithms, such as the algorithms that keep credit card transactions secure. Well, it keeps them safe until some company screws it up, right? :) And despite the crazy powers that appear in Fermat's little theorem and despite the existence of those infinitely annoying pseudo-primes, mainly proofs based on Fermat's little theorem turn out to be more useful than practically anything else, which makes Fermat's little theorem of enormous practical importance.

Now, before moving on to our second application of Fermat's little theorem, let me mention a characterization of these mysterious

pseudoprimes

. This really beautiful characterization was discovered (long before Carmichael, of course :) by the German mathematician Alvin Reinhold Korselt. At first glance, proving that a number like 561 is a pseudoprime seems tremendously difficult because it involves proving that 561 divides the difference on the right for all infinitely many options of the integer a. However, Korselt showed that if you know the prime factorization of a number, you can tell at a glance whether the number is a Carmichael number. Simply subtract 1 from each of the numbers in view, then our number is a Carmichael number if and only if all the numbers on the left are different and if they all divide the number on the right.

Then a number is a Carmichael number if none of its prime factors repeat and if all but one of its prime factors divide the number minus one. Pretty surprising characterization, right? I love it. Well, an arithmetic challenge for you: use Korselt's characterization to show that 1729 is a Carmichael number (Marty: no calculators!) Marty has a thing for calculators :) And now a quick pop culture math riddle: Why do you think the Futurama writers kept sneaking around? Number 1729 in the program? Is it because it is a pseudoprime? And while we're here, why are my initials BP on the Nimbus spaceship from Futurama?

Hmm. Now, our second application of Fermat's little theorem and it's time for yet another t-shirt... Tada Well, finally, to get into the Halloween spirit, let me show you how you can figure out by hand what the remainder is when you divide seriously monstrous number 11 raised to 666 by the unfortunate 13th cousin. To do this we need to reformulate Fermat's little theorem in the form that appears in Bender's head. what do we do? Well, first we take out the common factor a from the difference, like this. This shows that if prime o does not divide the first factor, our integer a, then it must divide the second factor, right?

Pretty obvious. Okay, now toour unlucky main number 13 and the base 11 of our monstrous integer. Of course, 13 doesn't divide 11, so Fermat's little theorem promises that 13 divides 11 to the power of 12 minus 1. In other words, when you divide 11 to the power of 12 by 13 you get a remainder of... what Well. ? 1 of course. In mathematical jargon we write it succinctly like this. Well, what interests us is the value of the pumpkin in this equation. We can sneak up on the pumpkin by starting with our little 11 to the power of 12. Now comes the trick. Since 11 to the power of 12 has a remainder of 1 when divided by 13, so does any power of 11 to the power of 12.

We leave it to you as an easy challenge. On the left, we can put the n in parentheses and we've almost revealed our pumpkin. 12 times 55 is 660, so if we choose n equals 55, we get this. Well, we're almost there. The power is still 6 away from our 666, but you can verify by hand that 11 to the power of 6 has the remainder 12 in division by the unlucky 13. Finally, we multiply the left and right sides to arrive at our final answer. , a remainder of 1 times 12 which is equal to 12. Can you justify the last step of this calculation? Okay, last challenge for you: what is the remainder of the super unlucky evil 666 to the power of 666 when you divide it by 13?

I must warn you that if you don't manage to submit the correct answer in the comments before midnight On Halloween Jason will pay you a visit. And don't try to be clever, just an answer, otherwise I'll tell Jason. And don't use a calculator, otherwise I'll tell Matty. And that's all for today. Happy Halloween!