I am currently working on a problem in which I must prove that there exists a larger number prime number than prime $P$, the largest prime of a finite set.

Here are a list of considerations:

  • There is a finite amount of primes
  • $P$ is the largest prime in the finite set
  • $x$ = $P!$
  • $y$ = $x$ + 1 (A number larger than the largest prime)

Here is how I went about proving that there exists a larger prime number than $P$:

Since $P$ is the largest prime in the set, we assume that there are no primes greater than it. The variable $y$ must have a prime factor due to the Fundamental Theorem of Arithmetic. This prime factor must belong to the set of finite primes. Since $x$ = $P!$, this prime factor must also be a multiple of $x$ since $x$ is equivalent to $P!$, it is a product.

Therefore, since this prime factor is a multiple of both $x$ and $y$, it must also be a multiple of their difference. However $y - x = (x + 1) - x = 1$, so this is impossible. This implies that there exists a prime factor that does not belong to the finite set, which means that there are an infinite number of primes.

Since there are an infinite number of primes, there must exist a larger prime than prime $P$, the "largest" prime.

Does this make sense? Is there a better way I could state or write this proof? By proving that there is an infinite number of primes, we know that there exists a larger prime.

But how could I find the prime that is just ever so slightly larger than $P$?

  • $\begingroup$ The proof by Archimedes just constructs a new prime which is larger by $1 + \prod_1^n p_i$, but not necessarily the next prime number after $p_n$ (considered the $p_i$ are sorted ascending). $\endgroup$ – mvw Jan 9 '16 at 2:45

Let $\{p_1,...,p_n\}$ the set of primes inferior or equal to $P$, $N=p_1....p_n+1$ is the product of prime numbers and is relatively prime with $p_i, i\leq n$. A prime number which divides $N$ is strictly superior to $P$.

  • $\begingroup$ Thank you, that helped a lot. $\endgroup$ – TheLongDark Jan 9 '16 at 2:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.