Solution 1: There are an infinite number of prime numbers
Here is the solution to Problem 1: Prove that there are an infinite number of prime numbers.
Note: The argument makes use of proof by contradiction. If you are not familiar with this type of argument, a tutorial can be found here and you can watch a video here.
Claim: There are an infinite number of prime numbers.
(1) Assume that there are only a finite number of prime numbers.
(2) Let $x$ be the largest such prime.
(3) It follows that $x!$ is divisible by all primes.
Note: $x!$ is the factorial for $x$. If you are not familiar, you can learn about factorials here or see a video here.
(4) But then, no prime divides $x! + 1$ since all such divisions will have a remainder of 1.
(5) Thus, we have a contradiction and can reject our assumption in step 1.
Either $x!+1 > x$ is a prime itself (which contradicts our assumption in step 1 that $x$ is the largest prime number) or $x!+1$ is composite and divisible by a prime number greater than $x$ (which also contradicts this same assumption in step 1).
Comments
Post a Comment