Welcome to a special Halloween edition
of Mathologer. Recently I did a video on Fermat's mega famous Last Theorem
Fermat's theorem says that the pretty Pythagorean integer identities like 3
squared plus 4 squared equals 5 squared or 5 squared plus 12 squared equals 13
squared don't have nontrivial counterparts if the exponent 2 is
replaced by any integer greater than 2. Today I'd like to tell you about a
second theorem associated with the great Pierre de Fermat. It goes by the name of
Fermat's little theorem and is also about powers of integers. Very important, at
least for people obsessed with movie maths like me and Marty, both of Fermat's
theorems have featured in the Simpsons and Futurama. In 1995, around the
time the proof of Fermat's Last Theorem was announced Homer stumbles across a
pretend counterexample to Fermat's Last Theorem. A really fun maths troll by the
Simpsons writers that had millions of viewers reach for their calculators. Then
in the 2014 Simpsons Futurama crossover episode the equation at the core of a
Fermt's little theorem is discovered by my alter-ego
Professor Frink. There in the upper left corner of the hatch in Bender's head some
of you may not be familiar with the three-stroke equal sign and the mod
thingo in brackets. I'll explain later but luckily 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 pick 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 integer 4. Fermatis little theorem then tells us that 3
divides 4 cubed minus 4. Of course, that's easy to check directly
since 3 divides 64 minus 4 which is equal to 60. But without doing the
arithmetic and just by looking at the expression on
the right it's not at all 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've chosen. And why should we care?
Of course mathematicians care simply because that's the way we're built. And
in a minute I'll show you a really really really beautiful proof of
Fermat's little theorem. But just in case that's not sufficient incentive -- though
it really should be -- I also promise to show you two really cool application of
Fermat's little theorem. Our first application is an unexpected and really
weird way to hunt down prime numbers something which is very important for
things like credit card encryption schemes. Along the way, we'll also
encounter some of my favourite numbers, the mysterious firm our pseudo primes. sA
a second application I'll turn Fermat's little theorem into a tool that you can
use to solve really frightening Helloween problems like this one here, Oh
and we'll also have some more Futurama :) But first the proof. It turns out that to prove Fermat's little theorem all we
have to do is to count some pretty necklaces. What do necklaces have to do
with any of this? Don't worry, of course I'll explain. As regular viewers are
probably now very used to I'll focus on one example which is sufficiently
generic to illustrate the general proof. So let's again choose the integer to be
4 and let's prove that the prime 7 divides 4 to the power of 7 minus 4 in a
way that will also clearly work for any prime and any positive integer. Now what
we're going to do is to count the number of necklaces of length 7 where each of
the 7 beads can be one of 4 colours. Except not all of the beads can be the
same colour. Here's an example ... and here's another one. So it's ok to not use all
the colours. The only thing we avoid is choosing all the beads to be of one
colour so that's not allowed. Ok seven beads, four colours, not all the same,
okay? Also important: we consider rotated versions of a necklace to count as one
and the same necklace. So, all of these guys here they all are same necklace.
However, we consider two necklaces that are mirror images to be different as
long as they cannot be rotated to coincide. Okay we'll 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 7 minus 4 which is what we want to prove!
Sneaky huh? Ok time to begin counting necklaces. To do this we first cut each
necklace and straighten it out like this. Of course there
are other ways to cut the necklace giving rise to different strings. For
example cutting here gives this string here. There are 7 gaps between the beads
and so there are 7 possible strings that we can cut and these seven cuts
correspond to the following 7, and this is really really important,
7 different strings of beads. Now if we had started with all possible necklaces
and imagine cutting each of them in all possible ways then we'd obviously end up
with all possible strings and the total number of strings is very easy to count.
Each string has 7 beads and each bead can have any of 4 colors. So the total
number of different strings is 4 times 4 times 4, 7 times which comes to 4 to
power of 7 strings. Now, remember, we didn't begin with absolutely all
necklaces, we left out the boring one color ones which also means we miss out
on the boring one color strings. How many of those are there. There’s 4 of those, and so our total number of strings is 4 to power 7 minus 4.
Almost there. Now, every necklace under consideration also gives rise to 7
different strings as in our example and that means that the number of necklaces
we began with is the number down there divided by 7. Tada that's it. How sneaky
and how absolutely ingenious was that! Yes but something a little bit weird
here, right? You think you've got it? Yes what's peculiar is that at no point did
I use the fact that 7 is a prime number. Hmm so where can our proof go wrong 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 strings that we get by cutting a necklace are necessarily
different. And obtaining 7 different strings for each necklace was absolutely
critical for our counting argument. For example, if he use 9 beads instead of 7
beads one possible necklace looks like this. In this necklace things repeat
every three beads which means that when we cut this necklace in all possible
ways we only get three different strings rather than nine and this invalidates
the last step in our proof. I'll leave it as a first challenge for you to show in
the comments that this sort of periodic necklace cannot occur if a necklace has
a prime number of beads and at least two colors. Oh and just 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 extra interesting here which means it's time
for another t-shirt... Tada Now as I was saying, 9 not dividing 4 to
the power of 9 minus 4 is also interesting and leads to our first
application of Fermat's little theorem. Fermat's little theorem tells us that if 9
was prime then 9 would divide 4 to power of
9 minus 4. But we know that actually 9 does not divide 4 to the
power of 9 minus 4 so nine cannot be a prime. I know
Wow, incredible, stop the presses, right :) However what this suggests is that we
can investigate whether or not some mystery number m is prime by swapping
m for 9 and checking for divisibility. And if the difference on the right is not
divisible by m then m is definitely not prime. On the other hand, what if the
difference on the right is divisible by m? Does this guarantee that m is prime?
Hmm, sadly the answer is `No'. For example, if we test m equals 4, then the
difference is definitely divisible by 4 since both terms on the right are
divisible by 4. But of course 4 is very much not prime. Bummer. Still 4 is a
pretty special number for this setup so maybe this is all worth a little more
exploration. So let's do an experiment and let Mathematica check divisibility
for the first 1,000 integers. Let's see how many non-primes and maybe primes
get discovered this way. However before firing up the machine I'll make
an adjustment. Those powers here will get very big very fast there's also nothing
special about using 4 in Fermat's little theorem and we could use any integer
greater than 1. So let's start at the start and keep those powers as small as
possible by replacing 4 with 2. Now we let Mathematica do its thing that's
the output of my program and as you can see at the beginning it's spot-on.
All the non primes 4, 6, 8, etc. fail our divisibility test and so Fermat's little
theorem proves they are non-primes. In fact, it's only when we get to 341
that we have a non-prime that our test thinks may be prime and there's only three such numbers
under 1000. But we don't have to put up with nonsense from those three
troublemakers. 2 was just one possible choice for our integer. So let's throw
3 at them. And that works. Using 3 identifies 341 and 645 as non-prime numbers. One annoying number to go. So we can throw 4 at 561
and if that doesn't work then 5 and then 6 and 7, and so on. Something
is going to work, right? Wrong!! It turns out that 561 is infinitely annoying. None
of our Fermat's little theorem tests 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, named after the American mathematician
Robert Daniel Carmichael. Actually they were missnamed since Carmichael was
neither the first to discover these numbers nor the first to seriously
investigate them. So maybe we should call them pseudo Carmichael numbers:) It
appears that the real discoverer of these numbers was a Czech mathematician
but Václav Šimerka. Anyway Carmichael numbers are very rare. Among the first
billion positive integers there are over 50 million primes but only 646
Carmichael numbers. Still it was proved in 1994 that overall they're infinitely
many Carmichael numbers, really tricky stuff. Actually knowing about these
numbers and the fact that they are relatively rare is also of practical
importance. Being able to easily generate very large primes primes that have a
thousand plus binary digits is of key importance for all sorts of encryption
algorithms such as the algorithms that keep your credit card transactions safe.
Well, keeps them safe until some company stuffs things up, right:) And
despite the crazy powers that appear in Fermat's little theorem and despite the
existence of those infinitely annoying pseudoprimes,
primarily tests based on Fermat's little theorem turn out to be more useful than
pretty much anything else, making Fermat's little theorem of huge practical
importance. Now before moving on to our second Fermat's little theorem
application, let me just mention a characterization of these mysterious
pseudoprimes. This really beautiful characterization was discovered (well
before Carmichael of course :) by the German mathematician Alvin Reinhold
Korselt. At first glance proving that a number like 561 is a pseudoprime looks
insanely difficult because it involves showing that 561 divides
the difference on the right for all infinitely many choices of the integer a.
However Korselt proved that if you know the prime factorization of a number then
you can pretty much tell at a glance whether the number is a Carmichael
number. Just subtract 1 from every one of the numbers in sight okay 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.
So number is a Carmichael number if none of its prime factors repeat and if all
its prime factors minus one divided the number minus one. Pretty amazing
characterization isn't it? I love it. Okay an arithmetic challenge for you: use
Korselt's characterization to prove that 1729 is a Carmichael number (Marty: no
calculators!) Marty's got something with calculators :) And now a quick pop culture
maths puzzle: why do you think the Futurama writers kept sneaking the
number 1729 into the program? Is it because it is a pseudoprime? And while
we're here why are my initials BP on the Futurama spaceship Nimbus? Hmm. Now for our second Fermat's little theorem application and time for yet another
t-shirt ... Tada Okay, finally, to get into the Halloween
spirit let me show you how he can figure out by
hand what the remainder is when you divide the seriously monstrous number 11
to the power of 666 by the unlucky prime 13. For this we need to recast Fermat's
little theorem into the form that appears in Bender's head. What do we do?
Well we first take the common factor a out of the difference, like that. This
shows that if the prime o does not divide the first factor, our integer a,
then it must divide the second factor, right? Pretty obvious.
Okay now to our unlucky prime 13 and the base 11 of our monster integer. Of course
13 does not divide 11 and so Fermat's little theorem promises us 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 maths lingo
we write that succinctly like this. Okay and what we are interested in is the
value of the pumpkin in this equation. We can sneak up on the pumpkin by starting
with our tiny 11 to the power of 12. Now comes the trick. Since 11 to the power of
12 has remainder 1 when divided by 13, so does any power of 11 to the power of 12.
We leave that for you as an easy challenge. On the left, we can pull the n
into the brackets and we've almost revealed our pumpkin. 12 times 55 is 660,
so if we choose n equal to 55, then we get this. Okay almost there. The power is still 6 short of our 666 but you can check by hand
that 11 to the power of 6 has remainer 12 on division by unlucky 13. Finally, we
multiply the left sides together and the right sides together 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 should warn you that if you don't succeed in submitting
the correct answer in the comments by midnight on Halloween Jason will pay you
a visit. And don't try to be smart, only one answer, otherwise I tell Jason. And
don't use a calculator, otherwise I'll tell Matty. And that's it for today.
Happy Halloween!
