Fermat’s HUGE little theorem, pseudoprimes and Futurama

A LOT of people have heard about Andrew Wiles solving Fermat's last theorem after people trying in vain for over 350 years. Today's video is about Fermat's LITTLE theorem which is at least as pretty as its much more famous bigger brother, which has a super pretty accessible proof and which is of huge practical importance for finding large prime numbers to keep your credit card transactions safe.

Featuring a weird way of identifying primes, the mysterious pseudoprimes and lots of Simpsons, Futurama and Halloween references (I love Halloween and so this is a Mathologer video has a bit of a Halloween theme).

As usual, thank you very much to Marty and Danil for their help with this video.

Enjoy :)

[macronencer]

The necklace proof is really lovely! I like it when proofs step outside of the abstract and use elements of reality to help them.

[schall]

14:59 Challenge accepted, Marty!

From remembering that 1729 is the Ramanujan number, 1729 = 12^3 + 1. So therefore, for 1729 to be a Carmichael number, all prime factors with 1 subtracted can only themselves have prime factors of 2 and 3.

1729 is not even, has a nine-sum of 2, and does not end in 5 or 0; so the lowest prime factor is at least 7. 1729 can be broken into chunks as 1400+280+49, all of which divide by 7. The result of this is 200+40+7 = 247. Remembering the difference between squares rule, this is 9 (3^2) below 256 (16^2), and so has factors of 13 (16-3) and 19 (16+3). So our final factorization of 1729 is 7*13*19.

Subtracting 1 from each prime factor gives 6, 12, 18. Each of these cleanly divides 1728. Therefore 1729 is a Carmichael number. QED

[Sam_on_YouTube]

Isn't 1729 Ramanujen's Taxi Cab Number? The smallest number that is the sum of 2 cubes in 2 different ways? And also the number on the taxi that his friend and mentor took on the way to see the dying Ramanujen.

[brettsmith]

You explain combinatorics better than anyone I’ve tried to learn from.

[ryaneakins]

I think I can solve the mystery of 1729, but I have to do it somewhere else. Can someone please call me a taxicab.

[Dziaji]

(1^2 - 1) % 2 = 0

Ok. I spent enough time proving it for myself. Cool theorem.

[zuthalsoraniz]

8:15
Take an arbitrary neckless containing b beads of c different colours, with b and c both being integers and c≥2. A periodic necklace is one in which the same pattern of beads, with length p≥2, occurs multiple times, and all the beads belong to the same repeating pattern - e.g. red green red green red green blue blue is not periodic, because not all beads belong to the same pattern, but red red green red red green is periodic.

Since there must be at least two instances of the repeating pattern in the necklace, the maximum length p is equal to b/2.

Saying that a necklace of length b is periodic with pattern length p is equivalent to saying that p divides b. But if b is a prime number, the only numbers that divide it are 1 and itself, and since 1<2 and b>b/2, a necklace with a prime number of beads in it cannot be periodic.

[behnamashjari]

Dr. Polster,
You should get the Fields Medal for what you do for math. Your channel is the most fun and learning part of youtube. Keep up the great work!

[peppybocan]

"561- Infinitely annoying" :D

[maitland]

Another super video. I appreciate them so much and always look forward to the next one!

[xnick_uy]

Fantastic video!

SInce you mentioned the connection between large prime numbers and encryption, it would be wonderful if you made a video explaining the key aspects of how that might go.

[enzuber]

Thanks so much for this terrific video - it will make a great addition to our school enrichment resources. Our Year 7 students learn about this theorem and it is challenging at first, so extremely helpful to have your teaching. I love the "why do we care?" discussion 😀.

[KnakuanaRka]

As for the last problem, here’s this:
First, looking at the base, represent it as a sum of a multiple of 13 and the remainder a. Raising this to any power b results in an a^b term and a whole bunch of terms that are powers and multiples of 13, which are equal to 0 mod 13 and thus get thrown out. Therefore, a^b=(a mod c)^b (mod c) for any integers. In our puzzle, we can calculate 666 mod 13 by hand pretty easily; 666=650+16, 16=13+3, so 666=3 mod 13, and 666^666=3^666 mod 13.
Then we can use the second form of the little theorem, saying that a^(p-1)=1 mod p. Since the mod here is 13, that means 3^12=1 mod 13, so we can freely divide it from our big number. This is equivalent to subtracting 12 from the power. 666 mod 12 is easily determined to be 6, so 3^666 mod 13= 3^6 mod 13.
Now, 3^6=9^3=729, and determining the mod 13 of this, 729=650+79, 79=65+13+1, so our final answer is that 666^666 mod 13 is 1.

[Peter_]

This guy is pretty awesome - he has a relaxed style, he is good-looking, and he has a cool accent.

[hpp]

Absolutely fantastic! Thank you very much for the wonderful presentation!

[darcipeeps]

Carmichael Numbers *aggressive finger quotes*

[chonchjohnch]

I derived the little theorem independently in high school, I was so excited until I found out I was a few hundred years late and wrong

[Vojtaniz]

Hello from the Czech Republic :-)
Great pronounciation, you are one of the very few people who don't read our "c" as "k" :-)

[RiccardoBrasca]

It should be pointed out that to generate very big (almost surely) prime numbers, what is used in reality is the Miller-Rabin primality test, that it is an improvement of Fermat's test. The main reason for using it is that it is faster, but another pleasant feature is that there are no Carmichaelish numbers for this test :)

[benjaminbrady]

I know 1729 is the taxi cab number but I can't quite figure out why BP is on the nimbus. I always assumed it was referencing BP oil or something