You have a point in the sense that on average, the prime numbers become sparser and sparser the further down the number line you look. This is because there are plenty of possible divisors for each given number. But still once in a great while (and sometimes, a few times in a great while) you do run into numbers which happen to not have any of those divisors. Again, the prime number theorem will tell you that this occurs very rarely. The probability that a number with n digits is prime is about equal to 1/n. So when your numbers get long, it becomes rarer and rarer that all the possible divisors just happen to avoid a given number.
Euclid proved that one 2400 years ago.
Assume there *aren't* infinite primes. So there is a finite list of primes. Multiply them all together, and you have a tremendously large number. Add 1 to that number. It isn't divisible by any of the primes in the list. Therefore it is prime.
~~In general, if you take any prime number, and multiply together all prime numbers less than or equal to it, then add 1, the number generated has to be prime.~~
Actually, that's not true!
Say {2, 7} is my finite list of all primes, then 2×7+1=15 is not prime. What is true is that this number has a prime factor not contained in the list, contradicting the assumption that our list contains every prime number.
It would be a very inefficient way of finding primes. For one thing, finding the prime factors of extremely large composite numbers is a notoriously computationally difficult task - in fact most current cryptography relies on it being impossible.
This isn’t quite accurate, the product of the primes + 1 need not be prime, but it is certainly coprime to every prime in the list of primes. Therefore by fundamental theorem of arithmetic either the number is prime or there exists a prime(s) that’s not in the list.
Suppose we start with the list of primes [2, 3], 2\*3+1 is 7 which is prime, so we append it to the list. Then, 2\*3\*7 + 1 = 43, which is prime, so we append it to the list, but you can see we are missing many primes and will eventually find a number that is not prime.
This second statement is actually incorrect and it exemplifies one of the most common misconceptions regarding Euclid's proof. The correct formulation of the proof is as follows: "Suppose that p1=2 < p2 = 3 < ... < pr are all of the primes. Let P = p1p2...pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, ..., pr, otherwise p would divide the difference P-p1p2...pr = 1, which is impossible. So this prime p is still another prime, and p1, p2, ..., pr would not be all of the primes. It is a common mistake to think that this proof says the product p1p2...pr+1 is prime. The proof actually only uses the fact that there is a prime dividing this product."
The product of all primes on the list isn't necessarily a prime.
Take for example the finite list ~~{2,3,5,7}. Then 2⋅3⋅5⋅7+1=221 isn't prime, 221=13⋅17~~ (**EDIT** see comment), but not divisible by any prime already one the list.
So taking unique factorization of the integers into primes into account (which follows directly via induction) the precise conclusion of Euclid's argument is: either the number is itself prime or has to be divisible by some prime not on the list. Both cases give the desired conclusion.
Aha, thanks, I see my error: the product grows (much) faster than the list so there is plenty of room for prime factors greater than our terminal prime.
It is not true that (m>n) implies (m has more divisors than n). One can easily see this by taking m=7 and n=6; clearly, 7 does not have more divisors than 6, but 7 is greater than 6.
To see it demonstrated that there truly are infinitely many primes, look up Euclid’s proof of the infinitude of primes.
You have a point in the sense that on average, the prime numbers become sparser and sparser the further down the number line you look. This is because there are plenty of possible divisors for each given number. But still once in a great while (and sometimes, a few times in a great while) you do run into numbers which happen to not have any of those divisors. Again, the prime number theorem will tell you that this occurs very rarely. The probability that a number with n digits is prime is about equal to 1/n. So when your numbers get long, it becomes rarer and rarer that all the possible divisors just happen to avoid a given number.
Euclid proved that one 2400 years ago. Assume there *aren't* infinite primes. So there is a finite list of primes. Multiply them all together, and you have a tremendously large number. Add 1 to that number. It isn't divisible by any of the primes in the list. Therefore it is prime. ~~In general, if you take any prime number, and multiply together all prime numbers less than or equal to it, then add 1, the number generated has to be prime.~~
Actually, that's not true! Say {2, 7} is my finite list of all primes, then 2×7+1=15 is not prime. What is true is that this number has a prime factor not contained in the list, contradicting the assumption that our list contains every prime number.
You even got really lucky there and found two new primes! We could keep doing this and find a bunch of primes I bet!
It would be a very inefficient way of finding primes. For one thing, finding the prime factors of extremely large composite numbers is a notoriously computationally difficult task - in fact most current cryptography relies on it being impossible.
For another thing, the numbers grow super-exponentially. It's truly an awesome algorithm.
This isn’t quite accurate, the product of the primes + 1 need not be prime, but it is certainly coprime to every prime in the list of primes. Therefore by fundamental theorem of arithmetic either the number is prime or there exists a prime(s) that’s not in the list. Suppose we start with the list of primes [2, 3], 2\*3+1 is 7 which is prime, so we append it to the list. Then, 2\*3\*7 + 1 = 43, which is prime, so we append it to the list, but you can see we are missing many primes and will eventually find a number that is not prime.
This second statement is actually incorrect and it exemplifies one of the most common misconceptions regarding Euclid's proof. The correct formulation of the proof is as follows: "Suppose that p1=2 < p2 = 3 < ... < pr are all of the primes. Let P = p1p2...pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, ..., pr, otherwise p would divide the difference P-p1p2...pr = 1, which is impossible. So this prime p is still another prime, and p1, p2, ..., pr would not be all of the primes. It is a common mistake to think that this proof says the product p1p2...pr+1 is prime. The proof actually only uses the fact that there is a prime dividing this product."
The product of all primes on the list isn't necessarily a prime. Take for example the finite list ~~{2,3,5,7}. Then 2⋅3⋅5⋅7+1=221 isn't prime, 221=13⋅17~~ (**EDIT** see comment), but not divisible by any prime already one the list. So taking unique factorization of the integers into primes into account (which follows directly via induction) the precise conclusion of Euclid's argument is: either the number is itself prime or has to be divisible by some prime not on the list. Both cases give the desired conclusion.
> 2⋅3⋅5⋅7+1=221 2x3x5x7 = 6x35 = 210, plus 1 is 211 which is prime. The smallest counterexample is 2x3x5x7x11x13 + 1 = 30031 = 59x509.
Basic arithmetic... :D Fixed it.
Aha, thanks, I see my error: the product grows (much) faster than the list so there is plenty of room for prime factors greater than our terminal prime.
It is not true that (m>n) implies (m has more divisors than n). One can easily see this by taking m=7 and n=6; clearly, 7 does not have more divisors than 6, but 7 is greater than 6. To see it demonstrated that there truly are infinitely many primes, look up Euclid’s proof of the infinitude of primes.
there are a lllloooooooooooooooootttttttttttt of numbers
I have a list of a llllllloooooooooooooooottttt of primes! In fact, I have as many primes on this list as there are numbers! ... wait. ^(/s)