3

Proposition: The Prime Numbers Set is infinite.

Proof: Suppose we have a finite set of prime numbers $p_{1}, p_{2}, ..., p_{n}$ such that $p_{n}$ is the largest of them.

Define $ c := p_{1}*p_{2}*...*p_{n}$

$c$ is clearly not prime.

Let $q = c + 1$ such that q is not divisible by $ p_{k} $ or other element of the set since 1 is not divisible by them.

Then $q$ is by itself a prime number or it is divisible by a prime number greater than $p_{n}$. That is not possible, since $p_{n}$ is the largest prime number. Contradiction!

Q.E.D.

Guilherme Duarte
  • 365
  • 1
  • 2
  • 17
  • 2
    Just sit back and wait for someone to point out that Eulid's proof is not really by contradiction... – Winther Aug 23 '14 at 23:42
  • 2
    The fact that $c$ is not prime is irrelevant, don't mention it. It is fine to say let $q=c+1$. The "such that" is confusing. You need to prove that $c$ is not divisible by any of the $p_i$, $1\le i\le n$. You have, more or less, but could be more explicit. The fact that $q$ is divisible by a prime greater than $p_n$ is not important. What is important is that it is divisible by a prime other than the $p_i$. – André Nicolas Aug 23 '14 at 23:43
  • Try $P = {2,7}$. – NovaDenizen Aug 24 '14 at 00:27
  • One small mistake: The $q$ you constructed is not necessarily divisible by a prime bigger than $p_n$. All you know is that it's divisible by a prime which is not on your list! – Alex G. Aug 24 '14 at 02:22
  • Thanks, now i understand what is wrong with my proof. – Guilherme Duarte Aug 24 '14 at 19:02

2 Answers2

1

Hint: http://en.wikipedia.org/wiki/Euclid's_theorem#Euclid.27s_proof

user153012
  • 12,240
0

The proof is technically correct, but it lacks clarity, much like many other proofs I have read.

Suppose the list of primes is finite and denoted as $\{p_1, p_2, ..., p_n\}$. Now define:

$q = p_1 \times p_2 \times ... p_n + 1$.

If $q$ is a prime number, then it is certainly not in the list, which contradicts our assumption that the list of primes is finite.

If $q$ is not a prime number (thus a composite number), it must have prime factors. However, these prime factors cannot be any of the primes in the list, because dividing $q$ by any of them would always yield a remainder of $1$, as shown below:

$q = (p_1 \times p_2 \times ... p_{i-1} \times p_{i+1} \times ... p_n) \times p_i + 1$

This, again, contradicts our assumption. Q.E.D.

Ari Royce Hidayat
  • 993