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.
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
> *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
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.
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!
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 😀.
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.
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.
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
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?
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.
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
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 :)
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.
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!!
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.
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.
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.
@@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.
@@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
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 :)
@@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 :)
@@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. :)
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.
@@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.
@@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
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).
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.
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.
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.' ?
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.
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
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
Carmichael characterization works for the prime case as well. Passing Fermat’s little theorem doesn’t always imply prime, but does always imply Carmichaelness.
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.
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.
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
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.
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
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.
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).
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?
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
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.
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.
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!
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.
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.
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 :)
I think there is a mistake on the math master card at 3:14 . It's number is 2718281828459043 however it is not prime, and another thing is if it is a refrence to Eulers number it should be 2718281828459045 (a 5 insted of a 3 at the end). Other than that, great video as always !
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.
SmileyMPV I mean, the last digit is 7, because we have 13^(multiple of 3), and 3^3 terminates in 7. I don’t know how to get the second to last digit, though.
The necklace proof is really lovely! I like it when proofs step outside of the abstract and use elements of reality to help them.
You are the first to comment on the proof ! Definitely one from the BOOK :)
Instablaster...
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.
the a
@@Mathologer TV fadf we we 00 r red we wer deer 4 red
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
Nine sum of 1729 is 1, not 2
The simplest way to factorise 1729: 1729 = (10^3 + 9^3)=(10 + 9)(10^2 - 10 * 9 + 9^2) = 19 * 91 = 19 * 7 * 13.
I did it a bit differently (but still no calculator) and can confirm this answer.
> *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
@@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).
11:04 Why is 9 highlighted?
Yes, one more typo for the Mathologer typo collection :)
Because 9 is prime obviously.
I was totally lost this entire video, but I honor myself in noticing 9 was incorrectly highlighted in a list of prime numbers. 💪 🧠
@Litigious Society
9/1 = 9
9/3 = 3
9/9 = 1
@@DlcEnergy I think you missed the joke in your proof
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.
You explain combinatorics better than anyone I’ve tried to learn from.
This guy is pretty awesome - he has a relaxed style, he is good-looking, and he has a cool accent.
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!
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 😀.
Glad this works for your kids :)
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.
Very good :)
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
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.
Sort of on the list :)
(1^2 - 1) % 2 = 0
Ok. I spent enough time proving it for myself. Cool theorem.
:)
Nice joke lol
Go to 9:34 to witness Burkard's amazing ventriloquism skills.
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
@@Mathologer I caught a very small one at 17:20. Does that count?
@@thingathinga7898 Yes, that one counts :)
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?
If m is divisible by m, then m is definitely not not m.
I think I can solve the mystery of 1729, but I have to do it somewhere else. Can someone please call me a taxicab.
Haha, good one!
But let's hope you live to be older than 32.
:)
That runs on BP fuel.
@@15schaa :)
Another super video. I appreciate them so much and always look forward to the next one!
Absolutely fantastic! Thank you very much for the wonderful presentation!
"561- Infinitely annoying" :D
I like you. You put an effort in pronouncing names of people of different languages correctly. My respects
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.
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
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
@@chandrikasaha6301That was a kind and elegant way to identify the independent creative process.
A really amazing explanation - thank you so much for this amusing and informative video.
Hello from the Czech Republic :-)
Great pronounciation, you are one of the very few people who don't read our "c" as "k" :-)
As my Czech friend once told me, "think of Czech 🇨🇿 as Polish 🇵🇱, but with all of the weird and confusing *double-consonants* left out!"
I love it whenever you make the pictures of mathematicians smile
A really nice touch
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 :)
I'm crying by your explanation it's so so genuinely good and I want the 561 tshirt
10:59 it appears 9 also passes the test according to what's on the screen, although of course it really doesn't.
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.
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!!
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.
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.
Sunday 1 am here in Australia :)
Silly daylight saving time... 😂
saturday 10 am in boston
Isn't 1729 also ramnujams cab number?
hello from the boring isle of england
@@dhruvakashyap You are on to something there :)
Carmichael Numbers *aggressive finger quotes*
That HUGE little smile. 0:38
I wonder how many people will notice :)
@@Mathologer I noticed that too.
that wasn't there until you said it
Fermat suddenly smiling made me shiver so hard wth
Well, good, because this is supposed to be a spooky video :)
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.
At 10:43 your table shows 9 as potentially prime. But with 2 as the constant this should be "not divisible -> not prime"
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.
There is also Euler's theorem! Helps with composite numbers :)
a^(phi(n)) = 1 (mod n)
Where phi(n) is Euler's totient function.
remember that this only applies if a and n are coprime!
What a beautiful proof.Thanks for the content
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
NICE video with the illustration and the likes and the commentsenGLAVIN!
"Don't use a calculator" Too late, I already punched the numbers into the python shell. All hail the pow-function!
Marty won't be pleased :)
Did you know python has a power operator why use a function when it is built in :)
Same thing, but I used the ** notation. Are you using a NumWorks?
@@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.
@@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
Your Prime Suspects shirt is making me scream internally. :D
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 :)
Like for Quadratic Reciprocity!
Soon :)
@@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 :)
@@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. :)
@@Mathologer Absolutely. I have used Fermat's little theorem and enjoyed the necklace animation.
And cubic reciprocity!
Thank you for your videos. I enjoy them so much
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.
mod 13, 666^666 = 3^666 = (3^3)^222 = 27^222 = 1^222 = 1
why
@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).
Upthorn See mine. Similar approach...
@@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.
@@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
I really like your videos
I didn't know this proof! Very good!!!
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).
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.
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.
That 3rd shirt is absolutely brilliant
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.' ?
best math teacher I ever came across
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?
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.
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
Pretty cool proof. So obvious as soon as he began. But cool to view it in that way
I liked the last pumpkin example, just what I needed.
11:45 these 10 seconds are fabulous
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
8:09: how is his arm behind the string but his shirt is in front?
This video is haunted :)
Reyad
The bottom string is the only one that is in front of Burkard.
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
This one is better than usual :)
I love the way you talk.
Hugs from Brazil.
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
No mistake, since p is supposed to be a prime number :)
Carmichael characterization works for the prime case as well. Passing Fermat’s little theorem doesn’t always imply prime, but does always imply Carmichaelness.
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.
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.
13:04 "... is of key importance..." I see what you did there
Actually this video is chock-a-block full of this sort of stuff. You are the first one to notice this particular one :)
Thanks to this video I was able to calculate that I was early!
That was so enlightening!
This video spooked my neurons away.
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
I came here to solve a programming problem..ended up wondering about the existence of humanity..great video. Subscribed.
Great and funny as always!
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.
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
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
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.
15:00
f(1729) = {7, 13, 19}
-> f-1: 6, 12, 18
18 = 3^2 * 2
2 | 1728
3 | 864 (= 900 - 36)
3 | 300-12 = 288
Since all f-1 are distinct and their factors all divide 1729-1, 1729 is a “carmichael” number :)
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).
It's interesting at 8:16 that the bead goes under your shirt but above your arm.
This video is haunted :)
It bothers me too much that 6 is a ‘prime suspect’ on your t-shirt!
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?
@@vwwvwwwvwwwvwwvvwwvw 83. (It’s the year of my birth and I always loved that my birth year is prime, if written as two digits).
That 1 dislike is from Jason because no one wants to hang out with him on Halloween.
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
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.
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.
RIP Apu, you will be missed
Trick or Treat
10:59 - a typo spotted.
2^9 - 2 = 510, which is not divisible by 9 -> not prime
Thats awesome. I never saw or imagine such proof.
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!
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.
Adriel Kere
I think lcm?
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.
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! ;)
:)
You just went full drive with the T shirts. Well where is the store for viewers to buy them and support Mathologer?
isn't it Euler's theorem thats used for encryption? also is this secure anymore? I'm told factorization is polynomialish (quantum aside)
could you do an episode on the haruhi problem
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 :)
I think there is a mistake on the math master card at 3:14 . It's number is 2718281828459043 however it is not prime, and another thing is if it is a refrence to Eulers number it should be 2718281828459045 (a 5 insted of a 3 at the end). Other than that, great video as always !
Opps! @8:33 you use have 9 beads and 3 colors, but the corresponding divisibility statement is for a necklace of 4 beads!
i actually found that first proof by myself, its really nice
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.
A challenge for you:
Calculate the last two digits of 13^(12^(...3^(2^1)...)). Hint: use a generalization of Fermat's little theorem.
SmileyMPV
5? Jk
SmileyMPV I mean, the last digit is 7, because we have 13^(multiple of 3), and 3^3 terminates in 7. I don’t know how to get the second to last digit, though.
last digit is 1