Proof: There are infinitely many primes numbers
ฝัง
- เผยแพร่เมื่อ 28 ส.ค. 2024
- We use proof by contradiction to prove the wonderful fact that there are infinitely many primes.
►Full DISCRETE MATH Course Playlist: • Discrete Math (Full Co...
*********************************************************
Other Course Playlists:
►CALCULUS I: • Calculus I (Limits, De...
►CALCULUS II: • Calculus II (Integrati...
►CALCULUS III (multivariable): • Calculus III: Multivar...
►DIFFERENTIAL EQUATIONS: • Laplace Transforms and...
►LINEAR ALGEBRA: • Linear Algebra (Full C...
► Want to learn math effectively? Check out my "Learning Math" Series: • 5 Tips To Make Math Pr...
►Want some cool math? Check out my "Cool Math" Series: • Cool Math Series
*****************************************************
YOUR TURN! Learning math requires more than just watching math videos, so make sure you reflect, ask questions, and do lots of practice problems!
****************************************************
►Follow me on Twitter: / treforbazett
BECOME A MEMBER:
►Join: / @drtrefor
MATH BOOKS & MERCH I LOVE:
► My Amazon Affiliate Shop: www.amazon.com...
Hands down the best explanation. I like how you defend every step. Everyone seems to just gloss over the factorization. Showing that there's a fraction, if you only use the numbers on the list, means you are missing a prime factor(s). Love it. This proof has always felt unsettled in my mind.
Dr. Bazett: I spent an entire day looking at this problem and always got stuck on the "remainder" issue, where it is just thrown out that dividing p by some prime results in remainder. Out of many dozens of articles and videos I've looked at you are the first one to actually explain this. I actually came close to your explanation at some point, but was incredibly perturbed that no other article backed up my intuition (and yours) about the resultant fractional component when dividing p by some prime. In other words, this was a valid observation, but I didn't know if this actually factored into Euclid's proof, or if it was something else that completed Euclid's proof. I was an engineering student at school and have started on a long road to re-learn stuff so I can learn more stuff. I immediately subscribed to your channel. Kudos.
The same thing happened to me! I was watching another video before this and while it was quite well-made and to the point, they didn't proof that p was indeed a prime number. I figured that seemed like the case but I had to come watch this video to see it for myself!!
Same
best explanation ever.
Best video on this topic hands down, brilliant explicit showcase of this. Thank you kindly
The remainder concept that you explained has really sunk in my mind. Thank You So Much
Best explanation on youtube, thank you!
good job!! your videos are extremely helpful! please carry on with your work!
Amazing explanation! It’s cool how you write in reverse on the mirror.
He writes normally and then the video is flipped.
@@MrConverse That's makes a lot more sense, thanks =)
What I love about this proof is it is simple, ancient and completely ignores the practicality of calculating p1...pn + 1 and of checking its divisability.
I think from step 3 we can conclude that p is a prime because it is not divisible by any and all existing primes, p1, p2, …, pn. We end up with an immediate contradiction because we assumed that the largest prime is pn but p > pn.
Who would've thought that garble nonsense could be so elegant! I would love to see you explain through contradiction that the square root of 2 is an irrational number :)
Can you please do a cool maths series!!???? Or is this already a thing???
That’s relatively straightforward as well. Assume that (sqrt 2) is equal to a reduced rational fraction of the form (m/n). Squaring both sides, we get that 2 = m^2/n^2. Cross multiplying gives us 2n^2 = m^2. Since the left hand side is obviously an even positive number, m^2 must be positive and even as well, so m must also be positive and even. So let m = 2c, where c is any positive integer. Now we can see that m^2 is equal to 4c^2 and also equal to 2n^2 from earlier, so 4c^2 = 2n^2, and n^2 = 2c^2. So n^2 is even, and therefore so is n.
But if m and n are both even, that means they have a common factor of 2, which contradicts the statement that the beginning fraction of m/n was in reduced form. Therefore, such a fraction m/n cannot exist, so the square root of 2 cannot be expressed as a rational fraction.
THANK YOU ONE HOUR BEFORE MY FINALS IT FINALLY MAKES SENSE!!!!!!!!!!!!!
Explanation was quite short and accurate...best indeed
THIS IS A WONDERFUL EXPLANATION, THANK YOU SO MUCH
]
What a beautiful explanation! Thank you!
Why can't we have a teacher like him in our schools....😭😭
because he's in the computer
This is the only video i found on TH-cam that explains this proof clearly. I was so confused before i watched this.
Where does the +1 come from
im only 1 minute into the video and i understand it
thank you!!!!
Superb best explanation!!
thanks for it
You are my favorite youtube math teacher
Awesome explanation thanks
Superb Explanation!
Wow! One of the best explanations I've ever seen
I honestly don't get why this is a proof by contradiction. Why do we suppose that there are finitely many primes? I see no reason that I have to assert that only finitely many primes exist in order to consider finitely many primes and make the same conclusions.
Hey, I’ve seen a few of your vids before and enjoyed them, nice job! It’s true that it is commonly written both ways, although I’ll note that Euclid himself didn’t frame it as a proof by contradiction so probably better not to even ignoring aesthetics. I’m not sure I have strong feelings one way or the other, perhaps it is common because pedagogically it is nice to see something ~deep~ right after one learns about the concept of proof by contradiction.
@@DrTrefor Hey, thank you! Lightboard crew 👍
Admittedly, I haven't looked at Euclid's original proof, which might address my concerns. I don't really have an issue with proofs by contradiction, and I'm not saying that it would be preferable to prove this directly with a different proof rather than a proof by contradiction. I just find that in this particular case, it almost reads like it's already a direct proof as written, just "wrapped" in a proof by contradiction heading and footer, if that makes sense.
It's like it's saying: Assume the set P of all primes is finite. But, we can show that this finite set is necessarily missing a prime. Therefore P does not contain all primes, which is a contradiction. Therefore the set P is not finite.
If we are able to argue that an arbitrary finite set is necessarily missing a prime, it seems like we're already done. But maybe I'm taking a leap that I'm not noticing here.
Sadly, it’s been some years since I’ve had access to a lightboard, so I’m stuck with a greenscreen which is nowhere near as awesome:/ But ya, I don’t disagree at all, it is sort of an unnecessary framing isn’t it.
@@DrTrefor Do you think it's effectively the same as a Cantor diagonalization argument here? They seem to be identical arguments when we look at it that way.
"For any finite list of primes, here's a prime not on the list. So, the cardinality of the prime numbers is strictly larger than the cardinality of any finite set."
"For any ordered list of real numbers, here's a real number not on the list. So the cardinality of the real numbers is strictly larger than the cardinality of the natural numbers."
I was so confused after watching the same proof on the numberphile channel! seeing this video makes the proof so clear!
1:05 that theorem is called the fundamental theorem of arithmetic.....
excellent explanation. thanks much!
Thank you. Best explanation.
Still wonder why he added the 1 in the end, anybody can explain? Please
Wow, you made the proof easy. Thanks. Could someone highlight the rationale being us adding 1? Because of course that makes the number p indivisible by any primes. And I am also still wondering how it becomes composite given that it is not perfectly a product of primes.
Thanks
Dayuuuum. This is a great video. Thanks for creating it. :)
I believe that there is a case missing here which is that it is composite, but is composed of some primes which are not in the original set that you assumed was all the primes.
A small correction to the explanation.
The assumption that P is a prime is wrong!
It is either Prime or that it is a composite that is divisible by other primes not in our finite group.
For example : 2*3*5*7*11*13 +1=30031
This number is not prime as it is equal to 59*509=30031 !
Another example (simpler)
2*7+1 =15 which is of course not prime and divisible by both 3 and 5 , primes not in our group.
Those remarks don’t change our proof as we added new prime/primes to our finite group , which contradicts our assumptions and proof that the group is infinite .
Very good explanation ❤️
thanks alot 💕 lots of love
Most welcome 😊
Another method. You can assume every natural number n > 1 is divisible by some prime number q, where q > 1. Let n =(P1*P2*P3 -- * Pk) + 1. Both n and (P1*P2*P3 --- *Pk) are divisible by q. Their difference is also divisible by q, which implies q = 1 (contradiction).
This is same method
@@youssefdirani It's not the same, look at the contradiction in each case.
So does that mean the product of consecutive primes from 2 to P is always another prime?
if you add one, yes.
@@DrTrefor Oops yeah thats what I meant
@@DrTrefor actually I thought you were right until I saw the next comment of W and the subcomment which gave a counter example. Hope you check
@@DrTrefor no sir
No be careful. Im still a beginner myself but this is not what this proof states. For example take the first 6 prime: 2*3*5*7*11*13=30030+1=30031. This is not divisible by any prime that came before it. But if said our pn was 6 then pn+1 should be a prime right? Not exactly, 30031 divides by 59 and 509. Which are in fact 2 primes but they are primes bigger than the pn+1. So what this shows is that pn+1 will be a factor of primes or possibly even a prime by itself from what ive read. What he shows in the video is that for a product of primes up to an arbitrary pn+1 it does not divide by the previous primes. So with respect to p he chose yes it is "prime" but if you continue along you find that 30031 is in fact composite, essentially its a never ending loop.
excellent!!!!!!!!!!!!!!!!!!
Why is 1 added the end of the list? What is the rationale for this?
Thanks,
Mark
thankyou dear professor 😍
Why we use the formula of P=P1P2P3....Pn+1? Can someone explain this?
Trefor Bazett - While in your proof by contradiction, it works to say that p1*p2*...*pn+1 is prime, I think it might be better to say that this number is not divisible by any primes on the list. Then, the contradiction is that p must be divisible by at least one prime on the list but is also not divisible by any prime on the list.
The reason I would make this distinction is because of questions I've seen from this approach before.
Sometimes people will do their own computations to get some intuition for the proof. But here's the rub.
It doesn't take too much work to find this example: 2*3*5*7*11*13+1 = 30031 = 59*509. Seeing that 2*3*5*7*11*13+1 is not prime, but your argument relies on numbers like this being prime, people begin to doubt the argument, thinking that you must have made a subtle error in your reasoning.
There is indeed something subtle happening in the argument when concluding that p is prime, but it's not an error! The conclusion that p is prime relies on the assumption that p1, ..., pn is a _complete_ list of primes, not just _any_ list of primes. This sort of thing is easy to miss when being introduced to a proof by contradiction.
Let me correct you , as in your example above it was supposed to be a full set of all the primes up to the last one, and not a subset , but the primes 59 and 509 are bigger than the biggest known prime and hence they are enlarging the group
this is a really good explanation!
Also, this proofs that any product of primes in order plus one is another prime
It actually doesnt. One counter example is 2*3*5*7*11*13+1. It equals 30031 and is divisible by 59 so its composite. Reason this doesnt prove that is we assume there exist no primes between 13 and 2*3*5*7*11*13+1, which in most cases isnt true.
@Dr Trefor Bazett here is an interesting answer
That's not actually true. 2*3*5*7*11*13 + 1 is composite.
just curious -- since all the p's are prime, is it possible that p could be advisable by an even number? How can you assume that there is not another factor from the composite p? thanks
p1 can be assumed the number 2, so no, p cannot be divisible by 2 hence by an even number
P could be a prime number, but it could also be a composite divisible by a prime larger than p sub n. A better proof would be to go to the start with P on one side and the product of all primers plus one on the other side. Then subtract one from both sides. Now divide both sides by any one of the known primes. Here we have some integer on the right equal to some mixed fraction on the left which is a contradiction. QED
Why p=p1p2...p3 + 1? What is the purpose of adding 1?
To make something that is prime, as otherwise p would be composite.
Dr. Bazett's answer is absolutely correct; I am not in any way discrediting it. I just want to provide some interesting additional context that I have from teaching number theory a few times.
I like to break things down to a specific lemma:
Suppose m, n, and k are integers, and suppose k divides m. Then k divides n if and only if k divides m+n.
The proof, I think, is doable as an exercise! (It's pretty much an exercise in the distributive property/factoring and the definition of divisibility.)
Now, the goal of the proof that there are infinitely many primes is to cook up something that isn't divisible by any of our finitely many primes. How can we do that? Well, from this lemma, we can find an "m" which is divisible by every one of our primes, and an "n" which isn't divisible by any of our primes. Then the lemma tells us that m+n won't be divisible by any of our primes. What's one way to cook up a number which is divisible by all of our primes? Multiply them all together! And what's a number that isn't divisible by any prime? There's only one such positive number: 1 itself. This explains where p=p1p2...p3+1 comes from.
But you can also use this lemma for pretty much the opposite purpose too! One of the (imo) hardest problems I assigned to my number theory students was the following:
For every positive integer c, prove that there exists a sequence of c consecutive positive integers which are all composite. As an example, for c = 3, the sequence 8, 9, 10 consists of 3 consecutive positive integers which are all composite.
Again, the hint for solving this is to use the lemma I mentioned above. Think about ways that you could cook up a bunch of m and n's to get the corresponding m+n's to be a sequence of composite consecutive positive integers. Also think about how p=p1p2...p3+1 in the proof that there are infinitely many primes and how that might relate here.
Even with this hint, I think it's a tough problem! But I think it's also really rewarding to work hard on this problem :)
When there are infinite prime numbers, the question is: Is the infinite prime number grouping smaller or the same size as all other (or even all) numbers? Or does this just depend on your definition of "infinite information"?
Also how big is the infinite prime group in comparison to the other one? Because interestingly the higher you count, the fewer primes you find. My point is the closer you reach infinity the smaller the prime group percentage gets in comparison to all numbers and then the percentage almost hits zero,but as soon as you hit infinite, you got infinite primes and infinite normal number?
Or do we have two infinities inside each other but one has the limes of reaching almost zero percent of the other one?
That's the most intriguing thing in my opinion.
But maybe "you cannot hit" infinity that ezly.
Yoo, let us just say that both are infinite, but the prime group has an infinity with "lots of blank spaces" in it's matrix framework (everywhere where no prime number is). Ok nice.
Sir please do videos about zeta functions and properties
where does the plus one come from
It's so that the resulting number cannot be divisible by any of the primes in question.
This guy is good
How should we reference this video, Dr?
just a link!
I don't understand why p not divisible by any of the primes implies that p must be prime. All we get is that it's divisible by some prime q not among p_1, ..., p_n. But why does that prime factor q have to be p? I have never understood this claim.
I much prefer your method of proving this (and have for a while). It's just cleaner.
A lot of people like the "Every integer greater than 1 is either prime or divisible by a prime" approach to saying things, for some reason, even though "Every integer greater than 1 is divisible by a prime" would suffice. I think it stems back to how people tend to think of factorizations as having at least two factors (shunning unary products), so they feel they need to word Fundamental Theorem of Arithmetic as integers greater than 1 either being prime or having a prime factorization.
From this perspective, if an integer greater than 1 isn't divisible by any primes, then since we have the disjunction "is prime or is divisible by a prime", the other part of the disjunction (is prime) must be true.
Sir plz teach us more
How don we get step 4 that p is a composite? I know p1p2…pn is a composite, so are you saying a composite plus 1 is a composite? I don’t get it.
I so love your videos.
@6:25 P is not evenly divisible by any of the p sub n prime numbers. Yes. That does not imply that P is a prime number. It could also be a composite that is divisible by a prime larger than p sub n. For example, take 2*3*5*7*11*13+1. That is not a prime number, it is divisible by 59, a number larger than p sub n, or in this case 13.
Gold as always😍
Thank you so much sir😇😇
You didn't prove that P2...Pn+1 is not divisible by P1
For example, if the largest prime was 5 then you would have 2x3x5+1 on top of your equation
Divide by (in this case 2) so you get 3x5+1 on top of our fraction and your P1=2
3x6+1=16 which IS divisible by 2 (your P1)
It was awesome 😁👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍🏻👍🏻👍🏻👍🏻👍🏻👍🏻👍🏻👍🏻👍🏻👍🏻👍🏻🤘🤘🤘🤘🤘🤘🤘🤘🤘
Simply genius...
I remember in my first year of uni i took a discrete maths class and we had to prove this in our final exam. My proof definitely made no sense lol
can someone explain why we have to plus one to p?
Legendary!
Amazing🎉🎉🎉🎉❤ sir❤
Impressive 😍😍😍
Instant subscription
I have this question:
Prove that there are infinitely many primes of the form 4n+3.
(I hasn't found any satisfactory ans)
Thank you.
Thanks
There is double negative in sentence: "c is composite if it is an integer > 1 that is not not prime"
What I don’t understand is why the same argument doesn’t work if you subtract 1. You still wind up with a fraction
Yes, the same argument does work.
None of p1,...,pn is the factor of p does not imply that p is a prime. There may be another prime q such that q|p.
This is true...but that’s the crux of the proof. What we are saying is that if p is prime, we’ve found another prime to add to our list from p1 to pn. If p is NOT prime, then there must be another prime q on the list somewhere between pn and p. Either way, the list of primes from p1 to pn cannot be a complete list. No matter how many primes we start with from p1 to pn, we can always show that the list is incomplete. Since this can be done regardless of the size of the initial prime list, the list must be infinitely long.
thank you
thanks
Why add 1?
Love from indiaaa❤
don't you have to divide both sides of the equation?
Even if u do the answer will be the same because we have another theorem which is: If p divides a², then p divides a. And in this problem, p doesn't divides a therefore p won't divide a² nor will p² do.
Hope your understand
wow, thank you
Great man it is was cool!
Thankyou!!!!
Hmm can't we use the same proof for Mersenne primes? Why doesn't it work for them?
Because that multiplication plus one isn’t of the form of a mersenne prime
@@DrTrefor Fair enough 😂
beautiful champ
Nice
At 5:00 you divide “p1p2…pn +1” by p1.
The p1 cancels giving “p2…pn and a remainder of 1/p1.”
I’m confused by the algebra. When the p1 below is used to cancel the p1 above, they both change to 1, correct?
So, how is p1 below then available to divide into the 1 above?
(If I have “abc+1/a” and a cancels a, isn’t the result “bc+1”?)
Also, if p is the product of the primes (p1p2pn), it’s clearly a composite, according to the theorem at 1:00. But when you add 1, it doesn’t make sense defining it as a composite.
This is how I see it, with P, Q, and R, easier for me.
Assume a finite list P of any primes called p1, p2, p3, and p4.
e.g. 2, 3, 5, and 7.
Let Q be the product of those primes: (p1)(p2)(p3)(p4).
e.g. 210.
Being a product of prime numbers, Q is a composite number.
Q is greater than the primes in P.
Let R be the sum of Q + 1.
e.g. 211
R cannot be a composite because it’s only one more than Q.
Therefore, R is a prime number.
Since R is greater than the primes in P, it cannot be in P, so it’s a new prime number.
So there are infinitely many primes.
Thanks. I appreciate your explanations, but I struggle with algebra.
In other words, because there is a plus sign, the Distributive Property is used (p1 is applied to each part).
“p1p2…pn” is divided by p1.
“1” is divided by p1.
@@georgeseese You can think of it as ((p1p2....pn) + 1) / p1, each part will be divided hence why there is a remainder of 1 / pi for any p that you choose
thanks!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Is he doing mirror writing??
Probably reversed the image
why are we adding 1 to the P's
Munyaradzi Piki By doing so, you're generating a number N that is guaranteed not to be evenly divisible by any of the primes on your finite list. If this new number N is indeed composite, you should be able to factor it into a product of distinct primes that are on your list. However, you won't be able to because you'll always get that remainder of 1 when you divide N by any of them. This means either that N is still composite and has prime factors not on our finite list, or that N is prime itself. Either way, we have found a new prime or primes that were not on our finite list. So basically, no matter how many primes you are given on your initial finite list, you can always show that there must be another prime that is not on the list. Therefore, there are infinitely many primes.
Ravindra Deshmukh Thanks! It may sound a little counterintuitive at first, but sometimes that's what proof by contradiction does...it forces you to think outside the box!
This video is too long. All you need to say is that because the lowest factor greater than 1 of p!+1 must be a prime number and must be greater than p, the list of primes has no limit.
must be a prime number and must be greater than n, the list of primes is endless.
hehe you said 'my pee is prime'
thanx for the effort but i didnt understand it though
Here is another explanation. Hope u are able to understand it form here. th-cam.com/video/h1Nu4TaEEjM/w-d-xo.html&t=
orrr just use bertrands postulate
What a clear way of explaining!
i get it now 🎉
Kung Fu Tutorials: Twin Primes Rules 2021 By Kung Fu
th-cam.com/video/RRScLdkQrlw/w-d-xo.html
fucking incredible
why do we need to add 1 in the first place
If we didn't, the number certainly wouldn't be prime as it would be divisible by any of the primes like p1
@@DrTrefor but if you add 1 is also not prime like 3x5+1=16
@@khanjra Was thinking the same question until seeing your comment. I ignored 2. So now with 2, basically every multiple would be even and with +1, it must be odd. Thanks.
@@faizahbegum5257 A product of some primes +1 doesn't need to be a prime, but if it's not, it must be divisible by some prime not in the list. So 3*5+1 is not divisible by either 3 or 5, proving that {3,5} are not all primes that exist. (It happens to be divisible by the prime number 2.)
@@MikeRosoftJH thanks soo much
I have a proof that I came up with and I’d like to ask if it would work:
Assume there are finite prime number of prime numbers
Since all composite number r product of prime numbers, there must only be finite number of composite numbers
Since prime number and composite numbers r mutually exclusive, we can add them up and 1 and we would have the entire positive integers
Since both prime and composite are finite,
The entire positive integer is finite, which is a contradiction
So prime is not finite.
Plz let me know if this proof works as well :)
Why on Earth should it work? 2 is a prime. 2*2 is composite. 2*2*2 is composite. 2*2*2*2 is composite. And so on - there obviously are infinitely many composite numbers, and that follows from the fact that there exists at least one prime number. (In fact, 2, multiplied by any integer greater than 1, is composite.)
dr. cooked here
Please sir speak Hindi because u am indian
There are infinite number of primes, but your proof is flawed.