How do we know there are an infinite number of prime numbers? How do we know that once you get to a certain point, they don’t all end up as composite numbers?
In: Mathematics
Proof by contradiction.
Assume you have a list containing every single prime number.
Multiple all those numbers together to get a very large number. Add 1 to that number to get a new number we’ll call C.
C cannot be divided by any of the prime numbers on your list, so it must not be composite. But it has to be composite because it isn’t on your list. That’s a contradiction. C can’t be composite but it has to be composite.
Because the assumption created a contradiction, the assumption must be wrong. You cannot in fact have a list of all the prime numbers.
Because you can mathematically prove it.
Let’s say there is a finite number of prime numbers.
If you multiple all of them together, then add 1, it would be undividable by any of the prime number used to make that number, which means that number is either prime, or it is dividable by another prime that wasn’t used to make that number up, which means you didn’t have all the prime numbers, which is a contradiction.
Good question, and one with a relatively straightforward answet/proof! Let’s assume that there is a “biggest prime number.” That means I could create a composite number by multiplying ALL the prime numbers together (if there’s a biggest one, then the number of primes is finite).
This number is kind of the MOST composite number. It’s divisible by EVERY prime number by definition. So… what happens if we add 1 to it?
Now, the remainder when we divide by a prime number will be 1. That makes this “big number + 1” unable to be divided by any prime, and that means it must be prime itself… but this prime is bigger than the biggest prime number (thanks to the multiplication), which makes this a logical contradiction.
Contradictions don’t exist in well-defined systems, so the issue must be our initial assumption: that there actually is a “biggest prime number.” Hence the primes go on forever because if they didn’t, we’d have an impossible situation on our hands!
Simple mathematical proof by contradiction.
Assume that there are a finite number of prime numbers. Then by definition, there is a largest prime, and every number larger than the largest prime is divisible by at least two of the primes.
Construct the number (N say) formed by multiplying all the primes together, then adding one. N is bigger than all the primes, but is not divisible by any of them. Contradiction.
Therefore our assumption that there are a finite number of primes is wrong.
There is a proof, and it takes advantage of the fact that a number is either prime, or a result of multiplying primes together. One of those two statements is always true.
So…
If there *was* a last prime, then you can count them and collect them. With that collection, multiply them ALL together.. 2 * 3 * 5 * 7 * 11 * 13 * and so on and so forth up to that last prime. Now take this result and then add 1.
What is this new number? It can’t be prime, it’s obviously *way* bigger than the biggest prime that exists after all. It also can’t be composite because that +1 on the end made it not divisible by any prime number that exists since we just used *all of them*. But it’s also a valid number in that all I’ve done is multiply a bunch of times (but not infinitely many) and then added 1. That’s normal math.
This number we invented cannot exist because it violates other established rules. We call this a contradiction because we’ve said that something is both true and false at the same time (in this case, the true statement is from what I said in the first paragraph). Therefore we have made a mistake in our assumptions, and the last assumption we made was wrong. Flip it around. Our last (and only) assumption was that there was such a thing as a last prime, so that is wrong. Therefore, there are infinite primes.
Latest Answers