How Euler Factored 4,294,967,297 (and Other Massive Numbers)
Вставка
- Опубліковано 17 кві 2024
- In the 1630s, Fermat conjectured that 2^2^n+1 was always prime, although he didn't have the tools -- or the patience -- to check beyond the first 5 examples. In this video, we explore how Euler managed to disprove that conjecture, and find some other crazy factorizations in the process.
we should rename "fermat's little theorem" to "eulers little theorem that fermat didn't prove" just because euler needs more publishing/discovery credits...
Leibniz had a proof. There’s no doubt that Fermat had a proof too bc all it takes is induction and binomial coefficients. Just expand (a+1)^p and take advantage of the fact that pCi is divisible by p unless i=0 or p.
Although the argument is simple, I'm not so sure that Fermat actually had a proof of it. Things that seem obvious now weren't so obvious 400 years ago.
@@GolumTR What is pCi supposed to be?
@@azzteke people use nCk meaning "n numbers, choose k",
nCk := n!/(k!(n-k)!)
I prefer the notation
C(n,k)
A lot of people claimed things that seemed obvious without proof, which were actually obvious; only if a proof is entirely lacking and not obvious do we use the word conjecture instead. Fermat’s little theorem was proved so readily it seems extremely likely he found an induction proof along the lines that one of the other commenters suggested above. Lastly, Euler doesn’t need anything else named after him! FLT is just a special case of Euler’s totient theorem.
Was Euler just a Google search engine or a GPT AI back in his days?
• Kept doing impossible things.
• Generated tons of equations and theories.
• Everyone just sent their questions to him, eg Lagrange, Goldbach, Bernoulli(s), German princesses, etc
He was extremely gifted, definitely. He had to have had an IQ of 160 or 170, maybe even higher.
If you read Fermat’s correspondence more closely, it appears all of Fermat’s conjectures about Fermat numbers, Mersenne numbers, the method for quickly finding factors of the form 2kp+1, and Fermat’s little theorem all date from the year 1640 - not the 1630s. Fermat like Euler found some factors of rather large Mersenne numbers by way of disproving their possible primality. There’s a very helpful article which examines the various letters extant from Mersenne and Fermat which were sparked by a set of inquiries from Frénicle de Bessy: C. R. Fletcher, A reconstruction of the Frenicle-Fermat correspondence of 1640, Historia Mathematica 18 (1991), 344-351.
Thank you very much for mentioning this; that's an interesting article, and I admit that I overlooked some of Fermat's results and conjectures. The excerpt I took from his letter was indeed from 1640, and that appears to be the first mention of Fermat's little theorem. It's also true that he found factors of large Mersenne numbers using the 1 mod 2p idea. I suppose the reason he didn't do the same for 2^2^n+1 was that he was going based off examples, rather than proofs, and the small examples led him to believe that those numbers were always prime.
However, he first conjectured that 2^2^n+1 is prime in the 1630s, not 1640 (at least according to a source published by the MAA). I will have to do some more work to track it down. Thanks again for the thought-provoking comment!
@@MathFromAlphaToOmega In terms of Fermat’s testing of 2^2^5+1 and 2^2^6+1 (which he actually had evaluated numerically), for the latter the problem looks intractable by trial division but F6 turns out to have a relatively small factor. F6 was factored twice in the 19th century, separately by Clausen and Landry; again the article by H.C. Williams, How was F6 factored? Math. Comp. 61 (1993), 463-474, is a nice insight into how Landry might have achieved the result knowing that factors existed (Lucas had proved F5 and F6 were composite several years before).
It is not quite so easy to write off the case of F5, since it is only 210 trial divisions up to the square root using Fermat’s or Euler’s method. The fact Fermat missed finding the 5·2^7+1 factor points to two possible conclusions:
(1) he made an error in his long division when he reached 641;
(2) he did not try looking for factors at all.
I think it’s hard to establish which is true at this distance.
Edited to add:
I’ve had a look through the Fermat volume of correspondence (the 1894 publication by Gauthier-Villars) and I can’t see anything resembling investigations into Mersenne or Fermat numbers prior to 1640, so I am curious what source MAA had for the 1630s claim, if you can easily lay your hands on it.
I was gonna say, what is the prime factor of 2^2^6+1? But then I just wrote a Python script incorporating the idea from the video instead.
@@Xanthe_Cat There was a series of articles posted on the MAA website about Euler's work, and one of them was on the Fermat primes. The author says that Fermat mentioned the conjecture in "several of his letters during the 1630s and 1640s." You can find it on the Euler Archive - it's called "How Euler Did It".
@@MathFromAlphaToOmega I’ve already read it - if that’s the article by Ed Sandifer you’re citing on the factorisation of F5? He doesn’t source his claim for 1630s and 1640s, and given the general tenor of the discussion that sounds like he’s mistaken which decades Fermat was writing letters about Fermat numbers - you’ll find letters to Pascal and Kenelm Digby which cite Fermat numbers, but there’s nothing in the 1630s.
Edited to add dates for letters:
Pascal, letter 79 (29 August 1654)
Digby, letter 96 (June 1658)
Drawbacks for reading Fermat’s letters:
(1) You have to be able to read French and Latin to some degree (I know enough to make rough translations), and
(2) The compilation of letters is obviously extremely complete. (Not.)
However, there doesn’t seem to be anything with regards to perfect numbers prior to 1640, and it was Frénicle’s challenge to Fermat in 1640 (in a letter relayed to Fermat by Mersenne) that seemed to prompt Fermat into the research that yielded Fermat’s little theorem and the conjectures about the 2^x-1 and 2^x+1 sequences, that x had to be prime in order for 2^x-1 to be prime, and x had to be a power of 2 for 2^x+1 to be prime.
Most embarrassing conjecture ever. The first nontrivial element breaks it
"yeahhh so i looked at the first few of them, they're all prime. and the next one is too big to figure out for now, so i'll just leave it there and say it's an open problem"
Proof by lack of counterexample
@@vassilispetrides8841,
yeah , true , until -
until someone makes himself ready to take the trouble .
This will be what people say about Riemann hypothesis lmao
@@FishSticker Well no, there's nothing trivial about the points we've found on the critical line
Lovely video! Subscribed!
Thank you - that means a lot!
Yo! You're also here.
At 6m40s et seq, yes, it's true that you can't replace the "2" in Mersenne's expression with any larger integer, a>2, because you'll always get a multiple of (a-1); but all you have to do is notice that when a=2, you can "say" you're dividing by (a-1) = 1, and retain that divisor in the formula.
You will then sometimes get primes that are "pseudo-Mersenne," or "generalized-Mersenne" numbers, which can also be interesting.
M(a,p) = (aᵖ - 1)/(a - 1); a,p > 1
a ≠ square or higher power of any integer, and p = prime
Fred
In particular, M(a,2) = a + 1, which is uninteresting, leading to a prime iff a is 1 less than a prime; but for k > 2, there are interesting cases, the first being
M(3,3) = 13 (prime)
Some others are:
M(3,5) = 121 = 11² [note that 11 ≡ 1 mod (2k = 2·5)]
M(3,7) = 1093 (prime)
M(3,11) = 88573 = 23·3851
M(5,3) = 31 (prime)
M(5,5) = 781 = 11·71
M(5,7) = 19531 (prime)
M(6,3) = 43 (prime)
M(6,5) = 1555 = 5·311
M(6,7) = 55987 (prime)
etc.
@@ffggddss That's a fair point - thank you for mentioning that. The same trick with orders will work there, too, but the numbers grow much faster, so it's not nearly as helpful as with 2^p-1.
Great video! I am looking forward to new ones if you are planning to continue. Maybe next time, I would suggest cranking up the speed of the visuals a bit, as it can get a bit annoying when waiting for the text to finish writing itself. Otherwise, really an awesome video. Good luck!
Thanks for the feedback - I'll keep that in mind next time!
at 8:02 the french use to do maths is so different from today's that even as a french maths student i dont understant what he meant
Ouais, c’est souvent très difficile de comprendre ce que les anciens mathématiciens voulaient dire. Leur façon d’expliquer les choses était beaucoup plus compliquée que la nôtre. Si vous essayez de lire les textes des Grecs anciens, c’est encore pire !
I really loved this video😊
My feedback to you is that you could add a bit more enthusiasm to your vids and not pause a lot. I don’t want to seem mean lots of love 🥰
Thanks - I appreciate the feedback!
@@MathFromAlphaToOmega I disagree with this suggestion. I like the cool calm tone of your commentary and the complete freedom of your videos from Hollywood tinsel (music, shouting, visual gimmicks, etc.). The pace is right for me: I last studied mathematics several decades ago and need to pause occasionally to make sure I've fully grasped what you've just said, which is good. Finally and more trivially, it's a tremendous pleasure to find a presenter who pronounces foreign names reasonably correctly and doesn't just assume that his audience will run a mile when they see a quotation in French. Keep up the good work. Subscribed.
@@robert-skibelo Thank you for the kind words, and I'm glad you enjoyed the video! My goal is always to make the math interesting in its own right, without needing to add anything over-the-top. Your comments show me that people appreciate that, and it's very encouraging!
i'm really appreciate your videos! it's really to my taste!
i love maths too
Thank you! I'm glad you like them!
Cool vid, subscribed.
I'm not convinced by the proof at 10:20. Sure, if b is a multiple of d then a^b = 1 mod p. But the question is whether a^b can equal 1 mod p when b is not a multiple of d. When you say "the first p-1 powers of *a* can be split evenly into these cycles" you're assuming the conclusion, namely that d divides p-1. Also, since your argument never uses the assumption that d is the _smallest_ positive integer with *a*^d = 1 mod p its definitely missing something.
The key is that if d does not divide p-1 and we don't get a cycle then that means p-1 lies between two multiples of d. So p-1 equals a multiple of d plus an integer r strictly between 0 and d (this is the division algorithm). This implies a^r = 1 which contradicts the fact that d is the smallest such positive integer.
You're right that I skipped over some details there; I did that just to give an intuitive explanation of what's going on. The fact that d is the least exponent with that property is what tells us that the circle has d points on it. Then the only powers corresponding to 1 are the multiples of d. I was debating whether to include a more rigorous proof, but I decided against it in favor of a more visual argument.
A much simpler and more correct proof of this fact would be to let b be the smallest positive integer for which a^b = 1 (mod p), and then write d = qb+r by Euclidean division (so 0
Place an infinite amount of points on a circumference of a circle. Then pick any point of your choice on the circumference. Add one to that point or subtract one from that point. How far have you moved on the circumference in radians?
What type of numbers are those in the thumbnail where it says 20 digits and where it says 98 digits?
What's the difference between finding a proof like Euler did (among millions of possible proofs) and just finding a prime factor (among millions of possible factors)?
can anyone explain the step from the 3rd to 4th line at 4:10?
In general, a sum of odd powers can always be factored. If you divide x^n+y^n by x+y for n odd, you'll get x^(n-1)-x^(n-2)y+x^(n-3)y^2-...+y^(n-1).
To go into it more deeply. Consider A^3 - B^3 = (A - B) x (A^2 + A x B + B^2 )
Numerically lets take some big numbers
31^3 - 26^3 = (31 - 26) x (31^2 + 31 x 26 + 26^2)
29791 - 17576 = 12215 = 5 x (961 + 806 + 676) = 5 x 2443
and we see it works out
This can be done with ANY power
such as A^12 - B^12 = (A - B) x (A^11 + A^10 x B + .... + B^11)
Now if we have an odd power we can swap the sign of B; i.e. (-B)
A^odd - (-B)^odd = A^odd - (-1)^odd x B^odd = A^odd + B^odd and we have a factorization with sums of odd powers.
Thus we could say that 31^3 + 26^3 = (31 + 26) x (31^2 - 31 x 26 + 26^2) and we can check 47367 = 57 x 831
So you have 2^28 + 1; since 28 has an odd factor (28 = 4 x 7) we see that we could write it as 2^28 + 1^28 = (2^4)^7 + (1^4)^7 = 16^7 + 1^7 and use the sum of odd powers trick
2^28 + 1 = 16^7 + 1^7 = (16 + 1) x (16^6 - 16^5 x 1+ 16^4 x 1^2 - 16^3 x 1^3 + 16^2 x 1^4 - 16 x 1^5 + 1^6)
or 268435457 = 17 x 15790321
namely the key feature was that 17 divides 2^28 + 1
Since we are looking for primes of the form 2^N + 1 ; we notice if N has any odd factor; then 2^(N/odd factor) + 1 will be a factor of 2^N + 1; example 2^20 + 1 since 5 is a factor of 20; then 2^(20/5) + 1 = 2^4 +1 (=17) will be a factor of 2^20 + 1 (=1048577; and yes 1048577 = 17 x 61681)
and things like 29^416 + 14^416 ; which is about a 609 digit number ; we can notice that 416 = 13 x 32
Thus 29^416 + 14^416 = (29^32)^13 + (14^32)^13 ; and thus 29^416 + 14^416 is divisible by 29^32 + 14^32 ; which is a 47 digit number.
Damn those margins: none of them is wide enough to contain "6700417" (and its many many prime factors...)
With the advancement of modern computer and Mathematicians out there will they ever find a bigger prime than 2^82,589,933-1
Almost certainly, but the Mersenne primes get rarer and rarer as the exponent increases, so it takes a ton of computation to find each new one.
@@MathFromAlphaToOmega and one other aspect that I just realised that 2239*36887 = 82,589,993. Witch makes 82,589,993 a semi prime number
With all the primes they had in the early 18th century, 1+2^32 would still have been possible- they'd just need all primes less than 1+2^16!
That’s only 6500 or so trial divisions up to the square root; Fermat’s 1 mod 2p method (attributed here to Euler, but Fermat undoubtedly knew it as well) reduces the work to 210 or so; and Lucas’s refinement narrows that to just 99 primes needing to be checked. (But how do you get that list of thousands of primes up to 2^16 in the first place? Well, recursively obviously, by trial divisions up to the square root, which is 2^8 for the largest possible primes. It’s still a mammoth amount of work, just to check one number.)
Fermat either didn’t have the appetite to conduct two hundred or so trial divisions, or he made an error when he got to the case of 5·2^7+1. It seems impossible to know which is true at this late date.
@@Xanthe_Cat I think he says here that at the time, they knew all primes =< 10^5- because referencing this list, they'd have more than enough primes to factor a number as big as (or bigger than) this 1+2^32 I started with.
Loader please! You don´t talk for yourself but for listener. Your voice needed to reach to your listener!