How many prime numbers exist? (Euclid's proof)
ฝัง
- เผยแพร่เมื่อ 13 ก.ย. 2024
- How many prime numbers are there? Will we ever run out? Euclid's proof, elegant and beautiful in how simply and efficiently it deals with such a seemingly enormous problem, settled it once and for all. That's one of the coolest things about maths - once you prove something, it's been proved forever.
This video comes from a series of lessons about cryptography (prime numbers are hugely important to modern encryption algorithms).
Eddie is a great teacher. Let me make some parts of his explanation more explicit and see if I can help the people in the comments writing they couldn't fully grasp the concept yet -----
So 2310 is the product of all primes up until the prime x. When you add 1 to 2310, you actually don't know if the resulting number 2311 is prime or not, and you don't need to:
- If 2311 is prime, then you found a prime number bigger than x, so x is not the largest prime.
- If, on the other hand, 2311 is not prime, then (by the fundamental arithmetic theorem), 2311 is a product of primes. But dividing 2311 by any of the primes until x leaves a remainder of 1, therefore the prime that divides 2311 is not on that list, i.e. the prime that divides 2311 is bigger than x.
In each case (2311 being prime or not being prime), you have a proof that x is not the largest prime. Since you can apply this method to *any* prime number p, you can prove that there is no largest prime number, i.e. there is an infinite list of prime numbers.
Thank you very much for this comment! It helped me alot! :)
I was not the only one thinking this 😊
For people who are struggling (like me) to see what this proof explained, maybe this will help: P is the set of all prime numbers {2,3,5,...,x}. Let us pretend we know only the primes 2,3,5,7. 2*3*5*7 = 210. Add one to that we get 211. We do not care that 211 is prime or composite.
What we do care about is the fact that 2,3,5,7 does not divide 211. If 211 is composite then there exists a number that does divide 211 which is prime, since all composites are products of primes. This prime isn't on our list, therefore, P is not the set of all primes. 211 just happens to be a prime number. So we think that now we have all the primes. Do the multiplication again. We get 2*3*5*7*211 = 44310. Adding one: 44310 + 1 = 44311. 2,3,5,7,211 does not divide 44311. But we find that 73 and 607 divide 44311, which aren't on our list. Add those to our list.
We just keep repeating this forever and thus there are infinitely many primes.
Why would you give the notes, when one could watch it again?
good explaination !
Thanks!
@@paraskwatra2621 sometimes hearing one explanation doesn't cut it. doesn't hurt anyone does it?
@@paraskwatra2621 I didn't understand it watching the video. but understood it reading his explanation.
Simple, clear, and concise explanation to someone who does not fancy Math as a subject. Thank you very much. THis really helps in my computer programming esp in cryptography
Best description I've found so far!! Good stuff!
Eddie Woo said that the product of a set of primes plus 1 is a prime number. This is not always the case. The product plus 1 is either a prime number that is not in the set, or it is a composite number where all of its prime factors are not in the set.
You don't have to go far to find one, for example: 2*3*5*7*11*13=30031
30031 is not a prime number, its prime factors are 509 and 59, both of course not in the set. 30031 is also the first product of consecutive primes plus 1 to be a composite number making it an interesting number.
I think it would have helped to include a mention of the fundamental theorem of arithmetic in this video; Any composite number can be written as a product of primes. Here that means that if you finally obtain a number (p1*p2*p3* +1) which is not prime, (i.e. something that is divisible by another number- a product of primes), then you were missing a prime in your list, to begin with. Hence your initial assumption of having a set of all primes was wrong.
Why would he do that? This is a recording of a lecture, any student taking this course would(or should) already know this.
@@lyingcat9022 you're right i know but it makes for a well-rounded video if you give a *small* summary of what we are meant to be contradicting.
To be fair, the missing prime number from the list isn't necessarily p_1 * p_2 * p_3 * ... * p_n + 1 but a number, let's call it a, which satisfies p_n < a
It seems like there are plenty of explanations and renditions of this proof that casually omit what you just explained. I've seen explanations that assume "case 1" is always true, which you've clearly demonstrated is not always so. Thanks for your rendition of the proof. It is more complete and more accurate than some others out there, but still straightforward and easily comprehensible.
@UCXJZfm9pBXWfOLytrSSTwkQ Since it is not a prime, it must be composite (since the number is strictly bigger than 1 and therefore not unit).
Cool is how good and simple your explanation is.
The proof starts at 4:50
Savier
I found this useful after reading over modeling , theory , and methods.
There are infinite number of prime numbers simply because prime numbers are just infinite amount of numbers added to a previous ones in infinite space of numbers.
Didn't get what you are saying. Can you repeat?
Multiplying together the first six primes and adding 1 doesn’t produce a
prime, but it produces an integer that is merely divisible by a new prime.
Since it's not a prime, it must be composite and every composite is the product of two primes which are not found in our initial list, so there's more primes than in our initial list.
This proof is not quite right. The product of any finite set of primes (P), plus one, is not necessarily prime. It might be. But if not, it must divide by some other prime not in the list. Either way, the set P was not complete.
The proof is right. There was never a claim that the product of all prime numbers + 1 is a prime number. It simply establishes that the new number is a number that will always leave a remainder of 1 if you divide by any of those numbers in the prime set of number we began with. That is you've now got a number that cannot be expressed as product of prime numbers that you claimed were the all of prime numbers (finite) as a premise. Here is an example:
The two possible outcomes after adding 1 to product of all primes in the set is::
1) If new number is not prime -> then we should be able to decompose it as product of primes (like - 81 = 9 X 9 => 3x3x3x3; 21= 7X3; 121 = 11x11). But with 2311, we are not able to divide it evenly - because there is some prime number that we don't know about.
2) If the new number is prime -> then you've just shown that there is a new prime number you've found that is not in the list.
**Both cases show that there is some new prime number out there that you didn't know about; but claimed that you knew all prime numbers were in the set you started with.
@@komalvenkatesh4527 He clearly claims that 2311 (or whatever number you come up with) is the missing prime. Check again from 10:00.
@@komalvenkatesh4527 yeah he should make that more clear though.
@@emiltonklinga3035 and 2311 is not a prime number?
@@tigera6 Yes it is, but not all Euclid numbers are, that was my point, so sorry for being a bit unclear.
would this create a prime if you subtracted one instead?
Eddie: How many primes do you think there are?
Me, a total idiot: mmmh, 17 🤓
👍🏽
Thanks to Euclid and Gauss I know that the lowest factor greater than 1 of p!+1 is a prime number greater than p. I can see why this means the list of all prime numbers is infinite. I don’t know why this video is 10 minutes long.
Thank you!!!
RSA is an initialism, not an acronym.
Eueclid: look I have this list of all the prime numbers proof me wrong!
Eddie: we can... 🤣😂
Its the eueclid who prove this right
Very helpful
That's pretty cool.
2309 is also a prime. So shouldnt one subtracted from the product of all the prime numbers also be prime?
You need to add, because the proof is looking for a larger number. Consider what happens if the X chosen in the video was much smaller. If the set of primes included {2, X} and only those values. The product of all values before X is just 2. If you subtract 1 you end up with 1 which doesnt help prove that the size of the set of primes goes on forever given any valid set of primes.
@@matthewgarber5517 Wouldn't the main problem be that if you took the factor of all these numbers and then substracted one that you might end up with a number that is a composite of 2 or more primes that already are in the list? I don't know if that's mathematically possible, but that would be the first thing I'd worry about.
thanks Eddie Woo enhance my uderstanding
Is he high school teacher? I learned this in college!
I'm not convinced unfortunately, Euclid's formula is widely incomplete
First it does not predict every prime but only a small number of them, starting at (2x3)+1 = 7, jumping to 31 and 211... so where did 2,3,5,11,13,17,19,23,29.... go, and how are they predicted besides the original definition of prime?
Second it predicts numbers that are not prime but products of prime not on the list of primes multiplied, and here's my main question, what if at some point all the results of multiplying primes +1 fall in this category, meaning they're not primes but the product of 2 or more primes not on the list yet? Wouldn't that mean that there is a finite number of primes?
Since we're not there yet, or ever, I'd like to continue to think that the 3rd answer is the correct one for now, until we can scientifically prove that there's a finite or infinite number of primes, the answer is we don't know.
Forgot to add this: Euclid's formula considers 1 to be a prime number (1x2)+1=3 so another good reason to discard it as inaccurate...
The goal of Euclid's formula is not to predict every prime (nobody knows how to do that). It's meant just to prove that there isn't a larger one - in other words, that there is an infinite amount of prime numbers.
@@morpheaworld You literally just proved the statement. 3 is only divisible by 1, not 2. You can not multiply 1 by 2 to form 3 therefore 3 is a prime number which means your list is incomplete and you proved Euclid's statement.
whoaaa......
thanqqqqq
Lol
Mate what you say is BS. not always a product of set of prime numbers + 1 is a prime number.
Yes, he said it in a misleading way. The number we get does not have to be a prime number, that's right, however it requires at least one new prime number that originally wasn't in our list. In the example they did in class they only calculated the product up to 11 and got already a quite big number. Obviously there are many more primes between 11 and 2311 however since every integer can be decomposed into it's prime factors and we know all the primes we've multiplied together are not a factor of our new number after we added 1, we need at least one additional prime to make up that new number.
It doesn't have to be a prime like for example the product of all primes up to 17 is "510510" and after adding 1 we get 510511 which is 97 * 5263. However as i said the prime(s) involved in that new number isn't / aren't contained in our original primes (2,3,5,7,11,13,17) and therefore require a new prime that is larger than our largest one.
I don't know how likely the sum of all primes up to a certain value + 1 is actually a new prime, but i guess it may be as likely as mersenne primes (2^x+1 or 2^x -1)
wrr
Hey anyone who didn't understand?
I am 14 and understood it fully.