Who thinks clearly - talks clearly. The best explanation I've seen. And as a teacher I will repeat it again and again: There is nothing better so far invented than a class board. There is no substitute for good language.
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.
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!!
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.
@@anonymous99923 I usually first remind to a class definitions which would be involved in the reasoning. In this case I would remind definition of "prime devisor", after that most would remember that we are not listing a number of devisors but prime devisors. Presentation and instructor are superb.
I usually first remind to a class definitions which would be involved in a reasoning. In this case I would remind definition of "prime devisor", after that most would remember that we are not listing a number of devisors but prime devisors. Presentation and instructor are superb.
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.
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
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).
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.
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
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.
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".
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.
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
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...
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"
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.
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.
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.
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
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.
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.
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'.
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.
Who thinks clearly - talks clearly.
The best explanation I've seen.
And as a teacher I will repeat it again and again:
There is nothing better so far invented than a class board.
There is no substitute for good language.
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
The only Professor's explanation I actually UNDERSTOOD!! Thank you :')
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
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.
@@anonymous99923 I usually first remind to a class definitions which would be involved in the reasoning. In this case I would remind definition of "prime devisor", after that most would remember that we are not listing a number of devisors but prime devisors. Presentation and instructor are superb.
Wow, the way you teaching is really enthusiastically clear, and therefore i get the material.in a energetic thinking!
What a great video, loved it, That's how the contradiction works everyone. Great work Mr. Eddie
I usually first remind to a class definitions which would be involved in a reasoning. In this case I would remind definition of "prime devisor", after that most would remember that we are not listing a number of devisors but prime devisors. Presentation and instructor are superb.
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?
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
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.
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
Great explanation, makes it very easy to understand. Thanks a bunch
Best explanation I've found on this proof thank you!
Wow you're much better than my own prof.
Thank you so much for the detailed explanation.
I'm studying software engineering and have to learn all of this stuff. Just have to say, thank you. Your energy is contagious.
I fell in love with maths listening this....♥️
I am stunned!
This is just beautiful.
better explanation than the first dude appeared on the video list after searching
Thank you, the best video on this topic on youtube!!
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
Thank you, Eddie.
best explanation I have seen
Oh my... I wish you was my year 1 Math professor...
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 explanation. Thank you
Beautiful!
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.
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
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
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.
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".
Hello eddi woo sir
I ask u one question is why we right end of the thm is "henced proved"
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.
absolutely perfect explanation ! amazing !! thumbs up !!!!!
great explanation, thank you very much
Excellent explanation thank you.
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
thanks a million.
I love this explanation. 👍👍👍👍
best explanation out there!! (trust me we tried loads too)
@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...
Great instructor. Gold! Thanks !
great explanation!
This was really helpful 🙏🏻
Great explanation :).
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
Fantastic 🙏
Thanks man, best explanation
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.
super explanation
gifted teacher
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
Very helpful.
Regards.
Thank you.
Eddie, just call it by the Latin name "reductio ad absurdum."
Euclid was a genius and you r genius in explaining..thanks sir
Thanks very much!
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
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.
Euler, you got me
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
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.
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.
Woo
Thanks
great!
those kids dont know how lucky they are. i'd slap the shit out of any kid i saw sleeping in his class
love that
This is not Euclid's original proof
yeah, Euclid's proof was not using contradiction.
I love you
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'.
saved my ass
so helpful thank you!
First, nice video Woo
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! 😊
I figured out it by myself i deserve a noble prize 😊 just kidding
But yeah i came up with same proof by myself
Thanks