Fermat’s HUGE little theorem, pseudoprimes and Futurama

[@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.

[@Mathologer]

You are the first to comment on the proof ! Definitely one from the BOOK :)

[@thaddeusazariah5568]

Instablaster...

[@mikesteele5935]

Yea but ... the proof by induction is just one line ! And to confirm the fact that a cycle gives exactly p distinct linear orders? I had to use the Stabilizer theorem for group actions to see this ... though there is a barehands way, I suppose.

[@alomgazi3755]

the a

[@JamesWylde]

@@Mathologer TV fadf we we 00 r red we wer deer 4 red

[@schall3603]

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

[@NoNameAtAll2]

Nine sum of 1729 is 1, not 2

[@rogerlie4176]

The simplest way to factorise 1729: 1729 = (10^3 + 9^3)=(10 + 9)(10^2 - 10 * 9 + 9^2) = 19 * 91 = 19 * 7 * 13.

[@sk8rdman]

I did it a bit differently (but still no calculator) and can confirm this answer.

[@AntonBourbon]

> *From remembering that 1729 is the Ramanujan number, 1729 = 12^3 + 1* If you know *that* much about the number (that it is a sum of cubes), why do you miss the fact you already have the 1st divisor in your hands? 1729 = 12³+1³ = (12+1)(12² - 12*1 + 1²) = 13*(144-12+1) = 13*133 = 13*(140-7) = 13*(20*7-7) = 13*7*(20-1) = 7*13*19

[@PC_Simo]

@@sk8rdman Same here; and you can check that, from my comment from a year ago (shows up pretty high up, in the comment section, for me, at least).

[@laurabradby]

11:04 Why is 9 highlighted?

[@Mathologer]

Yes, one more typo for the Mathologer typo collection :)

[@litigioussociety4249]

Because 9 is prime obviously.

[@bbwarwick]

I was totally lost this entire video, but I honor myself in noticing 9 was incorrectly highlighted in a list of prime numbers. 💪 🧠

[@DlcEnergy]

@Litigious Society 9/1 = 9 9/3 = 3 9/9 = 1

[@twistedsim]

@@DlcEnergy I think you missed the joke in your proof

[@brettsmith3467]

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

[@zuthalsoraniz6764]

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 1b/2, a necklace with a prime number of beads in it cannot be periodic.

[@ryanoftinellb]

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

[@esul4]

Haha, good one!

[@timbeaton5045]

But let's hope you live to be older than 32.

[@Mathologer]

:)

[@15schaa]

That runs on BP fuel.

[@Mathologer]

@@15schaa :)

[@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

[@chandrikasaha6301]

Still you remain the inventor. Just you don't happen to be the first one. I couldn't find it myself. Still happy to find that such a wonderful thing exists

[@xyz.ijk.]

​@@chandrikasaha6301That was a kind and elegant way to identify the independent creative process.

[@Peter_1986]

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

[@behnamashjari3003]

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!

[@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.

[@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.

[@Mathologer]

Very good :)

[@matrixarsmusicworkshop561]

Lol I though of the same thing, but I was like its somewhat but not very likely that that whole think is the ramanujan thing

[@Dziaji]

(1^2 - 1) % 2 = 0 Ok. I spent enough time proving it for myself. Cool theorem.

[@Mathologer]

:)

[@fierymathematics4767]

Nice joke lol

[@maitland1007]

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

[@peppybocan]

"561- Infinitely annoying" :D

[@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 :)

[@leocherry]

I like you. You put an effort in pronouncing names of people of different languages correctly. My respects

[@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.

[@Mathologer]

Sort of on the list :)

[@Mathologer]

Sunday 1 am here in Australia :)

[@the6p4c]

Silly daylight saving time... 😂

[@oliverhees4076]

saturday 10 am in boston

[@dhruvakashyap]

Isn't 1729 also ramnujams cab number?

[@AB-Prince]

hello from the boring isle of england

[@Mathologer]

@@dhruvakashyap You are on to something there :)

[@Vojtaniz01]

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

[@grantorino2325]

As my Czech friend once told me, "think of Czech 🇨🇿 as Polish 🇵🇱, but with all of the weird and confusing *double-consonants* left out!"

[@jamieee472]

I love it whenever you make the pictures of mathematicians smile A really nice touch

[@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 😀.

[@Mathologer]

Glad this works for your kids :)

[@andreaaristokrates9516]

"Don't use a calculator" Too late, I already punched the numbers into the python shell. All hail the pow-function!

[@Mathologer]

Marty won't be pleased :)

[@duality4y]

Did you know python has a power operator why use a function when it is built in :)

[@alinayossimouse]

Same thing, but I used the ** notation. Are you using a NumWorks?

[@andreaaristokrates9516]

@@alinayossimouse I literally opened an empty .py, hit F5, had the shell open and ran pow(11,666,13). The function should (I haven't checked) be much faster, because it's only calculating small products and immediately reduces them again. We had to code that function in school, fun times and it's nice to see it wasn't a waste of time learning about that stuff.

[@alinayossimouse]

@@andreaaristokrates9516 I see, good to know. I wasn't concerned about the speed of the operation but mainly about quick entry into my calculator's python shell via the keypad

[@hpp6116]

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

[@mjah]

That HUGE little smile. 0:38

[@Mathologer]

I wonder how many people will notice :)

[@shivanshjaiswal2626]

@@Mathologer I noticed that too.

[@hamiltonianpathondodecahed5236]

that wasn't there until you said it

[@HomeofLawboy]

Fermat suddenly smiling made me shiver so hard wth

[@Mathologer]

Well, good, because this is supposed to be a spooky video :)

[@moskthinks9801]

There is also Euler's theorem! Helps with composite numbers :) a^(phi(n)) = 1 (mod n) Where phi(n) is Euler's totient function.

[@vivekpanchagnula815]

remember that this only applies if a and n are coprime!

[@usernamenotfound80]

Go to 9:34 to witness Burkard's amazing ventriloquism skills.

[@Mathologer]

There is actually one more instance of this in the video. Can you spot that one too ? :) Not that it matters but I actually practised ventriloquism for a couple of years when I was a teenager

[@thingathinga7898]

@@Mathologer I caught a very small one at 17:20. Does that count?

[@Mathologer]

@@thingathinga7898 Yes, that one counts :)

[@IMIGamerz2105]

I kinda lipread what you really said during those ' ventriloquistic' moments 9:34 But what if m is divisible by m? 17:20 eleven times fifty five is... Am I right, Mathologer?

[@Rubrickety]

If m is divisible by m, then m is definitely not not m.

[@AndrewLoblaw]

At 10:43 your table shows 9 as potentially prime. But with 2 as the constant this should be "not divisible -> not prime"

[@darcipeeps22]

Carmichael Numbers *aggressive finger quotes*

[@bimbumbamdolievori]

I'm crying by your explanation it's so so genuinely good and I want the 561 tshirt

[@benjaminbrady2385]

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

[@saxbend]

10:59 it appears 9 also passes the test according to what's on the screen, although of course it really doesn't.

[@Mathologer]

Yes, this video is haunted and of course we all know that 9 is a very unlucky number in Japan with the same pronunciation as torture :) Seriously, though, just a typo.

[@shambosaha9727]

Did no one else notice that Benda's head also contains the Riemann Hypothesis, the Prime Number Theorem, and the sentence 'You are too wise to be forgot.' ?

[@pyotrleflegin7255]

A really amazing explanation - thank you so much for this amusing and informative video.

[@Pika250]

I had a feeling group theory was involved here. 11 is a cyclic generator modulo 13, hence the -1 (here 12) as the remainder of 11^6, and hence 11^666, on division by 13. 3, the reduction of 666 mod 13 (where 663 = 13 * 51), is not a cyclic generator mod 13 (where in fact 3 = 11^4), and hence 3^6 (and thus 666^666) would reduce to 1 mod 13. When we are given an integer T > S, where we are working modulo S, we replace T by (T mod S) the remainder of T upon division by S, call it N. We have effectively moved T beads along our necklace of S beads by instead moving N beads, where N < S.

[@haniyasu8236]

Fun little fact: this theorem is the more or less basis for the Miller-Rabin Primality test, which, in most programming languages, is the primality test of choice since it can check 64-bit integers *extremely* fast. Furthermore, it is conjectured that the test runs in polynomial time (over the number of digits), but it requires the Generalized Riemann Hypothesis in order to prove.

[@zar6]

The digits on the credit card at 3:17 are the digits of e, but the last digit is wrong for some reason. Was that on purpose?

[@nicksamek12]

On a credit card, the last digit is a checksum. Add up all the digits on the credit card ;) Edit; I've just done this. The last digit should be a 5. So now I have no clue.

[@martinepstein9826]

Whoops, let's not forget the first challenge problem: if a necklace has a prime number of beads and more than two colors then the p different rotations of the necklace are all different. For a contradiction, let's assume that for some number m strictly between 0 and p we can shift the beads by m places and get the same arrangement we started with. Let's label the positions 0, 1, 2, 3, ..., p-2, p-1 and let's refer to the bead now at position 0 as B. When we rotate the necklace and shift every bead over m places we add m to all the position numbers, so B ends up at position m. And since we are assuming the necklace is symmetric with respect to this rotation the bead that started at position m must be the same color as B (otherwise the rotated necklace would look different). Also note that we should view the position numbers as elements of arithmetic mod p so that they wrap back around after a full rotation. Anyway, if we rotate by 2m then B ends up in position 2m, so the bead that started at 2m must also be the same color. In fact by this argument any bead separated from B by a multiple of m must be the same color, so if not all beads are the same color then there must be some position number n that B never ends up in. This is the same as saying m*x = n mod p has no solution. However, we can prove there is a solution using the fact that the greatest common divisor of two numbers is equal to a linear combination. Since p is prime and 0

[@sivalley]

Your Prime Suspects shirt is making me scream internally. :D

[@Mathologer]

I've actually got two different ones. In many ways I like this other one better tinyurl.com/y7aqeb5z but did not use it because the white does not work so well with my white background in the videos :)

[@Carvin0]

About those Carmichael numbers at 11:20. Notice that 3 ^ 561 - 3 = 0 (mod 561), but 3 ^ 560 -1 = 374 (mod 561). Which shows if you used the second form you could've eliminated 561 just as easily as the other two. So it depends on how you express Fermat's Little Theorem. If you express it as a ^ (n -1) = 1 mod n then for n = 561 there are 240 integers, a, between 2 and 560 (inclusive) for which n doesn't satisfy FLT. This implies that the definition of "pseudoprime" needs specification (which a's, or lists of a's, and how is FLT expressed.) Just for fun, consider the next true prime after 561 which is 563. 3 ^ 563 - 3 = 0 (mod 563), and 3^562 -1 = 0 (mod 563).

[@R_C420]

NICE video with the illustration and the likes and the commentsenGLAVIN!

[@Gafa996Gaddisa]

My major will be maths if have a chance to to have teachers like you. Best explainer. Thank you. I am just subscriber not student.

[@phatrickmoore]

Carmichael characterization works for the prime case as well. Passing Fermat’s little theorem doesn’t always imply prime, but does always imply Carmichaelness.

[@nafrost2787]

18:08 The pumpkin is equal to 1. 13 is a prime and 666 doesn't divide 13 so fermat's little theorem hold so 666^12 = 1(mod 13). We use the same modification that Burkard used to get that (666^12)^n = 1(mod 13) for every integer n. Plugging to this n = 55 we get (666^12)^55 = 1(mod13), 666^(12 * 55) = 1(mod 13) , 666^660 = 1(mod 13). So now we need to calculate (666^6)(mod 13), and we can simplify this problem. Another identity in modular arithmetic, is that (a^b)(mod n) = ((a(mod n))^b)(mod n) (I think a, b and n need to be integers for this to work, but I'm not sure and anyway in our example the number we plug for each of those parameters is an integer). Plugging to this equation a = 666, b = 6 and n = 13, we get (666^6)(mod 13) = ((666(mod 13))^6)(mod 13) = (3^6)(mod 13). This is a reasonable calculation to do by hand, but for those who are lazy, there is a way to simplify this calculation as well. First we rewrite (3^6)(mod 13) as (3^(3*2))(mod 13), now we just need one more identity (we already used it earlier but it can't hurt to mention it again): ((a^b)^c)(mod n) = (a^(bc))(mod n) (again I think a, b, c and n need to be integers for this identity to be true, but I'm not sure and we are going to plug to them integers anyway). Now using this identity we have (3^(3*2))(mod 13) = ((3^3)^2)(mod 13) = (27^2)(mod 13) and now with the other identity this equals ((27(mod 13))^2)(mod 13) = (1^2)(mod 13) = 1(mod 13). After all of this we can now calculate (666^666)(mod 13): (666^666)(mod 13) = (666^(660 + 6))(mod 13) = (666^660)(mod 13) * (666^6)(mod 13) = (1 * 1)(mod 13) = 1(mod 13). So (666^666)(mod 13) = 1(mod 13). Q.E.D.

[@NoNTr1v1aL]

Like for Quadratic Reciprocity!

[@Mathologer]

Soon :)

[@Mathologer]

@@det1729 There will always be some people who know some of the stuff I talk about. In any case, even if somebody is familiar with, for example, the necklace proof for Fermat's little theorem I cannot imagine a person like that not enjoying the animation :)

[@tracyh5751]

@@Mathologer I've seen the necklace proof(in the context of group theory), and I loved the animation. I also quite liked how you snuck the division bar into the modular p equivalence symbol. :)

[@Tehom1]

@@Mathologer Absolutely. I have used Fermat's little theorem and enjoyed the necklace animation.

[@lorisdeplano5863]

And cubic reciprocity!

[@timgillam7964]

666 leaves remainder 3 when divided by 13 (13*51 = 663). 3 (mod 13) * 3 (mod 13) ≡ 9 (mod 13) 9 (mod 13) * 3 (mod 13) ≡ 27 (mod 13) ≡ 1 (mod 13) 1 (mod 13) * 3 (mod 13) ≡ 3 (mod 13) And the pattern repeats every three, 3, 9, 1, 3, 9, 1... When the exponent is a multiple of 3, the remainder when divided by 13 is 1. Since 666 is a multiple of 3, the remainder when divided by 13 is 1.

[@mahithgottipati6412]

I just used Fermat's Little Theorem (or Euler's Totient Function). From Fermat's, 11 ^ 12 ≡ 1 (mod 13). 666 ≡ 6 mod 12 (12*55=660). Now the question is 11 ^ 6 ≡ x (mod 13). 11 ≡ -2 mod 13, so (-2) ^ 6 ≡ x (mod 13). (-2) ^ 6 = 64. 64 ≡ -1 mod 13. *The remainder when 11 ^ 666 is divided by 13 is 12, not 1.* Another way you could have done it was: It is the same until 11 ^ 6 ≡ x (mod 13). Since 11 ^ 12 ≡ 1 (mod 13), and 11 ^ 6 ≡ x (mod 13), x ^ 2 ≡ 1 mod 13. From this, x ≡ -1 or 1 (mod 13). Again using the fact that 11 ≡ -2 (mod 13), (-2) ^ 6 ≡ -1 or 1 (mod 13). (-2) ^ 6 = 64. 64 ≡ -1 (mod 13). So, x ≡ -1 (mod 13). Again, the remainder when 11 ^ 666 is divided by 13 is -1 or 12, not 1.

[@gamer9smith]

That 3rd shirt is absolutely brilliant

[@davidhall7275]

I missed something. At 4:44 you said that rotating the string is not creating a new string. "Rotated versions of the necklace count as one and the same necklace." Yet when you cut the string at different places you consider each cut string unique. If you cut the string at 11:00 you have one string. When you rotate the necklace and cut again at 11:00 it is the very same necklace cut at the very same place but considered a new string at 18:39. Are you differentiating between necklaces and strings? I'm confused. Sorry, I don't wear jewelry.

[@shacharh5470]

I learned to prove Fermat's little theorem in a group theory course. It's a corollary of Lagrange theorem when applied to the multiplicative modular group. I don't know if your proof is equivalent or not. I also learned about its application to primality testing in another course I took in year 1, introduction to computer science

[@xhoidlostblade3856]

This is beautiful. And it helped me to understand how does the quantum factorization algorithm works (now I get why it's using phase estimation)! Thank you very much!!

[@xCorvus7x]

A periodic repetition on a necklace means to go exactly once around the necklace by taking whole steps of the length of the periodic pattern. A periodic pattern has a length greater than 1 and is always made up from whole beads, so the length n is a natural number. By going exaxtly once around the necklace with steps of length n, you have counted up to the total number of beads on the necklace, which means that this total number is divisible by n, since this total number is equal to the number of steps times n. This is only possible, if the total number of beads is composite, i. e. it is the product of two or more natural numbers which are greater than 1.

[@soberhippie]

9:33 Do you do all your narration in postproduction?

[@jasonwoolf]

I am curious to know whether you are acquainted with David S. (X.) Cohen who left his pursuit of a PhD in Math at U.C. Berkeley to become a writer for the Simpsons and went on to executive produce Futurama. I assume he is a big reason why so much math appears in these shows (and perhaps he put your initials on the Nimbus as an easter egg just for you).

[@AlessandroDruetto]

Also, in Bender's head, "TSP \in P" made me feel very nervous about the future (I'm an Operations Research specialist)... Even more now, since recently many "P = NP" hoax proofs were submitted to various journals, and one even managed to reach the actual publication; only to be removed the day after, due to an error in that journal's automatic publication procedure!

[@podemosurss8316]

8:24 It's a bit obvious, since the number is prime, it has no factoring numbers other than 1 and himself, and there is no expresion than could give back this number other than N·(string of 1s). In the case you took, the 9 being a square number it has factoring number 3, and it can be expresed as 3·3, that its: they are 3 equal strings.

[@Fireking300]

That 1 dislike is from Jason because no one wants to hang out with him on Halloween.

[@ericbilodeau8526]

Pretty cool proof. So obvious as soon as he began. But cool to view it in that way

[@FibonacciPrower]

First, notice that, since 663=51×13, then 666≡3 (mod 13), so we only need to calculate the remainder of 3^666 modulo 13. Now, since 3 and 13 are coprime, by little Fermat, 3^666≡3^6 (mod 13)≡729 (mod 13). But 728=13×56, so the value of the pumpkin emoji is 1.

[@3geek14]

666 = 13 * 51 + 3, so we can replace 666 in the base with 3 to work with smaller numbers. 666 = 12 * 55 + 6, so we can replace 666 with 6 in the exponent (as was done in the video). 3^6 = 27^2, and 27 = 13 * 2 + 1, so we can replace 27 in the base with 1. The final answer is thus 1^2=1.

[@vishnurahul3378]

What a beautiful proof.Thanks for the content

[@isbeb507]

could you do an episode on the haruhi problem

[@Mathologer]

It's sort of on my list of things to do. Numberphile did a video earlier on this year under the title Superpermutations. I have not watched it yet and so I don't know how far they got in terms of actually describing the algorithms :)

[@knooters]

Not sure if students learn about mod in other countries at a young age, but I never even learned about it at University level here in Norway. Hence I always work around it, but with a similar line of thought. Remainder of (666^666)/13 can be done by using just very basic knowledge: 666=663+3=51*13+3 (52*13-10 would also work, but it makes the calculation easier to make the "remainder" as small as possible) So the number we want to divide by 13 can be written as (51*13+3)^666, which is 3^666+13*k, with k being some ridiculously large integer. This follows because it is only the first term in the expansion that has no factor of 51*13. Hence, the remainder of 3^666 divided by 13 is the same as the remainder of 666^666 divided by 13. Now we use that 666=3*222, and that 3^3=27=2*13+1: 3^666=(3^3)^222=(13*2+1)^222 By the same concept, we just get rid of everything except the term with no factor of 13*2, which is 1^222=1 - which has to be the remainder.

[@MrRyanroberson1]

Oh wow I came across Fermat's little theorem and proved a sub-case. For any n coprime to b, n divides b^(n-1)-1, and shows that 1/n is representable in a finite periodicity. It seems b^n -b is more reliable but still doesn't include values like b^2, though b would never be a square root of a prime, I ignored that fix because I wanted all integers

[@MrRyanroberson1]

When you brought up 9 it reminded me that the limitation of this generalization is that it works ofr any n not a multiple of a square

[@rapidkai51423]

If an orchestra is playing a 7 note scale, and half the band is playing *x* notes for each scale degree and the other is playing *y* notes for each scale degree, and both groups are playing with the same tempo, how can someone calculate when the two groups will be playing the same note.

[@alexwang982]

Adriel Kere I think lcm?

[@Prinrin]

It's interesting at 8:16 that the bead goes under your shirt but above your arm.

[@Mathologer]

This video is haunted :)

[@reyad9571]

8:09: how is his arm behind the string but his shirt is in front?

[@Mathologer]

This video is haunted :)

[@ragnkja]

Reyad The bottom string is the only one that is in front of Burkard.

[@alexanderthegreat5352]

best math teacher I ever came across

[@martonlovas4583]

Mistake at 16:12: Just because a|bc and a doesn't divide b, a doesn't necessarily divide c. For example: 4|2*6

[@Mathologer]

No mistake, since p is supposed to be a prime number :)

[@SWebster10]

It bothers me too much that 6 is a ‘prime suspect’ on your t-shirt!

[@vwwvwwwvwwwvwwvvwwvw]

Agreed! Among the single digit numbers, there should be a 9 because at least it completes a prime sequence 3, 5, 7, 9 haha. My list of "prime suspects" (i.e., a list of numbers that might appear to be prime at first glance but are not except for one number that is in fact prime!): 51, 87, 83, 91. Can you spot the real prime?

[@AmberZak83]

@@vwwvwwwvwwwvwwvvwwvw 83. (It’s the year of my birth and I always loved that my birth year is prime, if written as two digits).

[@64standardtrickyness]

isn't it Euler's theorem thats used for encryption? also is this secure anymore? I'm told factorization is polynomialish (quantum aside)

[@fhtagnfhtagn]

Little Fermat's theorem alternative representation is a^(p-1)=1 (mod p). With this formula, 561 is not that prime when using it's divisors as a test base. Check this one: 3^560 = 375 (mod 561), not 1. Of course, when we do extra multiplication *3, we have 375*3 = 3 (mod 561) so formula a^p=0 (mod p) starts working.

[@Sarika428]

Everything flashed thru ma mind from 4:34 to 4:43. The best feeling I had in a long time, I usually can't solve such problems or puzzles

[@hglundahl]

If you love Halloween, you should check out Pope Michael's pumpkin collection. Pumpkin a features 3 Pumpkin b features . Pumkin c features 1 ... I think you can guess how the rest of the pumpkin's are inscrbied with lanterns inside, and what he does with the interior of the pumpkins so collected.

[@nikhilkartha4664]

14:29 That sound redundant. They will ofcourse be different always. Unless you mean the number cannot have any powers of primes greater than one. My intuition is that if you have different numbers and you subtract each of them by one or with any given constant, you will still have different numbers.

[@Demki]

13:04 "... is of key importance..." I see what you did there

[@Mathologer]

Actually this video is chock-a-block full of this sort of stuff. You are the first one to notice this particular one :)

[@MrPakurfulo]

I really like your videos

[@raydarable]

9:34 is this a voice-over?

[@Mathologer]

Yes, had to fix something that was not quite right there :)

[@clarencechew3971]

mod 13, 666^666 = 3^666 = (3^3)^222 = 27^222 = 1^222 = 1

[@ssdd9911]

why

[@vindex7]

@Upthorn According to your method 5^5 (mod 3) = 2^2 (mod 3) = 4 (mod 3) = 1 (mod 3). But that's wrong: 3125 = 2 (mod 3).

[@ZainAlAazizi]

Upthorn See mine. Similar approach...

[@michaelguenther7105]

@@vindex7 You _can_ reduce the exponent, but it needs to be reduced modulo ϕ(n), the Euler totient function, instead of n. For a prime p, ϕ(p) = p - 1, so in your example the exponent 5 would be reduced modulo 2, which is 1.

[@TruthNerds]

​@@michaelguenther7105 Thanks! This is called Euler's theorem, btw, which is a generalization of Fermat's little theorem, and is crucial e.g. for proving that RSA decryption is the inverse of encryption. en.wikipedia.org/wiki/Euler's_theorem

[@erik9817]

I liked the last pumpkin example, just what I needed.

[@WonderMePartyStrip]

This video spooked my neurons away.

[@customan10]

Thank you for your videos. I enjoy them so much

[@bhatkrishnakishor]

You just went full drive with the T shirts. Well where is the store for viewers to buy them and support Mathologer?

[@Tehom1]

You can actually narrow down 11^666 mod 13 to two possibilities even more easily. You start the same way, getting rid of 11^660 leaving 11^6. Now just notice that the exponent 6 is half of 12, and we know 11^12=1 (mod 13). So 11^6 equals a square root of 1. There are two square roots of 1: 1 and -1; this holds in mod 13 as well as in the integers, just in mod 13 we call -1 by its nickname "12". If you still want to calculate 11^6, do it as 11 = -2 (mod 13). Then immediately you get 11^6 = ((-2)^2)^3 = 4^3 = 4*4*4 = 3*4 = 12 (mod 13).

[@geraldillo]

So to check if a number is a carmichael number you first have to know the factors? But then you would need another another method to find those, right?

[@gonshi9]

11:45 these 10 seconds are fabulous

[@MCMaterac]

10:59 - a typo spotted. 2^9 - 2 = 510, which is not divisible by 9 -> not prime

[@omarcusmafait7202]

This one is better than usual :)

[@Fun_maths]

Do you have a similar nice visual proof for Euler's generalization of Fermat's little theorem? I would love to see one

[@MadocComadrin]

Never noticed the TSP in P in Bender's head before.

[@Mathologer]

There is some other good stuff in there apart from Fermat's little theorem and TSP :)

[@MelindaGreen]

How many necklaces are there if flipped versions don't count?

[@Mathologer]

There is a way to count those, too, but this count is trickier. When you also allow flipping you usually call these object bracelets. The wikipedia article on necklaces has some basic information en.wikipedia.org/wiki/Necklace_(combinatorics)

[@dlrdn7145]

I love the way you talk. Hugs from Brazil.

[@namahshrestha3226]

I came here to solve a programming problem..ended up wondering about the existence of humanity..great video. Subscribed.

[@YodaWhat]

Hey, the Simpsons were only off by a mere 700,212,234,530,608,691,501,223,040,959 ... or thereabouts. Hardly even worth mentioning! ;)

[@Mathologer]

:)

[@morgan0]

using this to check primeness is 99.999994429% accurate based on the 10^13 table item. and it’s insanely faster than bruteforce checking. either you do 10^13 remainder operations for a number at that size (or modulo since it’s positive) and checking each time what it equals or you do one power, one subtraction, one rem/mod, and one compare. basically it’s O(1) vs O(n), not worth giving up the accuracy at a small scale since there is definitely some spare cpu cycles for it but not when you want to do a positively enormous number. also 10^13 is 10,000,000,000,000

[@SherlockSage]

I think half the comments have beat me to it, but I don't want Jason visiting me 666^12 = 1 (mod 13) 666^660 = 1 (mod 13) 666 = 3 (mod 13) 3^6 = 27^2 = 1^2 = 1 (mod 13) Thus, 666^666 = 666^660 * 666^6 = 1*1 = 1 (mod 13) What I find really interesting are the generalizations of a^(p-1) = 1 (mod p) - For any integer n and any integer a coprime to n, the following holds, a^phi(n) = 1 (mod n) where phi() is the Euler totient function (a function that returns the number of positive integers < n that are coprime to n. Fermat's little theorem is a special case as phi(p) is always p-1 (due to every number less than p being coprime to p) - The Euler totient function is great, but the Carmichael function adjusts the totient function so that it finds the smallest m that always satisfies a^m = 1 (mod n) for any integer a that is coprime to n And from looking at Wikipedia, I also found out that: - While using Fermat's little theorem as a primality test fails for Carmichael numbers, Lehmer's theorem is a stronger version that can be used as a primality test and is in fact used as a basis for the Lucas-Lehmer test which is used to find massive prime numbers - And an extension Fermat's little theorem is used as the basis for the Miller-Rabin primaility test, which is another important and commonly used primality test

[@vwwvwwwvwwwvwwvvwwvw]

Opps! @8:33 you use have 9 beads and 3 colors, but the corresponding divisibility statement is for a necklace of 4 beads!

[@AaronSherman]

You kind of skipped over how primality tests apply the rarity of Carmichael numbers. The fact that it's a purely probabilistic approach is fascinating because it lets us choose exactly how certain we wish to be that a given number is prime by choosing the number of random selections of the term to be exponentiated. You could probably make a whole video out of just that and how modular arithmetic makes it easy to do quickly.

[@Mathologer]

Definitely worth another video :)

[@subhasmondal2007]

@@Mathologer in the video you could explain about using a strong Euler prime instead of a Carmichael number to circumvent the problem

[@subhasmondal2007]

@@Mathologer in the video you could explain about using a strong Euler prime instead of a Carmichael number to circumvent the problem

[@donaldasayers]

1729, now where have I seen that number before? On a taxi perhaps?

[@Mathologer]

Quite possible :)

[@15schaa]

Is BP for Blaise Pascal?

[@mumiemonstret]

I thought that you stopped the Carmichael number list just short of the number on your t-shirt (12:15) just to annoy us. But it turns out that 7635 isn't a Carmichael number. The shirt needs improvement!

[@abhi20user-z8jm5my9p]

When you do quartic equation video ?