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!