Proof that there are infinitely many prime numbers
- Get link
- X
- Other Apps
Hello everyone. Today we will prove that there are infinitely many prime numbers. This proof was first performed by the Greek mathematician Euclid.
Theorem: There are infinitely many prime numbers.
Proof:
Suppose there is a finite number of prime numbers. Let us denote the number of prime numbers by \(n \), and the prime numbers themselves by \(p \) and the indices \(1,2 \ldots, n-1, n \). So we have a finite set of primes \(p_1, p_2, \ldots, p_{n-1}, p_n \).
Now, we construct the number \(q \) as follows: \[q = p_1 \cdot p_2 \cdot \ldots \cdot p_ {n-1} \cdot p_n + 1 \] Then \(q \) can be either prime or a composite number. It is clear that \(q \) cannot be a prime number because we assumed that the number of primes is finite and that the largest prime number is the number \(p_n \). Therefore, \(q \) must be a composite number. If \(q \) is a composite number then there is some prime number \(p \) from the set \(p_1, p_2, \ldots, p_{n-1}, p_n \) that divides it. Denote by \(P \) product \(p_1 \cdot p_2 \cdot \ldots \cdot p_{n-1} \cdot p_n \). Then \(p \) simultaneously divides both \(P \) and \(P + 1 = q \) which means that \(p \) must also divide the difference \((P + 1) -P \), i.e. it follows that \(p \) divides the number \(1 \). But since no prime number divides the number \(1 \) we conclude that \(p \) cannot be in the set \(p_1, p_2, \ldots, p_{n-1}, p_n \). This means that no matter what the number \(n \) is, there is always at least one more prime number outside the finite set, therefore there are infinitely many prime numbers.
\(\blacksquare \)
- Get link
- X
- Other Apps
Comments
Post a Comment