It reminds me of something Ricky Gervais said about science books. 'You could destroy all science and math text books and in 1000 years they'd all be back with the exact same information in because all the same tests would generate all the same results, if you did this with the bible or any other religious text then it would simply be gone'
@@nekogod not science books, science (aka natural philosophy) has been around for around 2000 years we would be pretty stuck if all the books popped out of existence mathematics though, we would rebound much quicker than science, and we would fix mistakes people made along the way (complex numbers turned into compound numbers, using a base 12 system for arithmatic)
@@toastyarmor6858 Science books would be back eventually, though they may look different and the units might be different. The speed of light would remain the same, the number of particles in a hydrogen atom would remain the same, gravity would be the same etc. I'm not saying the exact books would be back and be identical, rather that the information contained is not defined by itself. Destroying the books doesn't destroy the information it still exists to be found again, this is not true of most other things.
@@nekogod thats not true though, maybe maths yes but science evolves and new discoveries would almost garuntee some things we have today in our books will not be there in 2000 years. Secondly, there is a religous scripture which millions have memorised down to the letter in full, I challenge you to know what it is ?
@@greenprofile5755 I will concede that some things will be different as we may have better theories for some things. But the bulk would be the same things like the speed of light in a vacuum, the gravitational constant etc. By destroy all books etc I meant destroy all knowledge if all religious books were destroyed and everyone who memorised them refused to pass on that knowledge it would be permanently lost. This is not true of maths at all and is almost completely not true for science either
@@siquod no, not really. it's usually done so it stays somewhat relevant to what makes sense in our reality but mathematics can also deal with completely unrealistic things and axioms, as long as they don't contradict each other. logic is not dependent on reality
I have a question: Suppose the only primes are 2,3,5,7,11,13 and 17. And I want to construct a number Q by multiplying all of them together, and then adding 1. 2 x 3 x 5 x 7 x 11 x 13 x 17 = 510,510 +1 = 510,511 which is not a prime. So... what gives? Who's to say Q in your proof isn't like 510,511? edit: did some thinking and 510,511 is factored by 19, 97, and 277, none of those being on the list. therefore the list was not complete. Well played mathematics... you win again.
You supposed 2,3,...,17 are the only primes, so, if that is true (and you're assuming it is) Q, which is the product of all the primes + 1, IS a prime number. But you said numbers 2,3,...,17 are the only primes, so you just contradicted yourself. That means 2,3,...,17 aren't the only primes. This is a proof by contradiction.
Yeah, the thing is that Q is not necessary a prime, but instead a coprime of all the others. In other words, the proof just states that there is not any prime of your finite list that divides Q, so either there exists a larger prime that divides Q or Q is a prime itself.
You don’t even need your list to be the first n primes. And you don’t even need to assume your list is complete for the proof to work. The proof is just that if you have any finite list of primes, you can show (by taking their product and adding one) that there’s other primes that weren’t in your list. If any finite list is incomplete then there must be infinitely many. Eg if you take the list 3, 5 and 7, you multiply them together and get 105. Add one and you get 106. Since 106 isn’t divisible by 3, 5 or 7 either it’s prime (obviously it’s not) or its prime factors weren’t on your list.
What puzzled me for ages about Euclid’s proof was what Grimes says at 1:43 and, especially, at 2:09. What I didn’t at the time realize was that proof calls on another famous piece of maths, the _Fundamental Theorem of Arithmetic,_ from which we can be confident that every integer greater than 1 is either prime, or is the product of primes where that product is unique. It’s part of the beauty of maths that I was able to be impressed at Euclid’s proof without knowing (or even knowing _about)_ the _Fundamental Theorem of Arithmetic._ But still, it niggled me, and eventually when I learned about it I was even more impressed. 🙂
I have been struggling with this for days, thank you so much! Every definition I read kept stating, “Q must be prime or the product of primes”, which left me wondering why it couldn’t be a product of non-primes larger than Pn
I never saw Euclid's proof using geometry. I came up with mine. Neither algebra nor arithmetic is needed. Suppose distinct segment lengths A, B, and C that can’t be divided into lengths of whole numbers other than the unit segment. Suppose that lines can be a multiple of segments A, B and/or C units only. Consider such a line XY X --------------------------- Y It can be divided in segments A as follows X --|--|--|--|--|--|--|--|--|-- Y It can be divided in segments B as follows X ---|---|---|---|---|---|--- Y It can be divided in segments C as follows X -----|------|------|----- Y Next, extend the length of the line all the way to Z X -----|------|------|----- Y------------------------------------------------------------------------------Z Since the assumption is that lines can be a multiple of segments A, B and/or C units only, so too is line XZ. This restricts the possible lengths that XZ can take. To see how, suppose I extend the line XZ by one unit U: X -----|------|------|----- Y------------------------------------------------------------------------------Z-| U Since this is the unit, it can’t be divided into lengths A, B or C. Therefore, line XZU can’t be divided into segments A, B or C. The length XZU constitutes a multiple of a new prime number. This argument applies all the way to infinity. Note that it can't be determined what that prime number is.
@@jeancorriveau8686 one of the opening suppositions of your "proof" is, _"that lines can be a multiple of segments A, B and/or C units only"._ However, towards the end it says that, _"line XZU can't be divided into segments A, B, or C"._ Isn't that a contradiction?
@@jeancorriveau8686, ah, I see. You were deploying proof by contradiction; fair enough. But then exactly what have you proven? Isn't it simply that the proposition, _"Lines can be a multiple of segments A, B and/or C units only"_ is false? It doesn't seem immediately obvious that that is equivalent to the proposition that there is an infinity of primes.
Seeing the passion you guys have for numbers and mathematics is inspiring. It shows me that what is mundane to you could be incredibly meaningful to me, and that no intellectual pursuit is without value. I don't have the same passion for numbers, but I do have passion for other things, and the fun and knowledge I gain by watching these encourages me to go and exercise my own talents and intellect. I am grateful for that.
Thank you for pointing that out to me. I guess I hadn't thought about the fact that since the list is by definition incomplete, it doesn't have to be the set of all prime numbers within a given range, just that the answer will never be divisible by any number in the series. If you leave 2 out of the series, your product will be divisible by 2 (and not any of the numbers in your series), proving that you have an incomplete list. Makes sense now.
At 5:15, when the book of Euclid's Elements is shown (his definition of a prime), I spotted a spelling error in the book. "A unit" is the correct spelling, versus the incorrect "an unit" one in the book. Nothing important really, in context of the subject, just saying... :)
I was doing some math and found that (2n)+(n^2)-1 created primes very well if n is even. Example: (2 x 99922222222220)+(99922222222220^2)-1 is prime. I also saw that up to 200 being n (leaving out odd numbers) it spit out a prime 42% of the time.
Sampling a random number from 0 to 200 that isnt even gives you a probability of around 43% to hit a prime. Thats better than your formula if we are looking at a injective functions that gives you primes. For numbers from 1E12 to 1E14 (sampled) your formula hits a prime around 5.6% of the time. The prime number theorem tells us there is a 6.34% probability with random sampling on non-even numbers. In fact, your formula of 2(2n)+((2n)**2)-1 is pretty much always worse than 2n+1 if we are only looking at the probability of getting a prime on input. Your formula however has the advantage of outputting way bigger numbers. If we adjust for the asymptotic quadratic growth of your formula then your formula is around 2.5% better from 1E12 to 1E14 but this will slowly but surely go to 0% as n grows.
@@hypnogri5457I’m going to be honest, I don’t remember writing this. You’re definitely correct! I wrote this 5 years ago. I was 10 when I wrote this, so I kinda have an excuse for being so wrong.
Restated just to memorize it: Let us assume there are finitely many primes and let us say that we have a set P whose elements contain all of these primes. Say we have a number Q which is the product of all the elements in set P, and let us add 1 to Q to get a different number R. Because Q has a unique prime factorization, and R is not equal to Q, this must mean that R contains a unique prime factorization that is not contained in set P. This is a contradiction, as we had assumed that we have all the finite amounts of primes in our set P. This implies that there are infinitely many primes.
Love that there's often a bunch of rubik's cubes laying around. Cubes got me into the concept of group theory as a kid, and introduced me to math when I started speedcubing!
I guess it is fair to say that. That's the beauty of the concept of "infinity", where two sets of numbers that seem to have different "sizes", can be made into pairs indefinitely, making them the "same" sizes.
Also that leads to the question of do we know all the primes from 2 to the largest or are we missing a lot in between? I'd love to see a response to this from anyone knowledgeable on it
We are missing almost all of them in between. The large primes are almost all Mersenne Primes, which are very rare compared to regular primes. In fact the number of "missing" primes is so large, that if you took every particle in the universe, you would not have enough particles to assign one to each prime. I'm struggling to express just how incomprehensibly large the largest known prime is. If every particle in the universe was an entire universe of particle, it would not even come close.
@@Ariel1S Damn, giving me the answers 8 years later. That's really crazy though considering the relative sparsity of primes. But this does make sense given some of the other Numberphile videos I've watched on large numbers. Do you know if my other question from 8 years ago is correct? Quoting myself, "if we have a list of the primes starting from 2 to the current known biggest prime, couldn't we multiply them all up and add one and we'd get the new biggest prime number? I mean obviously that number would be gigantic but it'd be a new prime wouldn't it?"
Silly actually but the Euclids version of lines to describe prime numbers made my coin slip through, now I understand prime numbers completely. Every other explanation is just confusing. Thanks!
It works if your list is complete up to that point. The problem is that even with the first two primes, you're skipping 5. 2x3 = 6 +1 = 7 ... but you have to come up with 5 in some other way. It turns out that the product of all primes MINUS 1 works just as well, but even so, you eventually get to where you're skipping primes, so your list is no longer complete. (2x3x5 = 30 from which we can deduce that 29 and 31 are prime, but now we've skipped 7, 11, 13, 17, 19, and 23).
The important thing is that Q is not made up of any primes on the list. Since Q is the product of "every" prime and then plus 1, none of the primes on our list can divide Q. (If any prime did divide Q, it would have to divide 1). This gives us two possibilities: 1) Q is a new prime which is not on the list 2) Q is a product of primes, but those primes are not on the list. Either way, this contradicts the completion of our list. Does this answer your question?
+Michael Miller What you're asking is called the "twin prime conjecture." It is an open problem, meaning that we don't know if it is true or not. So it may be possible that there are infinitely many twin primes. We don't know. It doesn't immediately follow from the existence of infinitely many prime numbers.
+MuffinsAPlenty In case anyone was thinking that P(n) - 1 is also always prime, it is not. 2 * 3 * 5 * 7 = 210. 211 is prime. 209 = 11 * 19 p(n) - 1 instead of the p(n) + 1 at 2:04 edited to add link to video time
@@aspiringcloudexpert5127 I think Amar is misremembering something. In 2013, mathematician Yitang Zhang made a significant step toward verifying the Twin Prime Conjecture by proving there are an infinite number of pairs of primes that differ by at most 70,000,000. (Yes, there is a numberphile video for this.) That sounds like a long way from proving the TPC, but the fact that an upper limit had been established on the gap between primes was considered a huge breakthrough. Since then, that upper limit has been whittled down to around 246. When they get the gap down to 2, the conjecture is proven.
Yes, all prime numbers squared give 1 as remainder divided by 8. Proof is simple: Every prime could be written as 4n+1 or 4n+3 because it is not divisible by 4, and 4n+2 is obviously even number, therefore not prime. (note this works with all primes but 2, (2*2)%8=4 ). when you square those two you get: 16n^2+8n+1 and 16n^2+24n+9 which you can separate as 8*(2n^2+n) +1 and 8*(2n^2+3n+1) +1, so remainder must be 1 :)
Because of the Fundamental Theorem of Arithmetic, if a number can be divided by a composite number (non-prime), then it it can be divided by a prime number. This is because every composite number can be written as a unique product of primes. So if a number isn't divisible by any primes, it cannot be divisible by any composite numbers either (because then it would be divisible by the prime factors of the composite number).
I really don't understand this proof. I'm probably just missing something; but if this were true, then couldn't you just generate new primes by multiplying the known primes and adding 1? And for example, (2*3*5*7*11*13)+1 creates a number that is not prime and can be a product of the previous prime factors because it can use them more than once, (i.e. 2*2*2*3*etc). Can you help me understand what I'm missing, thanks!
The main assumption of the argument is that there are finitely many primes. Under that assumption, one shows that there must a a new prime that does not exist in this list. Thus, the original assumption is wrong. This DOES not mean you can just make new primes this way because your initial assumption was already wrong, and any conclusions that follows from a flawed premise has no ground to stand on. For instance, 2*3*5*7*11*13+1 = 59*509 is NOT prime.
Albert Renshaw In this problem, we assume that P1, P2, P3... are all *successive* primes, not any random. After a point, we won't be able to generate more primes because the primes we have aren't successive
I was also confused by this part, but I found out why it works. Suppose you have a number divisible by 2,3 and 5. To get the next number divisibile by 2, you need to add 2 to it. To get to the next number divisible by 3, you need to add 3, etc. So if you only add one, your number cannot be divisible by 2, 3 or 5. It can however be divisible by another prime, like 7.
Proof by contradiction works by first making the negation of what you are trying to proof. In this case, there is a finite amount of primes. Then, you use logic to reach a contradiction. Since you have a contradiction, and the reasoning is correct (hopefully!), you can conclude that the initial assumption was false. Hope it helps.
Thank you for being the only person to actually give a detailed response. Interesting read/review of what I've studied years ago. I disagree with some of your response (or agree with other parts but fail to see how a point has been made). Since I wish to give you a fair and respectful answer, I will need a lot of time to reply. I am busy preparing for a trip to the Philippines, and then will be gone much of May, so if I don't reply soon, please don't take it as disrespect or a dodge.
Random question... How do people know that Pi will never end? We know it hasn't ended even after a ridiculous amount of digits, but how is that proof that it never ends? Or do people just assume?
The answer of that is more philosophical than mathematical. All numbers that we normally use are base on power of 10, so we can always find a 10^-infinity mistake when we measure, and therefore we will have always some mistake in measurement. In simple words nothing can be precisely measure, because we always be wrong by some 10^-n.
Basically, if pi terminated, it would have to be a rational number. This means it could be written as p/q, where p and q are integers. Further, this means that by using only whole numbers and the basic operations (addition, subtraction, multiplication, division, exponentiation, and rooting), one could devise a series of operations that would equal 0. You are not allowed to multiply by 0, in case you were wondering. Numbers like this are called algebraic numbers. On the flip side, numbers that cannot be reduced to zero are transcendental. Lindemann and Weierstrauss proved that e was transcendental. Then using Euler's Identity and some other theorems, they proved pi was transcendental, therefore irrational, and therefore non-terminating.
see too the proof about the so-called "liouville numbers", know that none algebraic irrational numbers can a liouville number (as square root of 2 and from any integer number; golden ratio, silver ratio, etc, ...) .only transcedental numbers as "pi" and euler number 2.718218183... i believe having helpwd, right ... ??? goodbye
One can prove that pi is an irrational number. Irrational numbers do not terminate (they have infinitely many digits after the decimal point). The easiest way to see this is to note that if a number *does* terminate, then it is rational (just write out the base 10 representation and add up all the “places”). So you can write any terminating number as a fraction. Since pi cannot be written as a fraction, it does not terminate (see “proof by contrapositive”). Also, some rational numbers do not terminate either, but irrational numbers are especially interesting because they have no repeating pattern in their digits. Another example of an irrational number is the square root of 2. Good question, but how did it get 44 upvotes before getting an answer?
2:40 What about powers of primes? You could take some prime factors of Q to some power, remove others; and have a cocktail of prime factors that, together, divide Q, exactly. 🤔
What about them? The number Q is 1+A*B*C*D*..., where A, B, C, D, ... are finitely many prime numbers. So by construction, Q can't by divisible by any of the primes A, B, C, D, ... . So it must either be a prime, or be divisible by some other prime than A, B, C, D, ... . (We are implicitly using the property that every positive integer has a unique factorization into primes.)
@@MikeRosoftJH I figured out that Q couldn’t be divisible by any combination of those primes, or their powers; because it’s 1 away from a multiple of all of them, and 2 consecutive multiples of n are n away from each other. That could have been said in the video, though. From, what I’ve heard from my Friend, who majored in Maths, at uni, if you were to present this proof shown in the video, and added no more info, in an exam, you would get pretty much 0 marks.
Paul Donovan Depends on the context, but in this case primes are defined as integers greater than 1 divisible only by themselves and 1. In other contexts negative numbers can be prime. My Abstract Algebra text defines a prime element of Z (set of integers) as an element p that isn't zero and if p divides a*b, then either p divides a or p divides b.
Because otherwise, Q would be divisible by ANY prime number. It would be P1 x (P2 x P3 x ... Pn) or P2 x (P1 x P3 x ... Pn) or P3 x (P1 x P2 x ... Px) and so on ~ all evenly divisible. By adding the 1, you get a remainder 1 no matter what prime number on the list you try to divide it by. Meaning there must be a prime number not on the list that divides it too.
i was asking the exact same question at first too but it just clicked. Any number can be made by timesing primes together In the proof by contradiction they assume that there are a finite number of primes therefore you can created a list So they have a number say N for example which is made by timesing all the primes together therefore all the primes being a factor of N But if we add any number it doesn't have to be 1 to N you are not able to make N from the number of primes in the list Therefore based on the fact that all number can be made up of timesing primes There must be another prime number which exists
+Spencer Wadsworth yeah, like Pythagoras was put on a boat with no food/water and sent off into the ocean for discovering the first irrational number, which is the square root of 2.
I never understand why this is always expressed as a proof by contradiction, which in my opinion only confuses the pupils when first confronted with this. Just start with any finite set of prime numbers, multiply them all, add one, and thus find a number that can't be divided by any prime on the list, but HAS to either be divisible by a prime (which is then not on the list) or be a prime itself. This shows that no finite set of primes can contain all primes - DONE! There's no need to start with "Suppose there were only finitely many primes."
If you want to "Just start with any finite set of prime numbers," you need to assume this list exists. Doing this you are doing a proof by contradiction.
I don't think so. I don't assume anything! I don't have to assume the existence of a finit set of prime numbers, because we all KNOW there are finite sets of prime numbers! I start with any finite set of prime numbers and show, that there are prime numbers not in my set. This proves, that no finite set of prime numbers can contain all of them - directly, no contradiction - so there have to be infinitely many of them: DONE (or, traditionally: q.e.d.)!
+karl131058 Thing is that you are only proving there are more primes than exist on your list, not that infinite primes exist. Extending it to other lists still requires you to prove it for those other lists. By assuming that which you set out to prove false, you can make the proof much simpler. "Assume there are finite primes. Then a list of all primes can be made. Using this list a number of the form of Q can be devised. Dividing Q by any prime on my finite list results in a remainder of 1 because of how Q is defined, thus there must be a prime not on my finite list. Thus there aren't finite primes, but infinite primes."
it is a proof by contradiction in that you assume ( mathematically speaking) that a finite set contains them all that's really all the proof this video shows is doing as well it assumes there are n primes it then shows that there has to be an (n+1)th not on the list already.
The point pf the proof is that it looks at two things. 1) Q it self is a prime and so the initial list was incomplete. 2) Q isn't prime so it will have to be divisible by a prime. But we can show that it won't be divisble by any of the primes on the list because there will always be a reminder of 1 (which is why we added the 1 in the first place) and that means there are more primes out there that aren't on the list so the list was incomplete. continues...
You're absolutely right. I'm glad I'm not the only one who has seen that. One thing special though about two that doesn't apply to other primes is the fact that it is the smallest prime number.
All right, now that we know that 1+2+3+4+5+6+... = -1/12, and there's an infinite number of primes, what is the sum of all the prime numbers? (2+3+5+7+11+13+17+19+23+29...) :p
+Félix Pinchon in theory you can make an infinite sum. -1/12 for all numbers then that means -n/12 for numbers divisible by n so when we get rid of all the even numbers ( those that divide by two) we get -1/12-(-2/12) = +1/12 add 2 back in and we get +2 1/12 then one third are divisble by 3 so -3/12 but those that divide by 6 have been taken away already because they have 2 as a factor. so add 3/12 because -3/12 -(-6/12) = 3/12 etc. I may be wrong.
+Félix Pinchon Let (sum over primes + 1) = x, then x^2 = sum of all numbers with at most two prime factors, because each of these numbers is reached exactly once when multiplying the terms with each other. So x^n = sum of all numbers with at most n prime numbers, for the same reasoning. Now take the limit n->infinity, so lim n->infinity = 1+2+3+4+...which we know is equal to -1/12. So x = lim n->infinity (-1/12)^(1/n) = 1. there you have it, 2+3+5+7+11+13+17+.... = x-1 = 0. *Insert Trollface here*
1+2+3+4+5+... does not equal -1/12. You are mistaking this for a different infinite sum. Also, there's a difference between converging and diverging series. A converging series comes closer to a certain value over time. For example 1+0.5+0.25+0.125... = 2. On the other hand a diverging series does not approach a specific number over time. 2+3+5+7+11+13+17+19+23+29+31... approaches infinity rather than a specific number.
You might be right about 2+3+5+7+11+13+17+19+23+29+31... approaching infinity, but I'm sure that 1+2+3+4+5... = -1/12 ^^ There's a lot of videos proving this on the internet
Euclid's proof, that there is an infinite number of prime numbers, is saying that "you can always add another to it, because it is infinite" he had a cyclic proof? that's like me saying the universe is infinite, because if you traveled to the edge of our known universe, you can keep going.
+paonquinho Actually, Euclid's original proof wasn't by contradiction. It's not actually necessary to assume that your initial list contains all primes, as the proof works just as well either way.
NoriMori how exactly is that stated? If your initial list isn't assumed to be all primes, then the fact that you can get more just implies that there are more than in your original list, not that there are infinitely many. It is a kind of induction?
Joe Alias "If your initial list isn't assumed to be all primes, then the fact that you can get more just implies that there are more than in your original list" And since you can keep doing this with any list of primes, there must be infinitely many of them. ;)
NoriMori Interesting, I see how that works, and yet when I try to explain to myself why that works, I still have to sort of do a proof by contradiction in my head--to say that you can always get more primes than a finite list contains implies that there are also more than in a finite list of all primes, if one were assumed to exist. I only took one mathematical logic class, so some of this is cloudy.
Like it is shown in the video there is no such thing as "the biggest prime", so it can't be infinite either. Things which don't exist can't have any properties.
I don't know why you got thumbs down.. Its really sad that people would thumb down a legitimate and interesting comment. You were curious and you had an idea, neither of these things are bad. So many haters on the web.
Fun fact about this proof: 2 * 3 + 1 = 7, a prime 2 * 3 * 5 + 1 = 31, a prime 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509 The product of all prime numbers in the interval [a,b] plus one will result in either a prime number that does not belong to that interval or a composite number whose prime factors do not belong to that interval.
I never saw Euclid's proof using geometry. I came up with mine. Neither algebra nor arithmetic is needed. Suppose distinct segment lengths A, B, and C that can’t be divided into lengths of whole numbers other than the unit segment. Suppose that lines can be a multiple of segments A, B and/or C units only. Consider such a line XY X --------------------------- Y It can be divided in segments A as follows X --|--|--|--|--|--|--|--|--|-- Y It can be divided in segments B as follows X ---|---|---|---|---|---|--- Y It can be divided in segments C as follows X -----|------|------|----- Y Next, extend the length of the line all the way to Z X -----|------|------|----- Y------------------------------------------------------------------------------Z Since the assumption is that lines can be a multiple of segments A, B and/or C units only, so too is line XZ. This restricts the possible lengths that XZ can take. To see how, suppose I extend the line XZ by one unit U: X -----|------|------|----- Y------------------------------------------------------------------------------Z-| U Since this is the unit, it can’t be divided into lengths A, B or C. Therefore, line XZU can’t be divided into segments A, B or C. The length XZU constitutes a multiple of a new prime number. This argument applies all the way to infinity. Note that it can't be determined what that prime number is.
You had a video earlier about the largest documented prime. From this proof you could derive a prime number generating algorithm: p[n+1] = p[n] * (p[n] + 1) It produces primes with 1 subtracted from it. So to get the prime just add 1 to p[n]. So far I'm on a prime with 1,707,522 digits after a few minutes of running it. Every prime has roughly 2x more digits but takes 4x longer to compute from the previous prime. This 1.7M prime took 87.1 seconds to calculate from the previous, which took 20
Amazing! You have simultaneously found not only a prime number generating equation, but a Mersenne prime generating equation. This also means that soon we may finally have a proof for infinite perfect numbers.
Even if you multiply the first n primes together and add 1, the result is not guaranteed to be prime. It will necessarily be relatively prime to the first n primes, but that doesn't mean it is prime itself. Ex: 2*3*5*7*11*13 + 1 = 30031 = 59 * 509 So then we'd have to use additional computing power to try to find any divisors of our result since it wouldn't necessarily be prime.
If there is a bijection between two sets A and B then they have the same cardinality. It's just defined by some equivalence relation over sets. The set S is considered finite with cardinality n if there is a bijection between S and a subset of the natural numbers {0, ..., n-1}. We can biject your set with {0, 1, 2, 3} and hence the cardinality is 4.
He didn't say that Q+1 was a prime number, he said that if it were a prime number it would violate the thinking that there is finite number of primes and therefore proving that primes are infinite. He's simply suggesting it could be prime, while at the same time there's a complete possibility that it's not a prime.
As an example, suppose our "list of known primes" we intended to generate a new prime from was at some point only {2, 3, 5, 7}. We compute the next one as (2*3*5*7) -1 = (210) -1 = 209, which isn't a prime (11*19=209).
The point I've been trying to make to you and everyone else here who disagrees is that you cannot confuse size in the sense of cardinality with size in the sense of actual length of a list. If you wish to list out all the numbers, and while doing this, you start listing primes and non-primes as they appear, once you pass 14, and so on.. your composite list will start to fill up faster than the primes list. We can see from this example that both lists "match up" with x but at different rates.
But you have to agree that 2 does have a little special place in this and other divisibility issues. All you need to see is the last number of a number, doesn't matter how many digits it has, we know instantly if it's divisible by 2 and is even. Of course the same goes with 5. But if the number ends in 1, 3, 7 or 9 we really don't know whether it's divisble by any number until we know the whole number. And it's just how we've defined even and odd. But you're making a good point though.
Not a stupid question at all, but no, your number is the number Q from the video, and at 2:07, James explains that Q may not be prime, but it could be divided by primes that are not on the list. So, we could find new primes by finding the prime factors of Q, but, as you said, at this point Q would be HUGE and finding its prime factors would be nearly impossible (at least with today's tools). A counterexample: 1*2*4*5*7*11*13+1=30031=59*509 (taken from wikipedia at "Euclid_number")
I didn't state it very well; you're correct that unless the list of primes is complete (which is impossible for the reason given in the video) the product plus or minus one is not guaranteed to be prime (it WILL be prime relative to primes in the list, though).
To clear up what I said Q being a number must be able to be rewritten as a product of prime numbers, in short, the primes listed cant do that because there will always be a remainder of one. Keep in mind that Q is a number greater than the largest prime that's on his list because its made up of multiplying all of his primes and adding one.
The point there is that Q is defined as the product of all primes plus one. That means that Q is either a missed prime or not a number. And it is a number, but not on the list. The +1 came from the very definition of Q.
You might benefit from another numberphile video, "Infinity is bigger than you think". Suffice to say, it's all about listing. To list my fingers, I can write thumb index middle ring pinky That list is 5 lines long, and each line contains exactly 1 finger (counting my thumb as a finger), so I have 5 fingers. I can put all the fingers into 1 line to make the "list" 1 line long, but that doesn't mean I have 1 finger. I can also put empty lines between fingers, but not have 6 or 7 fingers.
Okay here's the thing why many people have thumbed this down, I didn't. 1) I've lost count how may times this question has been answered on this video's comments. So shouldn't be too much trouble to find out. Obviously he/she didn't know that so he/she didn't know to look for it. 2) He gave 3 example numbers to prove his theory and one of them was wrong. If you're going to prove a point make sure at least your examples are correct. People should pay more attention to what they do.
Maybe I said that a bit prematurely. I'm also not a mathematician, but a physics student (hence I'm not an expert of set theory). Of course you *could* say that there is a difference in numbers of elements in said sets. After all, cardinality is just a definition. You could always make up your own, as long as it is well-defined, clear and works for any kind of set (not just numbers). And if it is helpful (or “better” than current definitions in any way), people might even start using it instead.
More precisely it's that you can't divide Q by any of said primes. "Using that same set of numbers differently" would mean some of them divide Q. For some prime in the list (say p1) to divide Q, there would have to be some integer k such that Q = p1*p2*...*pn + 1 = k*p1. But if you divide out p1 you get p2*p3*...*pn + (1/p1) = k. Since no numbers but 1 divide 1 and 1 isn't a prime, there's a contradiction, and so no primes in the list divide Q.
Because if Q is not prime, then it must be composed as a product of the prime numbers he listed. Meaning those prime numbers divide Q evenly. Call the list he made "N", so N +1 / P where P is a prime must equal a whole number. For that to be true N/P must be a whole number (which it will be) and 1/P must be a whole as well as fractions with common denominators split (Which is nonsense, a number greater than one will not yield a whole number and one is not prime)
If I understand you correctly, your question is more of "why does 1 make the proof work?" That's a fair question. Notice that Q - p1p2...pn = 1 We can show that Q isn't divisible by a prime by contradiction too. Suppose Q could be divided by a prime on the list. Say, for instance p1 (you can choose whichever prime you want, not just p1). So if p1 divides Q, then Q = p1 * r for some integer r. So p1(r - p2p3...pn) = 1 This means that p1 divides 1, but no prime divides 1, a contradiction.
I was dissatisfied with "by a factor of about 6" so I did something similar by using the prime number theorem to approximate the number of primes from 1 to 10^n and then from 10^n to 10^(n+1), and took the ratio of those. You end up canceling a bunch of logs and 10^ns and get (9n+1)/(n+1). Approaching infinity, you get nine times more primes between 10^n and 10^(n+1) than below 10^n. Naturally, the ratio of the number of primes up to 10^(n+1) to the number up to 10^n ends up (10n+1)/(n+1).
You have to add/say/remind that any interger can be decomposed into prime factors, otherwise one might say that Q could be divisible 10, like 3*3+1. But since 10 is 2*5 10 divides P1*P2*...*Pn etc...
i agree, i absolutely despise the sound of a sharpie writing on paper. to me, it's almost as bad as someone scratching on a blackboard. but still i keep coming back to numberphile
It is possible... but that is not a sure way of doing it because it doesn't always work: 2*3*5*7*11*13 + 1 = 30031 = 59*509 (so not prime), but if you stop at 11, 2*3*5*7*11 + 1 = 2311 (prime).. so sometimes it works, sometimes it does not.
1) when you do that you aren't guaranteed that the new number is prime, but it must have a prime as a factor that you haven't listed. however factoring numbers is generally hard. 2) 111 = 3*37, 1111=11*101, 11111=47*271.
No, Q isn't necessary a prime but it might be. What is true is that Q won't be divisible by any of the primes in the list but that doesn't guarantee that it's prime itself. It may be a product of two or more unknown primes that are bigger than the biggest prime on our list.
this is why the term "complete list" is important. lets say the complete list is 2 3 5 7 11 and 13, technically adding 1 would add a new number to the list BUT we know there is more to the list because that number is not prime. the question asked is the proof of the answer ;) assuming that adding 1 creates a new number means the list must be expanded.
Do you mean to take an odd number of "just some primes" or the complete list of primes until a biggest one (so far)? Because if you take the complete list from P_1 to P_n you'll have the first prime, namely the number 2, in that list. And if you multiply all together, the new number (Q - 1) = P_1 * P_2 * ... * P_n will be even and Q will be odd.
5:50 this man just divided a line into 7ths first try
Yeah... I noticed it too! Remarkable :)
What a guy!
@@joonasneumann9088 No he isn't xD He's a mathematician.
it's called geometry eyes.
@@joonasneumann9088 Is he? O.o
4:47 "Mathematics is the search for truth and this book is as true today as it was 2300 years ago" - James Grime
It reminds me of something Ricky Gervais said about science books. 'You could destroy all science and math text books and in 1000 years they'd all be back with the exact same information in because all the same tests would generate all the same results, if you did this with the bible or any other religious text then it would simply be gone'
@@nekogod not science books, science (aka natural philosophy) has been around for around 2000 years
we would be pretty stuck if all the books popped out of existence
mathematics though, we would rebound much quicker than science, and we would fix mistakes people made along the way (complex numbers turned into compound numbers, using a base 12 system for arithmatic)
@@toastyarmor6858 Science books would be back eventually, though they may look different and the units might be different. The speed of light would remain the same, the number of particles in a hydrogen atom would remain the same, gravity would be the same etc. I'm not saying the exact books would be back and be identical, rather that the information contained is not defined by itself. Destroying the books doesn't destroy the information it still exists to be found again, this is not true of most other things.
@@nekogod thats not true though, maybe maths yes but science evolves and new discoveries would almost garuntee some things we have today in our books will not be there in 2000 years.
Secondly, there is a religous scripture which millions have memorised down to the letter in full, I challenge you to know what it is ?
@@greenprofile5755 I will concede that some things will be different as we may have better theories for some things. But the bulk would be the same things like the speed of light in a vacuum, the gravitational constant etc. By destroy all books etc I meant destroy all knowledge if all religious books were destroyed and everyone who memorised them refused to pass on that knowledge it would be permanently lost. This is not true of maths at all and is almost completely not true for science either
5:44 Probably the most impressive thing he does in this video
Hats off to Euclid...
Fruit roll-ups Boi I was gonna day that but then I saw your comment.
@@maxonmendel5757 i was just about to say that ahaha but then i saw u already said that
He can divide a line in perfect seven parts
He is a mathematician
Magic is common there
I cheated by splitting a line, in pencil, into 8 segments; much easier...then erased one of the end segments.
My thoughts, exactly 😮.
@@maxwellsequation4887 I guess you could call him: ”a *_MATHEMAGICIAN”._*
**shot** 😵🔫
@@jwm239ah, but then one of the line segments become twice as long as the others!
4:49: "Mathematics is the search for Truth" - Absolutely! That is why I became a mathematician!
Mathematics is *a* search for truth in one domain of reality.
@@siquod no, not really. it's usually done so it stays somewhat relevant to what makes sense in our reality but mathematics can also deal with completely unrealistic things and axioms, as long as they don't contradict each other. logic is not dependent on reality
I have a question:
Suppose the only primes are 2,3,5,7,11,13 and 17. And I want to construct a number Q by multiplying all of them together, and then adding 1.
2 x 3 x 5 x 7 x 11 x 13 x 17 = 510,510 +1 = 510,511 which is not a prime.
So... what gives? Who's to say Q in your proof isn't like 510,511?
edit: did some thinking and 510,511 is factored by 19, 97, and 277, none of those being on the list. therefore the list was not complete. Well played mathematics... you win again.
Congratulations, you understood the video.
Tito Titoburg
You supposed 2,3,...,17 are the only primes, so, if that is true (and you're assuming it is) Q, which is the product of all the primes + 1, IS a prime number.
But you said numbers 2,3,...,17 are the only primes, so you just contradicted yourself.
That means 2,3,...,17 aren't the only primes.
This is a proof by contradiction.
Yeah, the thing is that Q is not necessary a prime, but instead a coprime of all the others. In other words, the proof just states that there is not any prime of your finite list that divides Q, so either there exists a larger prime that divides Q or Q is a prime itself.
You don’t even need your list to be the first n primes. And you don’t even need to assume your list is complete for the proof to work.
The proof is just that if you have any finite list of primes, you can show (by taking their product and adding one) that there’s other primes that weren’t in your list. If any finite list is incomplete then there must be infinitely many.
Eg if you take the list 3, 5 and 7, you multiply them together and get 105. Add one and you get 106. Since 106 isn’t divisible by 3, 5 or 7 either it’s prime (obviously it’s not) or its prime factors weren’t on your list.
What puzzled me for ages about Euclid’s proof was what Grimes says at 1:43 and, especially, at 2:09. What I didn’t at the time realize was that proof calls on another famous piece of maths, the _Fundamental Theorem of Arithmetic,_ from which we can be confident that every integer greater than 1 is either prime, or is the product of primes where that product is unique. It’s part of the beauty of maths that I was able to be impressed at Euclid’s proof without knowing (or even knowing _about)_ the _Fundamental Theorem of Arithmetic._ But still, it niggled me, and eventually when I learned about it I was even more impressed. 🙂
I have been struggling with this for days, thank you so much! Every definition I read kept stating, “Q must be prime or the product of primes”, which left me wondering why it couldn’t be a product of non-primes larger than Pn
I never saw Euclid's proof using geometry. I came up with mine. Neither algebra nor arithmetic is needed.
Suppose distinct segment lengths A, B, and C that can’t be divided into lengths of whole numbers other than the unit segment. Suppose that lines can be a multiple of segments A, B and/or C units only.
Consider such a line XY
X --------------------------- Y
It can be divided in segments A as follows
X --|--|--|--|--|--|--|--|--|-- Y
It can be divided in segments B as follows
X ---|---|---|---|---|---|--- Y
It can be divided in segments C as follows
X -----|------|------|----- Y
Next, extend the length of the line all the way to Z
X -----|------|------|----- Y------------------------------------------------------------------------------Z
Since the assumption is that lines can be a multiple of segments A, B and/or C units only, so too is line XZ. This restricts the possible lengths that XZ can take. To see how, suppose I extend the line XZ by one unit U:
X -----|------|------|----- Y------------------------------------------------------------------------------Z-|
U
Since this is the unit, it can’t be divided into lengths A, B or C. Therefore, line XZU can’t be divided into segments A, B or C. The length XZU constitutes a multiple of a new prime number. This argument applies all the way to infinity. Note that it can't be determined what that prime number is.
@@jeancorriveau8686 one of the opening suppositions of your "proof" is, _"that lines can be a multiple of segments A, B and/or C units only"._ However, towards the end it says that, _"line XZU can't be divided into segments A, B, or C"._ Isn't that a contradiction?
@@KT-dj4iy Yes, a contradiction. So, my initial assumption, "that lines can be a multiple of segments A, B and/or C units only" is wrong.
@@jeancorriveau8686, ah, I see. You were deploying proof by contradiction; fair enough. But then exactly what have you proven? Isn't it simply that the proposition, _"Lines can be a multiple of segments A, B and/or C units only"_ is false? It doesn't seem immediately obvious that that is equivalent to the proposition that there is an infinity of primes.
Infinite primes? Infinite Grimes.
Technium
Oh I love me some infinite grimes
Eternia Maybe James is our Rick Sanchez and he's only 30 years away from discovering interdimensional travel.
Technium kkkk
You mean (-1/12) because 1+2+3+4+5+6+7+8+9+...=-1/12
Infinite crimes.... wut
5:38 he draws a nearly perfectly straight line and then divides it into seven nearly perfectly equal parts like it's no big deal?!?!
Grime´s enthusiasm for mathematics makes me enthusiastic about mathematics!
Thanks for your reference to Euclid's Elements, after watching this video, I purchased the book and it's brilliant.
Never mind the Math, where can I get the brown paper roll?
Off the shelf at all manner of arts and crafts shops or packaging outlets. It's unbleached newsprint, and it's fairly common.
I love Dr. Grime's enthusiasm for his field of study. ^^
6:03 All these years and I've never heard of a geometric definition of a prime before. Very nice.
I actually like euclid's definition better than modern days
+@Pybro But it's different as it would include 1 as prime.
Group theory allows you to define something very similar. Cyclic groups of prime order have only themselves and the trivial subgroup as subgroups.
+@Hassan Akhtar Quite the contrary: 1 was the first number.
Yeah it's so clever
heh, I might agree with you if I wasn't taking geometry right now XP
Seeing the passion you guys have for numbers and mathematics is inspiring. It shows me that what is mundane to you could be incredibly meaningful to me, and that no intellectual pursuit is without value. I don't have the same passion for numbers, but I do have passion for other things, and the fun and knowledge I gain by watching these encourages me to go and exercise my own talents and intellect. I am grateful for that.
Translations:
Ashume -> Assume
Noombar -> Number
Drawring -> Drawing
hhhh you aAAA funny ,
Lol
The'ee should be mooo translations xD
Enlightenment *Noombah
cohld = called
Loved this, a specific book reference re: Euclids Elements would be great!
Thank you for pointing that out to me. I guess I hadn't thought about the fact that since the list is by definition incomplete, it doesn't have to be the set of all prime numbers within a given range, just that the answer will never be divisible by any number in the series. If you leave 2 out of the series, your product will be divisible by 2 (and not any of the numbers in your series), proving that you have an incomplete list. Makes sense now.
To host, thank you for sharing the book.Really interesting series of topics on math, very much appreciated.
At 5:15, when the book of Euclid's Elements is shown (his definition of a prime), I spotted a spelling error in the book. "A unit" is the correct spelling, versus the incorrect "an unit" one in the book. Nothing important really, in context of the subject, just saying... :)
That's not an error. The text likely is an old translation from when unit wasn't yet pronounced yunit in english but more like oonit.
Thank you sir
This is very well explained. Thanks Brady and Dr. Grimes!
I was doing some math and found that (2n)+(n^2)-1 created primes very well if n is even. Example: (2 x 99922222222220)+(99922222222220^2)-1 is prime. I also saw that up to 200 being n (leaving out odd numbers) it spit out a prime 42% of the time.
Sampling a random number from 0 to 200 that isnt even gives you a probability of around 43% to hit a prime. Thats better than your formula if we are looking at a injective functions that gives you primes. For numbers from 1E12 to 1E14 (sampled) your formula hits a prime around 5.6% of the time. The prime number theorem tells us there is a 6.34% probability with random sampling on non-even numbers.
In fact, your formula of 2(2n)+((2n)**2)-1 is pretty much always worse than 2n+1 if we are only looking at the probability of getting a prime on input. Your formula however has the advantage of outputting way bigger numbers. If we adjust for the asymptotic quadratic growth of your formula then your formula is around 2.5% better from 1E12 to 1E14 but this will slowly but surely go to 0% as n grows.
@@hypnogri5457I’m going to be honest, I don’t remember writing this. You’re definitely correct!
I wrote this 5 years ago.
I was 10 when I wrote this, so I kinda have an excuse for being so wrong.
this channel is gold
Restated just to memorize it:
Let us assume there are finitely many primes and let us say that we have a set P whose elements contain all of these primes. Say we have a number Q which is the product of all the elements in set P, and let us add 1 to Q to get a different number R. Because Q has a unique prime factorization, and R is not equal to Q, this must mean that R contains a unique prime factorization that is not contained in set P. This is a contradiction, as we had assumed that we have all the finite amounts of primes in our set P. This implies that there are infinitely many primes.
Such fun videos
"math is the search of truth" is the most beautiful thing
It took me a couple rewatches to understand that proof, but now that I do, I see why you called it elegant!
Love that there's often a bunch of rubik's cubes laying around.
Cubes got me into the concept of group theory as a kid, and introduced me to math when I started speedcubing!
Thank you sir
I guess it is fair to say that. That's the beauty of the concept of "infinity", where two sets of numbers that seem to have different "sizes", can be made into pairs indefinitely, making them the "same" sizes.
Also that leads to the question of do we know all the primes from 2 to the largest or are we missing a lot in between? I'd love to see a response to this from anyone knowledgeable on it
We are missing almost all of them in between. The large primes are almost all Mersenne Primes, which are very rare compared to regular primes. In fact the number of "missing" primes is so large, that if you took every particle in the universe, you would not have enough particles to assign one to each prime. I'm struggling to express just how incomprehensibly large the largest known prime is. If every particle in the universe was an entire universe of particle, it would not even come close.
@@Ariel1S Damn, giving me the answers 8 years later. That's really crazy though considering the relative sparsity of primes. But this does make sense given some of the other Numberphile videos I've watched on large numbers.
Do you know if my other question from 8 years ago is correct? Quoting myself, "if we have a list of the primes starting from 2 to the current known biggest prime, couldn't we multiply them all up and add one and we'd get the new biggest prime number? I mean obviously that number would be gigantic but it'd be a new prime wouldn't it?"
@@aceguy1234 Not necessarily. 2*3*5*7*11*13 = 30030, but 30031 is not prime.
@@aceguy1234 wooo you're still alive that's dope af
Silly actually but the Euclids version of lines to describe prime numbers made my coin slip through, now I understand prime numbers completely. Every other explanation is just confusing.
Thanks!
James should upload a skin care routine! His skin is amazing!
It works if your list is complete up to that point. The problem is that even with the first two primes, you're skipping 5. 2x3 = 6 +1 = 7 ... but you have to come up with 5 in some other way. It turns out that the product of all primes MINUS 1 works just as well, but even so, you eventually get to where you're skipping primes, so your list is no longer complete. (2x3x5 = 30 from which we can deduce that 29 and 31 are prime, but now we've skipped 7, 11, 13, 17, 19, and 23).
The important thing is that Q is not made up of any primes on the list.
Since Q is the product of "every" prime and then plus 1, none of the primes on our list can divide Q. (If any prime did divide Q, it would have to divide 1).
This gives us two possibilities:
1) Q is a new prime which is not on the list
2) Q is a product of primes, but those primes are not on the list.
Either way, this contradicts the completion of our list.
Does this answer your question?
If there are infinitely many prime numbers, are there also infinitely many twin primes?
+Michael Miller What you're asking is called the "twin prime conjecture." It is an open problem, meaning that we don't know if it is true or not.
So it may be possible that there are infinitely many twin primes. We don't know. It doesn't immediately follow from the existence of infinitely many prime numbers.
+MuffinsAPlenty In case anyone was thinking that P(n) - 1 is also always prime, it is not.
2 * 3 * 5 * 7 = 210. 211 is prime. 209 = 11 * 19
p(n) - 1 instead of the p(n) + 1 at 2:04
edited to add link to video time
There actually are an infinite number of twin primes. It has been proven recently, and Numberphile made a video about it.
@@amarmesic7170 Are you sure about that?
@@aspiringcloudexpert5127 I think Amar is misremembering something. In 2013, mathematician Yitang Zhang made a significant step toward verifying the Twin Prime Conjecture by proving there are an infinite number of pairs of primes that differ by at most 70,000,000. (Yes, there is a numberphile video for this.) That sounds like a long way from proving the TPC, but the fact that an upper limit had been established on the gap between primes was considered a huge breakthrough. Since then, that upper limit has been whittled down to around 246. When they get the gap down to 2, the conjecture is proven.
5:13 11 is also a prime.......just sayin’
I don't get it
Just realized I'm watching Numberphile instead of studying for my math final exam. Oh well
Yes, all prime numbers squared give 1 as remainder divided by 8. Proof is simple:
Every prime could be written as 4n+1 or 4n+3 because it is not divisible by 4, and 4n+2 is obviously even number, therefore not prime. (note this works with all primes but 2, (2*2)%8=4 ). when you square those two you get:
16n^2+8n+1 and 16n^2+24n+9 which you can separate as
8*(2n^2+n) +1 and 8*(2n^2+3n+1) +1, so remainder must be 1 :)
Because of the Fundamental Theorem of Arithmetic, if a number can be divided by a composite number (non-prime), then it it can be divided by a prime number. This is because every composite number can be written as a unique product of primes.
So if a number isn't divisible by any primes, it cannot be divisible by any composite numbers either (because then it would be divisible by the prime factors of the composite number).
I really don't understand this proof. I'm probably just missing something; but if this were true, then couldn't you just generate new primes by multiplying the known primes and adding 1? And for example, (2*3*5*7*11*13)+1 creates a number that is not prime and can be a product of the previous prime factors because it can use them more than once, (i.e. 2*2*2*3*etc). Can you help me understand what I'm missing, thanks!
The main assumption of the argument is that there are finitely many primes. Under that assumption, one shows that there must a a new prime that does not exist in this list. Thus, the original assumption is wrong. This DOES not mean you can just make new primes this way because your initial assumption was already wrong, and any conclusions that follows from a flawed premise has no ground to stand on. For instance, 2*3*5*7*11*13+1 = 59*509 is NOT prime.
Albert Renshaw In this problem, we assume that P1, P2, P3... are all *successive* primes, not any random. After a point, we won't be able to generate more primes because the primes we have aren't successive
I was also confused by this part, but I found out why it works. Suppose you have a number divisible by 2,3 and 5. To get the next number divisibile by 2, you need to add 2 to it. To get to the next number divisible by 3, you need to add 3, etc. So if you only add one, your number cannot be divisible by 2, 3 or 5. It can however be divisible by another prime, like 7.
+HTH565 Exactly.
Proof by contradiction works by first making the negation of what you are trying to proof. In this case, there is a finite amount of primes. Then, you use logic to reach a contradiction. Since you have a contradiction, and the reasoning is correct (hopefully!), you can conclude that the initial assumption was false.
Hope it helps.
damn, I forgot to add:
"and every next prime number follows the same rule"
Is it just me or did he split up that 7 line really well?
Alex Gheorghiu I audibly gasped
I had the same proof at the first semester of my studies. ❤
Thank you for being the only person to actually give a detailed response.
Interesting read/review of what I've studied years ago. I disagree with some of your response (or agree with other parts but fail to see how a point has been made).
Since I wish to give you a fair and respectful answer, I will need a lot of time to reply.
I am busy preparing for a trip to the Philippines, and then will be gone much of May, so if I don't reply soon, please don't take it as disrespect or a dodge.
Random question... How do people know that Pi will never end? We know it hasn't ended even after a ridiculous amount of digits, but how is that proof that it never ends? Or do people just assume?
The answer of that is more philosophical than mathematical.
All numbers that we normally use are base on power of 10, so we can always find a 10^-infinity mistake when we measure, and therefore we will have always some mistake in measurement.
In simple words nothing can be precisely measure, because we always be wrong by some 10^-n.
Basically, if pi terminated, it would have to be a rational number. This means it could be written as p/q, where p and q are integers. Further, this means that by using only whole numbers and the basic operations (addition, subtraction, multiplication, division, exponentiation, and rooting), one could devise a series of operations that would equal 0. You are not allowed to multiply by 0, in case you were wondering. Numbers like this are called algebraic numbers. On the flip side, numbers that cannot be reduced to zero are transcendental. Lindemann and Weierstrauss proved that e was transcendental. Then using Euler's Identity and some other theorems, they proved pi was transcendental, therefore irrational, and therefore non-terminating.
see too the proof about the so-called "liouville numbers", know that none algebraic irrational numbers can a liouville number (as square root of 2 and from any integer number; golden ratio, silver ratio, etc, ...) .only transcedental numbers as "pi" and euler number 2.718218183...
i believe having helpwd, right ... ??? goodbye
One can prove that pi is an irrational number. Irrational numbers do not terminate (they have infinitely many digits after the decimal point).
The easiest way to see this is to note that if a number *does* terminate, then it is rational (just write out the base 10 representation and add up all the “places”). So you can write any terminating number as a fraction.
Since pi cannot be written as a fraction, it does not terminate (see “proof by contrapositive”).
Also, some rational numbers do not terminate either, but irrational numbers are especially interesting because they have no repeating pattern in their digits. Another example of an irrational number is the square root of 2.
Good question, but how did it get 44 upvotes before getting an answer?
@@LenilsonCastroFerreira I had a stroke reading that
I sometimes feel so dumb while reading these comments
Just got that version of the Elements
I like the geometric description of primes. I wish there had been a little more geometry in my maths curriculum.
2:40 What about powers of primes? You could take some prime factors of Q to some power, remove others; and have a cocktail of prime factors that, together, divide Q, exactly. 🤔
What about them? The number Q is 1+A*B*C*D*..., where A, B, C, D, ... are finitely many prime numbers. So by construction, Q can't by divisible by any of the primes A, B, C, D, ... . So it must either be a prime, or be divisible by some other prime than A, B, C, D, ... . (We are implicitly using the property that every positive integer has a unique factorization into primes.)
@@MikeRosoftJH I figured out that Q couldn’t be divisible by any combination of those primes, or their powers; because it’s 1 away from a multiple of all of them, and 2 consecutive multiples of n are n away from each other. That could have been said in the video, though. From, what I’ve heard from my Friend, who majored in Maths, at uni, if you were to present this proof shown in the video, and added no more info, in an exam, you would get pretty much 0 marks.
@@MikeRosoftJH I see your point, though. It was just kind of glossed over, in the video.
Math is the coolest thing humans have ever discovered!
It is but sadly very few people could understand it's beauty
Can you have negative primes?
Paul Donovan Depends on the context, but in this case primes are defined as integers greater than 1 divisible only by themselves and 1. In other contexts negative numbers can be prime. My Abstract Algebra text defines a prime element of Z (set of integers) as an element p that isn't zero and if p divides a*b, then either p divides a or p divides b.
***** We're talking about the real number line
Donovan Daoust no
raumaan kidwai not to mention 2
Donovan Daoust Negative integers do not count as prime numbers; only the natural numbers - the positive integers - count as prime numbers.
I'm confused. Why did he add 1?
a prime times a prime can't be a prime
Because otherwise, Q would be divisible by ANY prime number.
It would be P1 x (P2 x P3 x ... Pn) or
P2 x (P1 x P3 x ... Pn) or
P3 x (P1 x P2 x ... Px) and so on ~ all evenly divisible.
By adding the 1, you get a remainder 1 no matter what prime number on the list you try to divide it by. Meaning there must be a prime number not on the list that divides it too.
i was asking the exact same question at first too but it just clicked.
Any number can be made by timesing primes together
In the proof by contradiction they assume that there are a finite number of primes therefore you can created a list
So they have a number say N for example which is made by timesing all the primes together therefore all the primes being a factor of N
But if we add any number it doesn't have to be 1 to N you are not able to make N from the number of primes in the list
Therefore based on the fact that all number can be made up of timesing primes
There must be another prime number which exists
I love how enthusiastic you are about numbers.
Great explanation
"Why is cardinality considered counting until we get to infinity"
...It isn't. It's precisely the same rules going from finite sets to infinite sets.
Euclids Elements: The Bible of Mathematics, only difference, that it is still true and no one has to be killed for it xD
Edgy.
wat. The bible was never true mate
Cabbage
+Spencer Wadsworth yeah, like Pythagoras was put on a boat with no food/water and sent off into the ocean for discovering the first irrational number, which is the square root of 2.
Mr.Champion isn’t it one of his folowers that said we could not measure the square root of 2 ?
I never understand why this is always expressed as a proof by contradiction, which in my opinion only confuses the pupils when first confronted with this.
Just start with any finite set of prime numbers, multiply them all, add one, and thus find a number that can't be divided by any prime on the list, but HAS to either be divisible by a prime (which is then not on the list) or be a prime itself. This shows that no finite set of primes can contain all primes - DONE! There's no need to start with "Suppose there were only finitely many primes."
If you want to "Just start with any finite set of prime numbers," you need to assume this list exists.
Doing this you are doing a proof by contradiction.
I don't think so. I don't assume anything! I don't have to assume the existence of a finit set of prime numbers, because we all KNOW there are finite sets of prime numbers! I start with any finite set of prime numbers and show, that there are prime numbers not in my set. This proves, that no finite set of prime numbers can contain all of them - directly, no contradiction - so there have to be infinitely many of them: DONE (or, traditionally: q.e.d.)!
+karl131058 Thing is that you are only proving there are more primes than exist on your list, not that infinite primes exist. Extending it to other lists still requires you to prove it for those other lists. By assuming that which you set out to prove false, you can make the proof much simpler. "Assume there are finite primes. Then a list of all primes can be made. Using this list a number of the form of Q can be devised. Dividing Q by any prime on my finite list results in a remainder of 1 because of how Q is defined, thus there must be a prime not on my finite list. Thus there aren't finite primes, but infinite primes."
it is a proof by contradiction in that you assume ( mathematically speaking) that a finite set contains them all that's really all the proof this video shows is doing as well it assumes there are n primes it then shows that there has to be an (n+1)th not on the list already.
en.wikipedia.org/wiki/Mathematical_proof
The point pf the proof is that it looks at two things. 1) Q it self is a prime and so the initial list was incomplete. 2) Q isn't prime so it will have to be divisible by a prime. But we can show that it won't be divisble by any of the primes on the list because there will always be a reminder of 1 (which is why we added the 1 in the first place) and that means there are more primes out there that aren't on the list so the list was incomplete. continues...
You're absolutely right. I'm glad I'm not the only one who has seen that. One thing special though about two that doesn't apply to other primes is the fact that it is the smallest prime number.
All right, now that we know that 1+2+3+4+5+6+... = -1/12, and there's an infinite number of primes, what is the sum of all the prime numbers? (2+3+5+7+11+13+17+19+23+29...) :p
+Félix Pinchon in theory you can make an infinite sum. -1/12 for all numbers then that means -n/12 for numbers divisible by n so when we get rid of all the even numbers ( those that divide by two) we get -1/12-(-2/12) = +1/12 add 2 back in and we get +2 1/12 then one third are divisble by 3 so -3/12 but those that divide by 6 have been taken away already because they have 2 as a factor. so add 3/12 because -3/12 -(-6/12) = 3/12 etc. I may be wrong.
There are no pattern. We can calculate sum to the infinity only in patterns.
+Félix Pinchon Let (sum over primes + 1) = x, then x^2 = sum of all numbers with at most two prime factors, because each of these numbers is reached exactly once when multiplying the terms with each other.
So x^n = sum of all numbers with at most n prime numbers, for the same reasoning.
Now take the limit n->infinity, so lim n->infinity = 1+2+3+4+...which we know is equal to -1/12. So x = lim n->infinity (-1/12)^(1/n) = 1.
there you have it, 2+3+5+7+11+13+17+.... = x-1 = 0.
*Insert Trollface here*
1+2+3+4+5+... does not equal -1/12. You are mistaking this for a different infinite sum. Also, there's a difference between converging and diverging series. A converging series comes closer to a certain value over time. For example 1+0.5+0.25+0.125... = 2. On the other hand a diverging series does not approach a specific number over time. 2+3+5+7+11+13+17+19+23+29+31... approaches infinity rather than a specific number.
You might be right about 2+3+5+7+11+13+17+19+23+29+31... approaching infinity, but I'm sure that 1+2+3+4+5... = -1/12 ^^ There's a lot of videos proving this on the internet
Euclid's proof, that there is an infinite number of prime numbers, is saying that "you can always add another to it, because it is infinite" he had a cyclic proof?
that's like me saying the universe is infinite, because if you traveled to the edge of our known universe, you can keep going.
+paonquinho Actually, Euclid's original proof wasn't by contradiction. It's not actually necessary to assume that your initial list contains all primes, as the proof works just as well either way.
NoriMori
how exactly is that stated? If your initial list isn't assumed to be all primes, then the fact that you can get more just implies that there are more than in your original list, not that there are infinitely many. It is a kind of induction?
Joe Alias
"If your initial list isn't assumed to be all primes, then the fact that you can get more just implies that there are more than in your original list"
And since you can keep doing this with any list of primes, there must be infinitely many of them. ;)
NoriMori
Interesting, I see how that works, and yet when I try to explain to myself why that works, I still have to sort of do a proof by contradiction in my head--to say that you can always get more primes than a finite list contains implies that there are also more than in a finite list of all primes, if one were assumed to exist.
I only took one mathematical logic class, so some of this is cloudy.
Biggest prime is infinite!
DanMejerwall Infinite is not a number, and only numbers can be prime.
+RedHairdo I think he meant to say that the biggest prime is never-ending.
infinite divides everything, it's not prime !
Like it is shown in the video there is no such thing as "the biggest prime", so it can't be infinite either.
Things which don't exist can't have any properties.
I don't know why you got thumbs down.. Its really sad that people would thumb down a legitimate and interesting comment. You were curious and you had an idea, neither of these things are bad. So many haters on the web.
Fun fact about this proof:
2 * 3 + 1 = 7, a prime
2 * 3 * 5 + 1 = 31, a prime
2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509
The product of all prime numbers in the interval [a,b] plus one will result in either a prime number that does not belong to that interval or a composite number whose prime factors do not belong to that interval.
I never saw Euclid's proof using geometry. I came up with mine. Neither algebra nor arithmetic is needed.
Suppose distinct segment lengths A, B, and C that can’t be divided into lengths of whole numbers other than the unit segment. Suppose that lines can be a multiple of segments A, B and/or C units only.
Consider such a line XY
X --------------------------- Y
It can be divided in segments A as follows
X --|--|--|--|--|--|--|--|--|-- Y
It can be divided in segments B as follows
X ---|---|---|---|---|---|--- Y
It can be divided in segments C as follows
X -----|------|------|----- Y
Next, extend the length of the line all the way to Z
X -----|------|------|----- Y------------------------------------------------------------------------------Z
Since the assumption is that lines can be a multiple of segments A, B and/or C units only, so too is line XZ. This restricts the possible lengths that XZ can take. To see how, suppose I extend the line XZ by one unit U:
X -----|------|------|----- Y------------------------------------------------------------------------------Z-|
U
Since this is the unit, it can’t be divided into lengths A, B or C. Therefore, line XZU can’t be divided into segments A, B or C. The length XZU constitutes a multiple of a new prime number. This argument applies all the way to infinity. Note that it can't be determined what that prime number is.
You speak of Euclid with such admiration!
This is exactly the sort of thing that there should be a video about!
One of my favorite episodes !
I would like to find this edition of Elements
I am gonna purchase that book right now !
You had a video earlier about the largest documented prime. From this proof you could derive a prime number generating algorithm:
p[n+1] = p[n] * (p[n] + 1)
It produces primes with 1 subtracted from it. So to get the prime just add 1 to p[n].
So far I'm on a prime with 1,707,522 digits after a few minutes of running it. Every prime has roughly 2x more digits but takes 4x longer to compute from the previous prime. This 1.7M prime took 87.1 seconds to calculate from the previous, which took 20
Amazing! You have simultaneously found not only a prime number generating equation, but a Mersenne prime generating equation. This also means that soon we may finally have a proof for infinite perfect numbers.
Even if you multiply the first n primes together and add 1, the result is not guaranteed to be prime. It will necessarily be relatively prime to the first n primes, but that doesn't mean it is prime itself.
Ex: 2*3*5*7*11*13 + 1 = 30031 = 59 * 509
So then we'd have to use additional computing power to try to find any divisors of our result since it wouldn't necessarily be prime.
I'm pretty amazed how easily James divided this line in 7 pieces on first try :P
The way you explained this made it easy to understand. Thanks.
math in a lot of ways seems like the amazing human ability to create a problem then spend eternity trying to solve it
If there is a bijection between two sets A and B then they have the same cardinality. It's just defined by some equivalence relation over sets.
The set S is considered finite with cardinality n if there is a bijection between S and a subset of the natural numbers {0, ..., n-1}. We can biject your set with {0, 1, 2, 3} and hence the cardinality is 4.
He didn't say that Q+1 was a prime number, he said that if it were a prime number it would violate the thinking that there is finite number of primes and therefore proving that primes are infinite. He's simply suggesting it could be prime, while at the same time there's a complete possibility that it's not a prime.
As an example, suppose our "list of known primes" we intended to generate a new prime from was at some point only {2, 3, 5, 7}. We compute the next one as (2*3*5*7) -1 = (210) -1 = 209, which isn't a prime (11*19=209).
I'm now seriously looking forward to a video on the density of prime numbers. :D
The point I've been trying to make to you and everyone else here who disagrees is that you cannot confuse size in the sense of cardinality with size in the sense of actual length of a list. If you wish to list out all the numbers, and while doing this, you start listing primes and non-primes as they appear, once you pass 14, and so on.. your composite list will start to fill up faster than the primes list. We can see from this example that both lists "match up" with x but at different rates.
But you have to agree that 2 does have a little special place in this and other divisibility issues. All you need to see is the last number of a number, doesn't matter how many digits it has, we know instantly if it's divisible by 2 and is even. Of course the same goes with 5. But if the number ends in 1, 3, 7 or 9 we really don't know whether it's divisble by any number until we know the whole number. And it's just how we've defined even and odd. But you're making a good point though.
Not a stupid question at all, but no, your number is the number Q from the video, and at 2:07, James explains that Q may not be prime, but it could be divided by primes that are not on the list. So, we could find new primes by finding the prime factors of Q, but, as you said, at this point Q would be HUGE and finding its prime factors would be nearly impossible (at least with today's tools).
A counterexample: 1*2*4*5*7*11*13+1=30031=59*509 (taken from wikipedia at "Euclid_number")
I didn't state it very well; you're correct that unless the list of primes is complete (which is impossible for the reason given in the video) the product plus or minus one is not guaranteed to be prime (it WILL be prime relative to primes in the list, though).
To clear up what I said Q being a number must be able to be rewritten as a product of prime numbers, in short, the primes listed cant do that because there will always be a remainder of one. Keep in mind that Q is a number greater than the largest prime that's on his list because its made up of multiplying all of his primes and adding one.
The point there is that Q is defined as the product of all primes plus one. That means that Q is either a missed prime or not a number. And it is a number, but not on the list. The +1 came from the very definition of Q.
You might benefit from another numberphile video, "Infinity is bigger than you think".
Suffice to say, it's all about listing. To list my fingers, I can write
thumb
index
middle
ring
pinky
That list is 5 lines long, and each line contains exactly 1 finger (counting my thumb as a finger), so I have 5 fingers. I can put all the fingers into 1 line to make the "list" 1 line long, but that doesn't mean I have 1 finger. I can also put empty lines between fingers, but not have 6 or 7 fingers.
Okay here's the thing why many people have thumbed this down, I didn't. 1) I've lost count how may times this question has been answered on this video's comments. So shouldn't be too much trouble to find out. Obviously he/she didn't know that so he/she didn't know to look for it. 2) He gave 3 example numbers to prove his theory and one of them was wrong. If you're going to prove a point make sure at least your examples are correct. People should pay more attention to what they do.
Maybe I said that a bit prematurely. I'm also not a mathematician, but a physics student (hence I'm not an expert of set theory). Of course you *could* say that there is a difference in numbers of elements in said sets. After all, cardinality is just a definition. You could always make up your own, as long as it is well-defined, clear and works for any kind of set (not just numbers). And if it is helpful (or “better” than current definitions in any way), people might even start using it instead.
More precisely it's that you can't divide Q by any of said primes. "Using that same set of numbers differently" would mean some of them divide Q.
For some prime in the list (say p1) to divide Q, there would have to be some integer k such that Q = p1*p2*...*pn + 1 = k*p1. But if you divide out p1 you get p2*p3*...*pn + (1/p1) = k. Since no numbers but 1 divide 1 and 1 isn't a prime, there's a contradiction, and so no primes in the list divide Q.
Because if Q is not prime, then it must be composed as a product of the prime numbers he listed. Meaning those prime numbers divide Q evenly. Call the list he made "N", so N +1 / P where P is a prime must equal a whole number. For that to be true N/P must be a whole number (which it will be) and 1/P must be a whole as well as fractions with common denominators split (Which is nonsense, a number greater than one will not yield a whole number and one is not prime)
If I understand you correctly, your question is more of "why does 1 make the proof work?" That's a fair question.
Notice that Q - p1p2...pn = 1
We can show that Q isn't divisible by a prime by contradiction too. Suppose Q could be divided by a prime on the list. Say, for instance p1 (you can choose whichever prime you want, not just p1).
So if p1 divides Q, then Q = p1 * r for some integer r.
So p1(r - p2p3...pn) = 1
This means that p1 divides 1, but no prime divides 1, a contradiction.
I was dissatisfied with "by a factor of about 6" so I did something similar by using the prime number theorem to approximate the number of primes from 1 to 10^n and then from 10^n to 10^(n+1), and took the ratio of those. You end up canceling a bunch of logs and 10^ns and get (9n+1)/(n+1). Approaching infinity, you get nine times more primes between 10^n and 10^(n+1) than below 10^n. Naturally, the ratio of the number of primes up to 10^(n+1) to the number up to 10^n ends up (10n+1)/(n+1).
You have to add/say/remind that any interger can be decomposed into prime factors, otherwise one might say that Q could be divisible 10, like 3*3+1. But since 10 is 2*5 10 divides P1*P2*...*Pn etc...
i agree, i absolutely despise the sound of a sharpie writing on paper. to me, it's almost as bad as someone scratching on a blackboard. but still i keep coming back to numberphile
this channel is soooo cool
It is possible... but that is not a sure way of doing it because it doesn't always work: 2*3*5*7*11*13 + 1 = 30031 = 59*509 (so not prime), but if you stop at 11, 2*3*5*7*11 + 1 = 2311 (prime).. so sometimes it works, sometimes it does not.
1) when you do that you aren't guaranteed that the new number is prime, but it must have a prime as a factor that you haven't listed. however factoring numbers is generally hard.
2) 111 = 3*37, 1111=11*101, 11111=47*271.
No, Q isn't necessary a prime but it might be. What is true is that Q won't be divisible by any of the primes in the list but that doesn't guarantee that it's prime itself. It may be a product of two or more unknown primes that are bigger than the biggest prime on our list.
this is why the term "complete list" is important.
lets say the complete list is 2 3 5 7 11 and 13, technically adding 1 would add a new number to the list BUT we know there is more to the list because that number is not prime. the question asked is the proof of the answer ;) assuming that adding 1 creates a new number means the list must be expanded.
Do you mean to take an odd number of "just some primes" or the complete list of primes until a biggest one (so far)? Because if you take the complete list from P_1 to P_n you'll have the first prime, namely the number 2, in that list. And if you multiply all together, the new number (Q - 1) = P_1 * P_2 * ... * P_n will be even and Q will be odd.