After looking at this problem for an entire day, yours is the first lecture that explains the critical step of adding "1" to "break" the factorability of x-1. Incredibly helpful. Kudos. Subscribing to channel right away.
Your explanation of why Euclid added 1 to x was really helpful and clear! My teacher glossed over it so I was confused. Thanks for the clarification! :D
This was great, but at 8:07, one should have raised the question of why X could not be divisible by a non-prime, only to quickly remind that non-prime numbers are always re-factorable into prime.
I was thinking about how if I was in that class, I definitely would have asked that question. "Why does it have to be divisible by a prime? Why can't it be divisible by something which is not a prime, like 6 for example?" But then I remembered that 6 is made up of 2 & 3 as prime factors, which is to say that all non-prime numbers are made up of prime factors.
After finding 100 of videos and 1000 Powerpoints to learn to solve this type of problem on internet, I have finally found the most easiest way to understand the problem. Thanks a lot Genius!!
Thanks a lot! I have spend a day finding this proof through articles and videos, but this is the clearest explanation i've got comparing with any other.
What do you mean?? He's doing amazing. It's much better kids have a good foundational knowledge in class through a slow and thorough demonstration than a quick gloss over, leaving them stressed and working intensively at home...
So we always have to start with the first few prime numbers (cannot be P2,P3,..) and have to be consecutive. We need to include the first prime number (which is the only prime number which is even) to get an even number then add 1 to it (for the number not to be divisible by any of the prime numbers taken).
Is there any mathematical basis for adding one? Cos to me it just looks like it's something you did and is therefore not a constant proof. Does that make sense? Please explain this to me
It relies on the theorem that any two consecutive integers are co-prime (they don't have any common factors > 1), thus adding 1 makes x not divisible by any of the prime numbers p1,...,pn math.stackexchange.com/questions/2046362/consecutive-numbers-are-coprime
There are only two types of numbers. 1) Prime number, 2 ) non prime numbers here adding 1 or any number to X, it results in Prime or non Prime number 1) If x is prime then it should be able to divide itself by either one of the numbers from list of all prime numbers ( p1,p2,p3...pn ) ( as x is multiple of all of them ) but clearly there is no prime number in list which divides x. That means x is either a prime number which is not present in list or some prime number exists which divides the x but thats not there in our list. 3) If x was non prime then obviously it should able to get divied by any one of prime numbers in our list but thats the not case. Thats why we say our asusmtion of finite set of prime numbers is wrong
in the product x is having it is using all the prime numbers lesser than it..So how can some other prime number divide it when it is clearly greater than x.....?
Exactly. That's a contradiction and that is what you are trying to achieve. So, if you prove a contradiction exists you prove your first statement is wrong.
I am confused: Basically, Eulicd said: use the product of all the prime and add +1, this will give you a new prime number. in the case of the video, these prime numbers were used 2x3x5x7= and + 1 = 211 and indeed 211 is a prime number. And this number represent a new prime number. But If we continue 2x3x5x7x11x13 = ans + 1 = 30.031 30.0031 isn't a prime number. So X= (P1xP2xP3xP4xP5xP6)+1 is not a prime number.
The other option was if it was divisible by a prime number which it is: 30031=59 × 509. Thus since there are other prime numbers beyond 13, contradiction.
I’m a year 13 student and in class I was taught this proof but I find it very intriguing because No one is saying how do you come to say with certainty the result of timing every prime number on our limited group of prime numbers won’t be a number that ends in for example 1,3,4,9 which would mean that when we add the one will end in 2,4,5,0 which would make it a non-prime number as we could divide them by either 2 or 5???
It will never give a number like that because of the nature of prime numbers. You can do the proof yourself how many times you want, but the point of algebra is proving something without having to try it 50 times for 50 different numbers. Imagine that the multiplication of all prime numbers is Y. Then X = Y + 1. No matter what you do, no "Y" term can divide X, and all numbers can be written as terms of primes; in our case Y. Which means that if all numbers can be written in Y terms, but X can't, then X must be a new prime or there is a prime missing and Y is an incomplete list. You got a new prime that wasn't on your original "complete set".
Because in this example, the *complete* list of primes are 2, 3, 5 and 7. So if x (211) is a prime, the list is incomplete and should have been - at the very least - 2, 3, 5, 7, 211.
The proof starts by saying that there is a fixed number of prime numbers. So take any list of prime numbers and state that the list is 100% complete. There are no more prime numbers that exist that you can put on that list. Then, say that x = the product of all the elements in the list + 1. By the logic he explains in the video, x would either have to be prime itself OR be divisible by a prime number that isn't on your list. However, you already stated that the list was complete and therefore there can't be any more prime numbers in existence. This is a contradiction and proves that your list is not complete. And because it is not complete, there are therefore an infinite number of prime numbers
Because if he had added 2 or 3 the value of x would also be be divisible by 2 or 3. And the same for all other numbers as they are just products of prime numbers. 1 is not prime, nor is it a product of primes so the value of x in the example would not be divisible by any prime number p1, p2, p3, ..., pn.
That's exactly why that 1 is added; no matter what number u try to divide that product to, there will always be a remainder of 1. Therefore, another prime number is ''discovered'' and the assumption that the list of primes is finite is negated/contradicted.
If you make X only the product of the primes it can be divided by any of those terms; it will always yield a non-prime number. By adding 1, you dive into a differente terrain of numbers that differ from the already known primes, and from there you get new primes you didnt have before.
How can it be divisible by another prime not on our list? That is NOT even an option... Because, a number that is DIVIDED by a greater number For example: x/y (when y>x) is NOT GOING TO BE DIVISIBLE. Ever. Lol IE: 1/2, 1/3, 2/3, 2/4, 1/8 Is that the contradiction??? 👀
It uses another theorem that every integer > 1 can be written as a product of primes. From this it must be the case that some prime number divides 'x', but none of those in the list can divide it. So there MUST exist another prime that is not in our list. The contradiction comes because you have assumed the list contains all the prime numbers, but you have found that it in fact doesn't.
The result of the proof gave us two possibilities: 1. x has to be prime. 2. If x isn't prime, then there must be a prime number that divides it. Assumption: There is a finite number of prime numbers In case 1: If x is prime, then you've disproved your assumption. You created a finite list of prime numbers and proved that x, which is prime, does not exist on that list. Therefore the assumption is false. In case 2: If x is a composite number, there must be at some prime factors that make it up. However, going through your finite list, none of the prime numbers divide x. Therefore there must be another prime number that exists beyond your list. Therefore the assumption is false.
This contradiction is based on the assumption of the existence of infinity: what if there's an "n" such that: P1*P2*P3*...*Pn doesn't exist? I'd like to see a "Proof by Contradiction: Infinity"
A nonprime number is always divisible by at least two other number, and if those factors are non prime, are also divisible by two other numbers until you reach a prime factor. Like if a number is divisible by 27, then it is also divisible by 9 and 3, and 9 is divisible by 3. That means 27 is divisible by 3 and 3 is a prime number.
Around 6:30 he says does "211 divide into 2". My logic says of course it can't as 211 is much larger than 2; however there is an implicit "parts" following in the English which cannot be implied in the maths. A recent report by the AAT into assessment results was scathing about divisions being done backwards (in terms of saying it was simple maths the students were getting wrong without noting the division was being done backwards: "divisor ÷ dividend"). I suspect it was a case of a similar implied "...parts" which was being used in lectures which was missed by the students, especially those with English as a second (plus) language. I suspect this as i help with an adult numeracy class and i hear from students whose first langusge is not English reading "dividend ÷ divisor" as " divisor divided by dividend" but still getting the correct result; they could be trying to translate "dividend divided into divisor [parts]"
@@Raysnature wait have I had it wrong my whole life?? '2 divide in to 211' in my brain means 2/211 and you'd get a really small answer because it's like saying 2 (things) divided into (split into) 211 (pieces), which are gonna hella small pieces xD
errrr ... OK .. lets say: 13 is the biggest Prime-Number .. 2×3×5×7×11×13 = 30030 + 1 = 30031.... 30031 / 59 = 509.... so i just proofed 13 is the biggest Prime-Number???
I had to double check that myself. By showing that 30031 is a factor of 59, You proved the existence of 59 as prime, which is bigger than the original set. Meaning you have shown even more primes to exist.
Euclid didn't prove it by contradiction. Euclid proved that for any finite list of primes, there is another prime not in the list. So any finite list does not contain all the primes, which implies the list is infinite. Which is not the same as assuming there are only finitely many primes. Euclid's proof is closer to a proof by induction than a proof by contradiction.
You need to create multiple scenarios that go accordingly to what you stated, if you keep changing them and it is wrong, eventually a contradictory scenario will come forth. If you think of it; it is not a "nobel tought" or anything, its just "are they infinite or finite?". Its a very simple question, so just work with scenarios where they are finite and play with the boundaries of prime-ness and the answer will appear. It's not that Euler (the guy who actually made this proof) just came up with it on the first try.
Just because someone is an excellent teacher or explainer, doesn't mean he is a great inventor. Feynman and his equals are unique examples of both inventors as teachers. In contrast, Newton was a very bad teacher and explainer, but an amazing mathematician.
A quicker way of putting it: Because the lowest factor greater than 1 of p!+1 must be a prime number and must be greater than p...the primes go on forever. This is not actually a 'proof by contradiction'.
After looking at this problem for an entire day, yours is the first lecture that explains the critical step of adding "1" to "break" the factorability of x-1. Incredibly helpful. Kudos. Subscribing to channel right away.
I agree: a needed ingredient and well placed.
@@mgtowvalues Well put. Same with me too
But he should have shown an example where p1*p1*...*pn +1 is not a prime, but the prime factor is beyound the set of p1,p2,...,pn.
Your explanation of why Euclid added 1 to x was really helpful and clear! My teacher glossed over it so I was confused.
Thanks for the clarification! :D
This was great, but at 8:07, one should have raised the question of why X could not be divisible by a non-prime, only to quickly remind that non-prime numbers are always re-factorable into prime.
I was thinking about how if I was in that class, I definitely would have asked that question. "Why does it have to be divisible by a prime? Why can't it be divisible by something which is not a prime, like 6 for example?" But then I remembered that 6 is made up of 2 & 3 as prime factors, which is to say that all non-prime numbers are made up of prime factors.
Thank the math gods this man exists.
Thank maths this math god exists
Thanks God this man exist.
my name is ben
@@dichocolate hello tim
@@adios04 PARADOX?
What a great video, loved it, That's how the contradiction works everyone. Great work Mr. Eddie
After finding 100 of videos and 1000 Powerpoints to learn to solve this type of problem on internet, I have finally found the most easiest way to understand the problem. Thanks a lot Genius!!
Thank you so much Professor Woo. The best video on Euclid's proof on the web
The only Professor's explanation I actually UNDERSTOOD!! Thank you :')
I've attempted Qs and watched so many videos without understanding it until I came across this video, so thank you! This was broken down really well.
Wow you're much better than my own prof.
Thank you so much for the detailed explanation.
Wow, the way you teaching is really enthusiastically clear, and therefore i get the material.in a energetic thinking!
It helps if you know this axiom which this proof is using: Any integer which is > 2 is either a prime number or can be written as a product of primes.
That’s not an axiom, it’s called the fundamental theorem of arithmetic and you can prove it
@@zafnas5222 this dude is correct
Great explanation, makes it very easy to understand. Thanks a bunch
Thanks a lot! I have spend a day finding this proof through articles and videos, but this is the clearest explanation i've got comparing with any other.
eddie woo da goat
Best explanation I've found on this proof thank you!
absolutely perfect explanation ! amazing !! thumbs up !!!!!
Excellent explanation thank you.
Great instructor. Gold! Thanks !
This is just beautiful.
Thank you, Eddie.
Thank you, the best video on this topic on youtube!!
I love this explanation. 👍👍👍👍
Thank You Mr Woo amazing video
Great explanation. Thank you
best explanation I have seen
great explanation, thank you very much
Beautiful!
This was really helpful 🙏🏻
I am stunned!
Great explanation :).
great explanation!
I fell in love with maths listening this....♥️
Fantastic 🙏
Oh my... I wish you was my year 1 Math professor...
Hello eddi woo sir
I ask u one question is why we right end of the thm is "henced proved"
Thanks man, best explanation
Very helpful.
Regards.
I'm studying software engineering and have to learn all of this stuff. Just have to say, thank you. Your energy is contagious.
thanks a million.
best explanation out there!! (trust me we tried loads too)
Thanks very much!
gifted teacher
Thank you.
super explanation
Euler, you got me
Euclid was a genius and you r genius in explaining..thanks sir
@Eddie Woo. Do you manage to finish the year's syllabus at your rate of teaching?
What do you mean?? He's doing amazing. It's much better kids have a good foundational knowledge in class through a slow and thorough demonstration than a quick gloss over, leaving them stressed and working intensively at home...
So we always have to start with the first few prime numbers (cannot be P2,P3,..) and have to be consecutive. We need to include the first prime number (which is the only prime number which is even) to get an even number then add 1 to it (for the number not to be divisible by any of the prime numbers taken).
great!
Is there any mathematical basis for adding one? Cos to me it just looks like it's something you did and is therefore not a constant proof. Does that make sense? Please explain this to me
It relies on the theorem that any two consecutive integers are co-prime (they don't have any common factors > 1), thus adding 1 makes x not divisible by any of the prime numbers p1,...,pn math.stackexchange.com/questions/2046362/consecutive-numbers-are-coprime
Woo
I didn't understand how we could place +1. I mean you said x= product of all the prime numbers, then how could we place 1?
Because we assume, to set up a proof by contradiction, that there are finitely many primes.
No I think he missed something
Let x be a number = (product of all primes) + 1
Then it leads to a contradiction
There are only two types of numbers. 1) Prime number, 2 ) non prime numbers
here adding 1 or any number to X, it results in Prime or non Prime number
1) If x is prime then it should be able to divide itself by either one of the numbers from list of all prime numbers ( p1,p2,p3...pn ) ( as x is multiple of all of them ) but clearly there is no prime number in list which divides x. That means x is either a prime number which is not present in list or some prime number exists which divides the x but thats not there in our list.
3) If x was non prime then obviously it should able to get divied by any one of prime numbers in our list but thats the not case.
Thats why we say our asusmtion of finite set of prime numbers is wrong
5:25, where does he get 6*5 from?
(2*3)*5 he just skipped the 2 times 3 and went straight to the times five
Thanks
love that
in the product x is having it is using all the prime numbers lesser than it..So how can some other prime number divide it when it is clearly greater than x.....?
Exactly. That's a contradiction and that is what you are trying to achieve. So, if you prove a contradiction exists you prove your first statement is wrong.
I am confused:
Basically, Eulicd said: use the product of all the prime and add +1, this will give you a new prime number.
in the case of the video, these prime numbers were used 2x3x5x7= and + 1 = 211 and indeed 211 is a prime number. And this number represent a new prime number.
But If we continue
2x3x5x7x11x13 = ans + 1 = 30.031
30.0031 isn't a prime number. So X= (P1xP2xP3xP4xP5xP6)+1 is not a prime number.
The other option was if it was divisible by a prime number which it is: 30031=59 × 509. Thus since there are other prime numbers beyond 13, contradiction.
First, nice video Woo
so helpful thank you!
I love you
I’m a year 13 student and in class I was taught this proof but I find it very intriguing because No one is saying how do you come to say with certainty the result of timing every prime number on our limited group of prime numbers won’t be a number that ends in for example 1,3,4,9 which would mean that when we add the one will end in 2,4,5,0 which would make it a non-prime number as we could divide them by either 2 or 5???
aqa a level maths ? :D
It will never give a number like that because of the nature of prime numbers. You can do the proof yourself how many times you want, but the point of algebra is proving something without having to try it 50 times for 50 different numbers. Imagine that the multiplication of all prime numbers is Y. Then X = Y + 1. No matter what you do, no "Y" term can divide X, and all numbers can be written as terms of primes; in our case Y. Which means that if all numbers can be written in Y terms, but X can't, then X must be a new prime or there is a prime missing and Y is an incomplete list. You got a new prime that wasn't on your original "complete set".
Why does x being prime mean the list must be incomplete?
Because in this example, the *complete* list of primes are 2, 3, 5 and 7. So if x (211) is a prime, the list is incomplete and should have been - at the very least - 2, 3, 5, 7, 211.
The proof starts by saying that there is a fixed number of prime numbers.
So take any list of prime numbers and state that the list is 100% complete. There are no more prime numbers that exist that you can put on that list.
Then, say that x = the product of all the elements in the list + 1.
By the logic he explains in the video, x would either have to be prime itself OR be divisible by a prime number that isn't on your list.
However, you already stated that the list was complete and therefore there can't be any more prime numbers in existence.
This is a contradiction and proves that your list is not complete. And because it is not complete, there are therefore an infinite number of prime numbers
why did he only add 1 and not some other number like 3, 5, 7, etc? what's the reason behind adding a 1?
Because if he had added 2 or 3 the value of x would also be be divisible by 2 or 3. And the same for all other numbers as they are just products of prime numbers. 1 is not prime, nor is it a product of primes so the value of x in the example would not be divisible by any prime number p1, p2, p3, ..., pn.
@@ByronDenham I see. Thanks.
Eddie, just call it by the Latin name "reductio ad absurdum."
Why did you add 1 to the "x"? What if x equals just to product of pnth?
That's exactly why that 1 is added; no matter what number u try to divide that product to, there will always be a remainder of 1. Therefore, another prime number is ''discovered'' and the assumption that the list of primes is finite is negated/contradicted.
If you make X only the product of the primes it can be divided by any of those terms; it will always yield a non-prime number. By adding 1, you dive into a differente terrain of numbers that differ from the already known primes, and from there you get new primes you didnt have before.
Start from the beginning I know that's better than my lecture's explanation, they just assume you know everything and I do not T_T
How can it be divisible by another prime not on our list? That is NOT even an option...
Because, a number that is DIVIDED by a greater number
For example: x/y (when y>x) is NOT GOING TO BE DIVISIBLE. Ever. Lol
IE: 1/2, 1/3, 2/3, 2/4, 1/8
Is that the contradiction??? 👀
It uses another theorem that every integer > 1 can be written as a product of primes. From this it must be the case that some prime number divides 'x', but none of those in the list can divide it. So there MUST exist another prime that is not in our list. The contradiction comes because you have assumed the list contains all the prime numbers, but you have found that it in fact doesn't.
The result of the proof gave us two possibilities:
1. x has to be prime.
2. If x isn't prime, then there must be a prime number that divides it.
Assumption: There is a finite number of prime numbers
In case 1:
If x is prime, then you've disproved your assumption. You created a finite list of prime numbers and proved that x, which is prime, does not exist on that list. Therefore the assumption is false.
In case 2:
If x is a composite number, there must be at some prime factors that make it up. However, going through your finite list, none of the prime numbers divide x. Therefore there must be another prime number that exists beyond your list. Therefore the assumption is false.
why do we care if 211 is divisible by an other prime can't it just be divisble by an other number which isn't a prime? I'm stuck
All composite numbers are some products of prime number lesser then them.
g00gle h8r ooooooh ok thx
This contradiction is based on the assumption of the existence of infinity: what if there's an "n" such that: P1*P2*P3*...*Pn doesn't exist? I'd like to see a "Proof by Contradiction: Infinity"
Infinity just means it doesn't end. It's not a thing.
@@Nothing_serious You're confusing "infinite" with "infinity" - the former is an adjective, the latter is a noun (and hence, it is a "thing").
@@jillbluerei4806 Same thing:
Infinite - "limitless or endless in space, extent, or size; impossible to measure or calculate."
-google
Can it not be divisible by a non prime?
A nonprime number is always divisible by at least two other number, and if those factors are non prime, are also divisible by two other numbers until you reach a prime factor. Like if a number is divisible by 27, then it is also divisible by 9 and 3, and 9 is divisible by 3. That means 27 is divisible by 3 and 3 is a prime number.
itfiaslan, ok thx a lot
Why do u add 1?
So division by the divisors P1...Pn always gives a remainder of 1.
@@headlibrarian1996 but that feels forced. the plus one is just something that was added.
Around 6:30 he says does "211 divide into 2".
My logic says of course it can't as 211 is much larger than 2; however there is an implicit "parts" following in the English which cannot be implied in the maths.
A recent report by the AAT into assessment results was scathing about divisions being done backwards (in terms of saying it was simple maths the students were getting wrong without noting the division was being done backwards: "divisor ÷ dividend").
I suspect it was a case of a similar implied "...parts" which was being used in lectures which was missed by the students, especially those with English as a second (plus) language.
I suspect this as i help with an adult numeracy class and i hear from students whose first langusge is not English reading "dividend ÷ divisor" as " divisor divided by dividend" but still getting the correct result; they could be trying to translate "dividend divided into divisor [parts]"
I think he just miss spoke. I believe he meant to say does '2 divide in to 211'. Even Mr Woo is human and says things incorrectly now and again. :-)
@@Raysnature wait have I had it wrong my whole life?? '2 divide in to 211' in my brain means 2/211 and you'd get a really small answer because it's like saying 2 (things) divided into (split into) 211 (pieces), which are gonna hella small pieces xD
@@kismetgundersen9716 Looked at another way and said differently. Does 2 'go into' 211 = 2 'divide into' 211.
those kids dont know how lucky they are. i'd slap the shit out of any kid i saw sleeping in his class
saved my ass
errrr ... OK .. lets say: 13 is the biggest Prime-Number .. 2×3×5×7×11×13 = 30030 + 1 = 30031.... 30031 / 59 = 509.... so i just proofed 13 is the biggest Prime-Number???
I had to double check that myself. By showing that 30031 is a factor of 59, You proved the existence of 59 as prime, which is bigger than the original set. Meaning you have shown even more primes to exist.
@@brightspark1119 this really prooves nothing about math, but how cool body you are :D
Euclid didn't prove it by contradiction. Euclid proved that for any finite list of primes, there is another prime not in the list. So any finite list does not contain all the primes, which implies the list is infinite. Which is not the same as assuming there are only finitely many primes.
Euclid's proof is closer to a proof by induction than a proof by contradiction.
so before you contradicted a statement you got to know how to prove it first?
You need to create multiple scenarios that go accordingly to what you stated, if you keep changing them and it is wrong, eventually a contradictory scenario will come forth.
If you think of it; it is not a "nobel tought" or anything, its just "are they infinite or finite?". Its a very simple question, so just work with scenarios where they are finite and play with the boundaries of prime-ness and the answer will appear.
It's not that Euler (the guy who actually made this proof) just came up with it on the first try.
This is not Euclid's original proof
yeah, Euclid's proof was not using contradiction.
I can tell he's going to invent something amazing for the future of maths..
You can tell that based on what exactly? This is high school math level.
Just because someone is an excellent teacher or explainer, doesn't mean he is a great inventor. Feynman and his equals are unique examples of both inventors as teachers.
In contrast, Newton was a very bad teacher and explainer, but an amazing mathematician.
He'd better do it quick. New concept maths is a young man's game; very few original insights come from people over 40. ;--)
@@Raysnature Or woman's =)
@@faith2756 Indeed! 😊
A quicker way of putting it: Because the lowest factor greater than 1 of p!+1 must be a prime number and must be greater than p...the primes go on forever. This is not actually a 'proof by contradiction'.
I figured out it by myself i deserve a noble prize 😊 just kidding
But yeah i came up with same proof by myself
Thanks