Infinite Primes - Numberphile
ฝัง
- เผยแพร่เมื่อ 22 เม.ย. 2013
- How do we know there are an infinite number of primes?
More links & stuff in full description below ↓↓↓
Dr James Grime explains, with a bit of help from Euclid.
Follow James at / jamesgrime
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Patreon: / numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/stores/numberphile
Other merchandise: store.dftba.com/collections/n... - วิทยาศาสตร์และเทคโนโลยี
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!
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
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.
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 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.
Grime´s enthusiasm for mathematics makes me enthusiastic about mathematics!
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.
This proof made so much sense. Thank you.
"math is the search of truth" is the most beautiful thing
I love Dr. Grime's enthusiasm for his field of study. ^^
Thanks for your reference to Euclid's Elements, after watching this video, I purchased the book and it's brilliant.
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.
@@barrykendrick3146 sure but back then 1 was not even considered a number but as a concept like infinity or zero (placeholder 0).
+@@hassanakhtar7874 Quite the contrary: 1 was the first number.
Yeah it's so clever
To host, thank you for sharing the book.Really interesting series of topics on math, very much appreciated.
This is very well explained. Thanks Brady and Dr. Grimes!
Loved this, a specific book reference re: Euclids Elements would be great!
The way you explained this made it easy to understand. Thanks.
I love how enthusiastic you are about numbers.
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.
Such fun videos
You speak of Euclid with such admiration!
this channel is gold
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?!?!
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.
One of my favorite episodes !
I would like to find this edition of Elements
This videos are SO GREAT
It took me a couple rewatches to understand that proof, but now that I do, I see why you called it elegant!
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
What? That's not what's happening here. If you factor 209, you still find primes that weren't on the list.
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?
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
6:03 All these years and I've never heard of a geometric definition of a prime before. Very nice.
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!
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
I am gonna purchase that book right now !
I love coming back to this video from time to time. For the first time I saw an Abacus in the background. Perhaps a Numberphile Abacus video is in order?!
James should upload a skin care routine! His skin is amazing!
Translations:
Ashume -> Assume
Noombar -> Number
Drawring -> Drawing
hhhh you aAAA funny ,
Lol
The'ee should be mooo translations xD
Enlightenment *Noombah
cohld = called
I'm now seriously looking forward to a video on the density of prime numbers. :D
Thank you that was very well done!
damn, I forgot to add:
"and every next prime number follows the same rule"
Just got that version of the Elements
This is exactly the sort of thing that there should be a video about!
Great video - thanks!
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
Just realized I'm watching Numberphile instead of studying for my math final exam. Oh well
Truly Amazing!!!
I like the geometric description of primes. I wish there had been a little more geometry in my maths curriculum.
Is it just me or did he split up that 7 line really well?
Alex Gheorghiu I audibly gasped
5:13 11 is also a prime.......just sayin’
I don't get it
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.
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.
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
"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.
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.
useful explanation. it help me in my school maths journal.
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.
Math is the coolest thing humans have ever discovered!
It is but sadly very few people could understand it's beauty
First line was replying to (and agreeing with) you.... then I got distracted by Tietna's stupid and wandered off the plot. You're doing a great job explaining.
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 :)
There's Sb, As, Al, Se, and H2, O2, N2, Re...
H,He,Li,Be,B,C,N,O,F,Ne,Na,Mg,Al,Si,P,S,Cl,Ar,K,Ca,Sc,Ti,V,Cr,Mn,Fe,Co,Ni,Cu,Zn,Ga,Ge,As,Se,Br,Kr,Ru,Sr,Y,Tb, or something along those lines for symbols. ... I used to know most of the symbols as well as the names ( admittedly probably not pronounced properly.
***** I was singing 'The Elements'.
These are the only ones of which the news has come to Harvard - there may be many others but they haven't been discarvered.
Everything from Lawrencium onwards was discovered after Tom Lehrer wrote the song I believe.
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
Can you make more videos with James? Please?
Thank you very much!
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.
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'm pretty amazed how easily James divided this line in 7 pieces on first try :P
Thank you!
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
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 would love to see that video made!
Thanks for the reply!
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.
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
loving numberphile
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).
can't wait for the sequel to Euclid's Elements: Keter's Elements
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
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).
this channel is soooo cool
Comparing prime with a line segment: mind blown 💥
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.
Wow the best proof ever so elegant
exactly, i think it's a fascinating concept :)
Succinct and clear - thanks!
It's really great...
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.
ahhhh the teasers at the end!!!
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.
Well that thought might be the most important thought that ever occured when we first found primes and why we started studying them. And as you saw in this video that there are infinitely many of them we just don't know how to find them yet.
Thanks for coming into kingsmead
Hello, there! Can you make a video explaining idoneal numbers? The internet is quiet minimal regarding this topic.
looking forward to next video
Thanks! I didn't realized that
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.
I thought about this proof myself and I'm very proud of myself now.😃
Bravo!
great video! i was wondering if you all could do a video on modular arithmetic, especially on how to use it to solve the "Decimation" problem - 1000 soldiers are lined up in a circle with every 10th one killed. The last soldier standing may live. Where would you want to stand to be the last soldier?
I had the same proof at the first semester of my studies. ❤
Beautiful proof !!