Euclid's proof that there are infinitely many primes! Classic math proof! 

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.

Thank you!

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.

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!

Giuseppe Cantore lollll!!

michael nelhams thanks!!!!!

Clouck I am very happy to hear. Thanks!!

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...

Tf? This is in class 10th RD sharma (cbse curriculum) (india) No wonder our exams our tough

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 :)

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.)

Thanks

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}

Thank you!

Thank you!

Then take a look at Euclid's ORIGINAL proof ("Elements" Book IX, Proposition 20). You're gonna love it even more ;J

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.

Lol, thanks! There are inf many others tho

Can you prove it? ( ͡° ͜ʖ ͡°)

Spencer Key "proof by example" just RU-vid 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 ;>

Literally everything in this video was explained tho. What don't you understand?

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

It does

My pleasure!

?

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.

P1 = 2. Adding two means factoring 2. Therefore, this is not prime.

This is an implication of the Fundamental Theorem of Arithmetic.

Thank you. Now you have and I am glad = )

John Cena

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.

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.