I think it's just simpler to say that q gives a remainder of 1 when divided by any prime p(i), i=1,2,...,n meaning that it's not divisible by any p(i) and is therefore prime itself
@@mathsoldier3413 Let us consider first prime number 2 2+1 is a prime 3 2*3+1 is a prime 7 2*3*5+1 is a prime 31 Now if u divide 31 by 2 u get remainder 1, By 3 u get remainder 1 By 5 u get remainder 1 A number is a prime if it has only 2 factors 1 and itself. If u want to test if n is a prime or not u will have to start diving at 2 and keep going until n-1; Smarter way would be to stop at n/2 Even smarter would be square root n Any composite number can be represented as a factor of multiple prime numbers. If a number can not be represented as a factor of prime numbers it would mean that number is also a prime number. q can not be represented as a factor of all prime numbers available p1 to pn because when you divide by any p1 or p2 or pn you will get a remainder of 1. This means q is also a prime. That would mean pn was not the largest prime and that would mean there are infinite prime numbers. What about p1*p2*p3*...pn+2? This is not a prime number because it would be divisible by 2 because p1=2.
alright I'd say.. the contradiction comes also from the fact that in the definition of Q, division by pk gets remainder 1, and since pk divides Q (as it is one of his prime factors) it has also remainder zero, so this is in contradiction with the uniqueness of quotient and remainder in the algorithm of division :)
There are a lot of fun variants of Euclid's proof as outlined here. Here's a cute variant (which requires knowing already that 2,3 and at least one other number are prime): Suppose there were only finitely many primes; then we can set q as the product of all odd primes, so then q+1 and q-1 must both be powers of 2 (since they have no odd prime factors). But q+1-(q-1)=2 and the only powers of 2 which differ by 2 are 2 and 4, so q=3, but obviously q>3. Contradiction. Here's a very different proof which is highly silly for being unnecessarily overpowered: consider the Riemann zeta function. zeta(2)=pi^2/6 and zeta(2) has the Euler product representation. If there were only finitely many primes then zeta(2) would be rational since there would be finitely many terms in the Euler product each of which is rational. But pi^2 is irrational and hence so is pi^2/6 which is a contradiction. This one is fun for requiring that pi^2 is irrational, that zeta(2)=pi^2/6, and that zeta has the Euler product representation. There may be more convoluted proofs of the infinitude of primes (the one using DFAs is also almost as bad) but I don't know them.
My favorite thing about this is, without knowing there are more than 3 primes, this proves that there are either 3 primes or infinite primes. Quite the juxtaposition.
To anyone interested, a shorter way of putting it: Because the lowest divisor greater than 1 of n!+1 must be a prime number and must be greater than n...
At the end of these holidays in France, I will start the university, specialized in math and your videos are so cool man All the things with the u world, the integrations, I've never seen that at school, your channel is full of wonderful tricks Thanks
_Finally_ somebody explains why the product of all the primes plus one has a prime factor that's not part of that list of primes. When this proof is presented by people (and sometimes even books), it almost always lacks that explanation.
I don't think that the explanation presented in this video is the best one out there. It could be done more simpler. An integer is divisible by another integer when the numerator (a.k.a. the dividend) is an exact integer multiple of the denominator (a.k.a. divisor). In other words, when the numerator has the same prime factors as the denominator, along with some other factors perhaps. For example: 21 is divisible by 3, because 3·7=21. Written as a fraction: 21/3 = 7·3/3 = 7. The numerator (21) was a multiple of the denominator (3), because you can get seven `3`s and get `21`. When you divide them, you take away these threes, one after another, and see how many times that was possible, and if there's something left afterwards (something less than `7`, a remainder). But there isn't: `21/3 = 7·3/3 = 7`. It was possible to take away `3` seven times, and nothing was left. So the answer is `7`. But if there's a remainder (e.g. when you divide `23` by `3`), then `3` does not fit exactly into `21`. Instead, you can take it away seven times (as before), but there's a remainder of `2` which is less than `3` and cannot be taken away. So `3` fits into `23` seven times and a bit. That bit is `2/3` (the remainder, which still remained to be divided by `3`, and it cannot). So we can write: `23 = 7·3 + 2`, which means that `3` goes into `23` seven times, and then you can only add `2` more. Now back to the proof. When you have a bunch of primes, and you multiply them together, you get a number, let's say `A = 2·3·5`. And this number is divisible by each of these primes, because if you put one of these primes in the denominator, it will cancel with the according prime in the numerator, leaving the product of the other primes as a result. E.g.: 2·3·5 / 3 = 2·5 But what happens when you add `1` to that product? B = A + 1 = 2·3·5 + 1 This means that when you try to divide `B` by any of these primes, there will always be a remainder of `1` ! The prime only divides evenly into `A`, leaving the other primes as the quotient, and the `+1` as the remainder. No matter which of these primes you choose to divide `B` by, this remainder of `1` will always be there. This means that you _cannot_ divide `B` evenly by _any_ of these primes. The result will always be some fraction. (The integer part will be the quotient, and the fractional part will be the remainder divided by the divisor.)
_"This means that when you try to divide `B` by any of these primes, there will always be a remainder of `1` !"_ That's an assertion presented without proof. *Prove* that there is always a remainder of 1. That's what this video shows, and what most often lacks in the "proof" when it's presented by most people.
What I wrote above was just the answer to the question "why", not the proof of it. I thought that was what you were asking about. But if you want proof, then Euclid's original proof contains it as its lemma. See also one of Sci Twi's comments here. She answered exactly that question by explaining how Euclid's lemma works.
OK here's how Euclid did it (rephrased a bit to make it standalone): Suppose that `q` divides both `p` and `p+1`. Then `q` would also have to divide `1`. (Because if something divides the sum and one of its parts, it also has to divide the other part. Do I have to prove this one for you as well? Or do you believe this is true?) But this is impossible, because the unit is supposed to be indivisible (by any other integer except `1` itself). So we have a contradiction, and our original assumption has to be false. The other one is true: that `q` can divide either `p`, or `p+1`, but not both. (Another way to see it is to notice that the smallest prime is `2`, so the minimum gap between two numbers that are both divisible by it, is `2`, not `1`. So if they're off by `1`, they cannot be both divisible by the same prime at the same time. If one of them is, the other cannot.)
Cool... If you are open to ideas, it looks to me that those are some of the tradicional Internet proofs but also some of the most clean proofs (and somewhat not like most proofs iykwim) and there are a lot more and more profound proofs outhere... Just within the basics of number theory there are: the division algorithm, Bézout's identity, (which use the good ordered theorem). You could also try the Fundamental Theorem of Arithmetic, and from that the number of divisors of a number... Or proof that if p prime and p|ab then p|a or p|b (to show how to proof an or statement)... Just some ideas... Very nice channel, btw.
Guille Heraldo S12 Valdeón Thanks for the suggestion. I was in Berkeley these past weeks and just felt like I wanted to do some proofs, as of these were the first things that I learned in my student years. I may do more classic proofs later on if I can find some big blackboards. :)
Can someone please explain to me why we add a 1 to the product of all primes. Is it just there so that we get a fraction at the end or what purpose does it serve?
It's because if you have a number that is the product of all the prime numbers + 1, now it's not divisible by any of the prime numbers, so it must be a new prime number.
you +1 because you 'can' this new number (like any number) must have a UNIQUE prime factorization, this is what Pk represents, being both a factor of Q and a number in the set of {P1-Pn}
Nope, not necessarily. Imagine your list of primes was {2, 3, 5, 7, 11, 13}, if you multiply these together and add 1 you get 30031, which is not prime, in fact 30031 = 59 * 509. The new number is not necessarily prime, but it must have prime factors that are not on the original list.
I was responding to the original commenter, not to you, unfortunately youtube's comment system doesn't make it very clear who comments are directed at.
Not only that, but also some commends don't show up at all. They're visible only to the user who write them, and silently invisible to everyone else. It happens all the time to me. 99% of my comments here never show up.
Let's try proof by contradiction. Suppose this is not the best video to ever exist. Let's find an example of a better video... Oh wait...... There seems to be a contradiction in my contradiction... :q Umm... I found a brilliant proof of this theorem, but there was too few space in this comment to put it all ;>
Please do #15 on the 2017 MIT integration bee qualifying exam, lim n->infinity of I n where I1 = ∫ 1/1+sqrt (x, I2=∫ 1/1+(1/1+sqrt (x)), I3=∫ 1/1+(1+1/(1/1+sqrt (x))) ...
If the set of prime numbers is finite, then: 0 < product for all primes p of sin(pi/p) = product for all primes p of sin(pi*(1+2*(product for all primes p' of p'))/p) = 0 QED (see the following image for the well written formula: gyazo.com/88fbcc88077cc96c7995dc5a374f67ea )
{P1, P2,...Pn} is a finite set thus has a highest element which is Pn we can easily show that q < Pn (since it's multiplied etc..) thus q doesn't belong to {P1,P2...Pn} How about using bezout's theorem to prove that gcd(q , Pk) = 1 ? yea its quite the same
A shorter way of putting it: The list of primes is endless because the lowest factor greater than 1 of p!+1 must be a prime number and must be greater than p. This is not actually a 'proof by contradiction'.
GeekJokes mainly because it’s annoying. It makes prime factorization trivial - also, all numbers would have an infinite number of prime factors, that infinite number being infinite ones, so discounting one as prime just makes everything more ‘meaningful’. Of course, none of these are world-breaking problems - all can be solved with a bit of tweaking - but it’s annoying and the easier fix is “1 is not prime”.
@Patrik Wild In fact, that is how it used to be. One used to be a prime, but every single time you had to go "blah blah blah primes, except 1." It got old, and people thought "if we always have to exclude 1 nearly if not all the time, maybe 1 doesn't belong in this group" and so we altered the definition from "is divisible by only itself and 1" to "is divisible by exactly two factors, itself and 1" and made life simpler.
Why is there a necessity of adding "1", if I have "2" being added Q = (p1*p2*p3*p4) + 2 , would it make this proof not work since I now have a '2' on the right side ---> = 2/pk , since pk can be '2' this would make the right side an integer, and since the left side of (Q-(p1*p2*p3*p4)) /pk is an integer wouldn't this now make the equation hold true? . . . Oh wait . . . Ohh I get it now since we are assuming that there are an " finite " number of primes, then an arbitrary equation like this must be true for all values of 'c' at the end of Q = (p1*p2*p3*p4) + c I wonder how this proof would work if '1' was considered a prime number, I guess it wouldn't work maybe . . . Wait so hold on so if ' 1 ' was considered a prime number then we could use a constant lower than the value of 1 such as 1/2, for instance: Q = (p1*p2*p3*p4) + 1/2 And then we would run into the same contradiction again Thus, proving that the arbitrary equation does NOT satisfy ' all ' values of 'c' to hold true for the equation Thus there must be an infinite amount of primes because when you assume that there aren't , "this equation derived from assuming so", would never would never hold true for all values of c ~ Any feedback?
you missed one essential thing, any number achieved by multiplication of prime numbers will be even, so if you add 2 instead of 1 the number will never be a prime since you just introduced a 3rd factor to it (itself, 1 and now also 2, since it's even) and 1 is not a prime by convention afaik, to make it easier (not really sure on the origins of that, so look it up if you are keen enough)
Many months late, but I thought I would respond. Including a "+c" at the end would be problematic, since Q could then possibly be divisible by one of the primes in your list. As you point out, if one of the primes in your list is 2, then taking (p1*p2*p3*p4)+2, for instance, _would_ be divisible by 2. So we no longer have a contradiction. If 1 were considered a prime, the proof would still work, but you would just have to say more words about why 1 isn't an issue. This is the benefit of excluding 1 from the list of primes - it allows us to simplify arguments and statements. And you cannot allow c to be a non-integer. The Fundamental Theorem of Arithmetic only applies to integers. If you had c = 1/2, then Q would no longer be an integer, so you couldn't conclude that it would have to be divisible by some prime.
I knew your proof will be bad (I already expected it being done by contradiction, as most people nowadays do it), but I didn't expected it to be _that_ bad! :( Where should I start?... Let's start from the usual misconception about the "contradiction". Euclid's original proof was _not_ by contradiction at all! And you would know that if you looked into the actual "Elements" by Euclid (Book IX, Prop. 20), e.g. the English translation by Heath, or that on David Joyce's website. He pretty much said: "Give me your set of prime numbers, and I'll show you how to find a prime number which is not in your set." (And since this can be done as many times as you please, it must mean that "there's more of prime numbers than any assigned multitude of prime numbers", quoting Euclid.) It is a common misconception repeated over and over by modern mathematicians who distorted Euclid's original proof by sandwiching it into a proof by contradiction. There are several mathematical papers explaining that in depth, such as "Prime Simplicity" by Hardy and Woodgold (2009) with an excessive list of references to literature with examples of distorted versions of the proof, or their later paper "Three Thoughts on Prime Simplicity" (2012), or Siegmund-Schutlze's work "Euclid's proof of the infinitude of primes: distorted, clarified, made obsolete, and confirmed in modern mathematics" (2014), with very nice and logical breakdown of Euclid's original proof and comparison to modern versions.
As Timothy Gowers wrote on his blog post "When is a proof by contradiction necessary?": | _This is a question that arises when I am teaching somebody who comes up with a proof like this._ | _“Suppose that the sequence `(aₙ)` is not convergent._ | _Then … a few lines of calculation … which implies that `aₙ → a`._ | _Contradiction.”_ | _They are sometimes quite surprised when you point out that the first and last lines of this proof can be crossed out._ It is less funny when you find most of the modern versions of classic proofs to look like this, or when you find a lengthy proof of some complicated statement which has been unnecessarily made into a proof by contradiction :P That's why some famous mathematicians started to be dubious about proofs by contradiction recently, and they try to figure out when is a proof by contradiction unavoidable, and when it can actually be avoided and replaced by a direct proof.
The next bad thing in your proof is that you said that the primorial plus one cannot be a prime. Sure, I understand that it is true _if_ you assume that your set already contained all the primes there are, and `q` is definitely not in that set, so it cannot be a "prime" (according to this definition, based on belonging to a certain set). But this way of proving it is directing your viewers' train of thoughts into very wrong tracks! Because they may be tempted to think that this number can _never_ be a prime, which is simply not true! There _are_ primes of the form `p₁·p₂·p₃·…·pₙ + 1`, the simplest one being `2·3 + 1 = 7`. If you assume that `2` and `3` are "all primes there are", and Euclid's trick shows you that their product plus one is `7`, then according to your definition, `7` cannot be prime, which is false, because it's enough to try to divide it through all the numbers from `1` to `7` to find out that it has only two factors: one and itself, which makes it a prime too (according to the _right_ definition of what a prime number is).
Telling the students that the primorial plus one is always a prime is no better, though, because the student might get a wrong impression that this is a way to construct a number that is _always_ prime. And when they check some of the first simplest examples, they find out that this is the case, which convinces them even more into believing that this is the case. E.g. `2+1=3, 2·3+1=7, 2·3·7+1=43` ... But a simple counter-example can tell us that it isn't: `2·3·7·43=1807=13·139`. Your proof is also overly complicated (not to say obfuscated :q ). Much more complicated than the original Euclid's proof which can be contained in a couple of lines. (Look at the original proof and you'll see what I mean.)
That's why Euclid didn't do it that way, and didn't make any of these assumptions: a) He didn't assume that the "any assigned multitude of prime numbers" (basically a set) is _exhaustive_ (i.e. that it contains _all_ prime numbers). He just assumed that it is _some_ finite set of prime numbers. b) He didn't assume that this set is continuous (i.e. that you didn't miss any of the primes). c) He didn't even use a product of primes! Instead, he took "the least number DE measured by A, B, and C" (so basically the least common multiple of those primes). d) He didn't claim that this number plus one is a prime, or that it isn't - instead, he said that it could _either_ be a prime number _or_ a composite number (since course there are only these two possibilities to consider), and showed than in each of these cases you can conclude the existence of a new prime number which is not in the set. So you have to add it to the set. And this can be done over and over. The set can be extended _ad infinitum_ .
The proof is trivial and is left as an exercise to the reader.
1willFALL oh man, I remember these days lol!
blackpenredpen is this such a famous line for maths professors?
Metalhammer1993 I think so. Lol.
Also it happens a lot in textbooks too
The proof is so trivial I left it as an exercise to my dog :J He ate it all.
The margin is too narrow to contain the proof.
It's insane how much content you make. I love your videos I really learn a lot from them.
Thank you!
I think it's just simpler to say that q gives a remainder of 1 when divided by any prime p(i), i=1,2,...,n meaning that it's not divisible by any p(i) and is therefore prime itself
This made it click for me. Thank you!
me too! Thanks!
It's not that simple. How do you prove that you can't find at least 2 prime factors of P1*P2*P3*....Pn+1 between Pn and P1*P2*P3*....Pn ?
@@searchwikipediafallacy5567 I confused why did he add 1 in q=p1.p2…pn +1?
@@mathsoldier3413 Let us consider first prime number 2
2+1 is a prime 3
2*3+1 is a prime 7
2*3*5+1 is a prime 31
Now if u divide 31 by 2 u get remainder 1,
By 3 u get remainder 1
By 5 u get remainder 1
A number is a prime if it has only 2 factors 1 and itself.
If u want to test if n is a prime or not u will have to start diving at 2 and keep going until n-1;
Smarter way would be to stop at n/2
Even smarter would be square root n
Any composite number can be represented as a factor of multiple prime numbers. If a number can not be represented as a factor of prime numbers it would mean that number is also a prime number.
q can not be represented as a factor of all prime numbers available p1 to pn because when you divide by any p1 or p2 or pn you will get a remainder of 1. This means q is also a prime. That would mean pn was not the largest prime and that would mean there are infinite prime numbers.
What about p1*p2*p3*...pn+2? This is not a prime number because it would be divisible by 2 because p1=2.
alright I'd say..
the contradiction comes also from the fact that
in the definition of Q, division by pk gets remainder 1, and since pk divides Q (as it is one of his prime factors) it has also remainder zero, so this is in contradiction with the uniqueness of quotient and remainder in the algorithm of division :)
I love your videos. They are so intriguing and even make sense to someone who is only currently in Math II
I AM SO GLAD TO HEAR THAT!
I do try to make my videos as easy to understand as possible for everyone who likes math!
You forgot to write the +C
Giuseppe Cantore lollll!!
There are a lot of fun variants of Euclid's proof as outlined here. Here's a cute variant (which requires knowing already that 2,3 and at least one other number are prime): Suppose there were only finitely many primes; then we can set q as the product of all odd primes, so then q+1 and q-1 must both be powers of 2 (since they have no odd prime factors). But q+1-(q-1)=2 and the only powers of 2 which differ by 2 are 2 and 4, so q=3, but obviously q>3. Contradiction.
Here's a very different proof which is highly silly for being unnecessarily overpowered: consider the Riemann zeta function. zeta(2)=pi^2/6 and zeta(2) has the Euler product representation. If there were only finitely many primes then zeta(2) would be rational since there would be finitely many terms in the Euler product each of which is rational. But pi^2 is irrational and hence so is pi^2/6 which is a contradiction. This one is fun for requiring that pi^2 is irrational, that zeta(2)=pi^2/6, and that zeta has the Euler product representation. There may be more convoluted proofs of the infinitude of primes (the one using DFAs is also almost as bad) but I don't know them.
Damn man, talk about bringing a tactical nuke to a fistfight.
That's like proving all nths roots of 2 are irrational for n>2 using Fermat's Last Theorem.
My favorite thing about this is, without knowing there are more than 3 primes, this proves that there are either 3 primes or infinite primes. Quite the juxtaposition.
To anyone interested, a shorter way of putting it:
Because the lowest divisor greater than 1 of n!+1 must be a prime number and must be greater than n...
Explained very well for my UK A level maths :) Thank you
Tf?
This is in class 10th RD sharma (cbse curriculum) (india)
No wonder our exams our tough
At the end of these holidays in France, I will start the university, specialized in math and your videos are so cool man
All the things with the u world, the integrations, I've never seen that at school, your channel is full of wonderful tricks
Thanks
Clouck I am very happy to hear. Thanks!!
_Finally_ somebody explains why the product of all the primes plus one has a prime factor that's not part of that list of primes. When this proof is presented by people (and sometimes even books), it almost always lacks that explanation.
I don't think that the explanation presented in this video is the best one out there. It could be done more simpler.
An integer is divisible by another integer when the numerator (a.k.a. the dividend) is an exact integer multiple of the denominator (a.k.a. divisor). In other words, when the numerator has the same prime factors as the denominator, along with some other factors perhaps. For example:
21 is divisible by 3, because 3·7=21. Written as a fraction: 21/3 = 7·3/3 = 7.
The numerator (21) was a multiple of the denominator (3), because you can get seven `3`s and get `21`. When you divide them, you take away these threes, one after another, and see how many times that was possible, and if there's something left afterwards (something less than `7`, a remainder). But there isn't: `21/3 = 7·3/3 = 7`. It was possible to take away `3` seven times, and nothing was left. So the answer is `7`.
But if there's a remainder (e.g. when you divide `23` by `3`), then `3` does not fit exactly into `21`. Instead, you can take it away seven times (as before), but there's a remainder of `2` which is less than `3` and cannot be taken away. So `3` fits into `23` seven times and a bit. That bit is `2/3` (the remainder, which still remained to be divided by `3`, and it cannot). So we can write: `23 = 7·3 + 2`, which means that `3` goes into `23` seven times, and then you can only add `2` more.
Now back to the proof.
When you have a bunch of primes, and you multiply them together, you get a number, let's say `A = 2·3·5`. And this number is divisible by each of these primes, because if you put one of these primes in the denominator, it will cancel with the according prime in the numerator, leaving the product of the other primes as a result. E.g.:
2·3·5 / 3 = 2·5
But what happens when you add `1` to that product?
B = A + 1 = 2·3·5 + 1
This means that when you try to divide `B` by any of these primes, there will always be a remainder of `1` ! The prime only divides evenly into `A`, leaving the other primes as the quotient, and the `+1` as the remainder. No matter which of these primes you choose to divide `B` by, this remainder of `1` will always be there. This means that you _cannot_ divide `B` evenly by _any_ of these primes. The result will always be some fraction. (The integer part will be the quotient, and the fractional part will be the remainder divided by the divisor.)
_"This means that when you try to divide `B` by any of these primes, there will always be a remainder of `1` !"_
That's an assertion presented without proof. *Prove* that there is always a remainder of 1.
That's what this video shows, and what most often lacks in the "proof" when it's presented by most people.
What I wrote above was just the answer to the question "why", not the proof of it. I thought that was what you were asking about. But if you want proof, then Euclid's original proof contains it as its lemma. See also one of Sci Twi's comments here. She answered exactly that question by explaining how Euclid's lemma works.
OK here's how Euclid did it (rephrased a bit to make it standalone):
Suppose that `q` divides both `p` and `p+1`.
Then `q` would also have to divide `1`. (Because if something divides the sum and one of its parts, it also has to divide the other part. Do I have to prove this one for you as well? Or do you believe this is true?)
But this is impossible, because the unit is supposed to be indivisible (by any other integer except `1` itself).
So we have a contradiction, and our original assumption has to be false.
The other one is true: that `q` can divide either `p`, or `p+1`, but not both.
(Another way to see it is to notice that the smallest prime is `2`, so the minimum gap between two numbers that are both divisible by it, is `2`, not `1`. So if they're off by `1`, they cannot be both divisible by the same prime at the same time. If one of them is, the other cannot.)
I love your channel, keep up the good work!
michael nelhams thanks!!!!!
You are such a good teacher!!!
thanK YOU SM! my textbook was really bad at explaining this important proof
Loved ur content , lots of love from india ❤️
Cool... If you are open to ideas, it looks to me that those are some of the tradicional Internet proofs but also some of the most clean proofs (and somewhat not like most proofs iykwim) and there are a lot more and more profound proofs outhere... Just within the basics of number theory there are: the division algorithm, Bézout's identity, (which use the good ordered theorem). You could also try the Fundamental Theorem of Arithmetic, and from that the number of divisors of a number... Or proof that if p prime and p|ab then p|a or p|b (to show how to proof an or statement)... Just some ideas...
Very nice channel, btw.
Guille Heraldo S12 Valdeón
Thanks for the suggestion. I was in Berkeley these past weeks and just felt like I wanted to do some proofs, as of these were the first things that I learned in my student years. I may do more classic proofs later on if I can find some big blackboards. :)
How about Lindemann-Weierstrass Theorem? ;>
It might be quite useful, e.g. proving transcendence of `e` and `π` comes out of it for free :)
Make a proof for fun video explaining the infinitely many Pythagorean primitives! :D
Can someone please explain to me why we add a 1 to the product of all primes. Is it just there so that we get a fraction at the end or what purpose does it serve?
It's because if you have a number that is the product of all the prime numbers + 1, now it's not divisible by any of the prime numbers, so it must be a new prime number.
brianush1 (5*3)+1=16 not prime
5×3×2+1=31 prime
+Ali Mustafa 5*3 is not all primes up to 5. All prime numbers must be multiplied, or at least all prime numbers which you think exist.
you +1 because you 'can' this new number (like any number) must have a UNIQUE prime factorization, this is what Pk represents, being both a factor of Q and a number in the set of {P1-Pn}
wait so if you multiply all the prumes and add one, doesn't that make the new number a prime? seems like the proofs can stop there
Put then you have to prove that multiplying all prunes and adding one gives your a prune :) The proof provided is a formal proof.
Nope, not necessarily. Imagine your list of primes was {2, 3, 5, 7, 11, 13}, if you multiply these together and add 1 you get 30031, which is not prime, in fact 30031 = 59 * 509. The new number is not necessarily prime, but it must have prime factors that are not on the original list.
Mxlexrd - that's still not a proof, you'd have to prove your assertion to be able to use it in the formal proof.
I was responding to the original commenter, not to you, unfortunately youtube's comment system doesn't make it very clear who comments are directed at.
Not only that, but also some commends don't show up at all. They're visible only to the user who write them, and silently invisible to everyone else. It happens all the time to me. 99% of my comments here never show up.
Very clear explained . Thanks !
i have a question what if you can evenly divide 1 by one of the p's
So this is how induction was born?
The Saviour contradiction u mean. Hmmmm I am not sure. But this is def one of the oldest proof by contradiction
induction proof is different. contradiction is use as logic to prove a statement so it still a direct proof
@@blackpenredpen why are you able to add +1
nvm it is to show that Q is greater then the primes I suppose
What a lovely Proof that is!
Thank you!
Then take a look at Euclid's ORIGINAL proof ("Elements" Book IX, Proposition 20). You're gonna love it even more ;J
This video is so old he still used chalk and blackboard. Definitely filmed during 300 B.C.E.
great explanation, thanks!
This is the greatest video to ever exist
Lol, thanks! There are inf many others tho
Can you prove it? ( ͡° ͜ʖ ͡°)
Spencer Key "proof by example" just TH-cam search it! Lol 😆
Let's try proof by contradiction.
Suppose this is not the best video to ever exist.
Let's find an example of a better video...
Oh wait......
There seems to be a contradiction in my contradiction... :q
Umm... I found a brilliant proof of this theorem, but there was too few space in this comment to put it all ;>
Great!
Thanks
Where do you teach?
Please do #15 on the 2017 MIT integration bee qualifying exam,
lim n->infinity of I n where I1 = ∫ 1/1+sqrt (x, I2=∫ 1/1+(1/1+sqrt (x)), I3=∫ 1/1+(1+1/(1/1+sqrt (x))) ...
If the set of prime numbers is finite, then:
0 < product for all primes p of sin(pi/p) = product for all primes p of sin(pi*(1+2*(product for all primes p' of p'))/p) = 0
QED
(see the following image for the well written formula: gyazo.com/88fbcc88077cc96c7995dc5a374f67ea )
lectures by the real Euclid in ~300bc must have been cool as eff. infinite primes, irrational numbers and fun with triangles etc. :)
{P1, P2,...Pn} is a finite set thus has a highest element which is Pn
we can easily show that q < Pn (since it's multiplied etc..) thus q doesn't belong to {P1,P2...Pn}
How about using bezout's theorem to prove that gcd(q , Pk) = 1 ? yea its quite the same
Nice proof!
Thank you!
thank you so much ...fan of you :D
Elegant
"contradicition"
A bit laboured... but got there in the end.
A shorter way of putting it: The list of primes is endless because the lowest factor greater than 1 of p!+1 must be a prime number and must be greater than p.
This is not actually a 'proof by contradiction'.
That's good but i want you to to explain more.
Literally everything in this video was explained tho. What don't you understand?
Why is one not a prime? I remember the numberphile video, but it shows its more of a convention rather than an actual proof
GeekJokes mainly because it’s annoying. It makes prime factorization trivial - also, all numbers would have an infinite number of prime factors, that infinite number being infinite ones, so discounting one as prime just makes everything more ‘meaningful’. Of course, none of these are world-breaking problems - all can be solved with a bit of tweaking - but it’s annoying and the easier fix is “1 is not prime”.
@Patrik Wild In fact, that is how it used to be. One used to be a prime, but every single time you had to go "blah blah blah primes, except 1." It got old, and people thought "if we always have to exclude 1 nearly if not all the time, maybe 1 doesn't belong in this group" and so we altered the definition from "is divisible by only itself and 1" to "is divisible by exactly two factors, itself and 1" and made life simpler.
you are the MAN!!!
Why doesn't this work for q = [product] - 1?
It does
thank you so much bro
Nice proof, I haven't seen this one before :)
Thank you. Now you have and I am glad = )
finally ive found the channel
My pleasure!
what if we consider 1 as a prime number;(
SIR CAN YOU PLEASE CLARIFY THAT YOU SAID Q IS ( P1*....PN) +1 THEN HOW COME A FACTOR OF Q ALSO BE A FACTOR OF (P1...*PN) ?? PLEASE ANSWER
?
Great! It's easy to understand tho! btw, where are you from?
why do you need to add 1 to Q
"if q is not prime then it has a prime factor " , can you prove this?
This is an implication of the Fundamental Theorem of Arithmetic.
聽這個腔調 請問是台灣人嗎？
What if you contrast q as
q = p1p2...pn + 2
P1 = 2. Adding two means factoring 2. Therefore, this is not prime.
This also proof by priyanshu method
Why is there a necessity of adding "1", if I have "2" being added
Q = (p1*p2*p3*p4) + 2 , would it make this proof not work since I now have a '2' on the right side
---> = 2/pk , since pk can be '2' this would make the right side an integer, and since the left side of (Q-(p1*p2*p3*p4)) /pk is an integer
wouldn't this now make the equation hold true?
. . . Oh wait . . . Ohh I get it now since we are assuming that there are an " finite " number of primes, then an arbitrary equation like this must be true for all values of 'c' at the end of
Q = (p1*p2*p3*p4) + c
I wonder how this proof would work if '1' was considered a prime number, I guess it wouldn't work maybe . . .
Wait so hold on so if ' 1 ' was considered a prime number then we could use a constant lower than the value of 1 such as 1/2, for instance:
Q = (p1*p2*p3*p4) + 1/2
And then we would run into the same contradiction again
Thus, proving that the arbitrary equation does NOT satisfy ' all ' values of 'c' to hold true for the equation
Thus there must be an infinite amount of primes because when you assume that there aren't , "this equation derived from assuming so", would never would never hold true for all values of c
~ Any feedback?
you missed one essential thing, any number achieved by multiplication of prime numbers will be even, so if you add 2 instead of 1 the number will never be a prime since you just introduced a 3rd factor to it (itself, 1 and now also 2, since it's even)
and 1 is not a prime by convention afaik, to make it easier (not really sure on the origins of that, so look it up if you are keen enough)
Many months late, but I thought I would respond.
Including a "+c" at the end would be problematic, since Q could then possibly be divisible by one of the primes in your list. As you point out, if one of the primes in your list is 2, then taking (p1*p2*p3*p4)+2, for instance, _would_ be divisible by 2. So we no longer have a contradiction.
If 1 were considered a prime, the proof would still work, but you would just have to say more words about why 1 isn't an issue. This is the benefit of excluding 1 from the list of primes - it allows us to simplify arguments and statements.
And you cannot allow c to be a non-integer. The Fundamental Theorem of Arithmetic only applies to integers. If you had c = 1/2, then Q would no longer be an integer, so you couldn't conclude that it would have to be divisible by some prime.
what is his name ?
John Cena
Awful explanation of an otherwise elegant proof
I knew your proof will be bad (I already expected it being done by contradiction, as most people nowadays do it), but I didn't expected it to be _that_ bad! :( Where should I start?... Let's start from the usual misconception about the "contradiction".
Euclid's original proof was _not_ by contradiction at all! And you would know that if you looked into the actual "Elements" by Euclid (Book IX, Prop. 20), e.g. the English translation by Heath, or that on David Joyce's website. He pretty much said:
"Give me your set of prime numbers, and I'll show you how to find a prime number which is not in your set."
(And since this can be done as many times as you please, it must mean that "there's more of prime numbers than any assigned multitude of prime numbers", quoting Euclid.)
It is a common misconception repeated over and over by modern mathematicians who distorted Euclid's original proof by sandwiching it into a proof by contradiction. There are several mathematical papers explaining that in depth, such as "Prime Simplicity" by Hardy and Woodgold (2009) with an excessive list of references to literature with examples of distorted versions of the proof, or their later paper "Three Thoughts on Prime Simplicity" (2012), or Siegmund-Schutlze's work "Euclid's proof of the infinitude of primes: distorted, clarified, made obsolete, and confirmed in modern mathematics" (2014), with very nice and logical breakdown of Euclid's original proof and comparison to modern versions.
As Timothy Gowers wrote on his blog post "When is a proof by contradiction necessary?":
| _This is a question that arises when I am teaching somebody who comes up with a proof like this._
| _“Suppose that the sequence `(aₙ)` is not convergent._
| _Then … a few lines of calculation … which implies that `aₙ → a`._
| _Contradiction.”_
| _They are sometimes quite surprised when you point out that the first and last lines of this proof can be crossed out._
It is less funny when you find most of the modern versions of classic proofs to look like this, or when you find a lengthy proof of some complicated statement which has been unnecessarily made into a proof by contradiction :P That's why some famous mathematicians started to be dubious about proofs by contradiction recently, and they try to figure out when is a proof by contradiction unavoidable, and when it can actually be avoided and replaced by a direct proof.
The next bad thing in your proof is that you said that the primorial plus one cannot be a prime.
Sure, I understand that it is true _if_ you assume that your set already contained all the primes there are, and `q` is definitely not in that set, so it cannot be a "prime" (according to this definition, based on belonging to a certain set).
But this way of proving it is directing your viewers' train of thoughts into very wrong tracks! Because they may be tempted to think that this number can _never_ be a prime, which is simply not true! There _are_ primes of the form `p₁·p₂·p₃·…·pₙ + 1`, the simplest one being `2·3 + 1 = 7`. If you assume that `2` and `3` are "all primes there are", and Euclid's trick shows you that their product plus one is `7`, then according to your definition, `7` cannot be prime, which is false, because it's enough to try to divide it through all the numbers from `1` to `7` to find out that it has only two factors: one and itself, which makes it a prime too (according to the _right_ definition of what a prime number is).
Telling the students that the primorial plus one is always a prime is no better, though, because the student might get a wrong impression that this is a way to construct a number that is _always_ prime. And when they check some of the first simplest examples, they find out that this is the case, which convinces them even more into believing that this is the case. E.g. `2+1=3, 2·3+1=7, 2·3·7+1=43` ... But a simple counter-example can tell us that it isn't: `2·3·7·43=1807=13·139`.
Your proof is also overly complicated (not to say obfuscated :q ). Much more complicated than the original Euclid's proof which can be contained in a couple of lines. (Look at the original proof and you'll see what I mean.)
That's why Euclid didn't do it that way, and didn't make any of these assumptions:
a) He didn't assume that the "any assigned multitude of prime numbers" (basically a set) is _exhaustive_ (i.e. that it contains _all_ prime numbers). He just assumed that it is _some_ finite set of prime numbers.
b) He didn't assume that this set is continuous (i.e. that you didn't miss any of the primes).
c) He didn't even use a product of primes! Instead, he took "the least number DE measured by A, B, and C" (so basically the least common multiple of those primes).
d) He didn't claim that this number plus one is a prime, or that it isn't - instead, he said that it could _either_ be a prime number _or_ a composite number (since course there are only these two possibilities to consider), and showed than in each of these cases you can conclude the existence of a new prime number which is not in the set. So you have to add it to the set. And this can be done over and over. The set can be extended _ad infinitum_ .
You should use your time to make math videos.
Explendit proof sir...❤❤