# Trouble understanding proof- infinitely many primes?

I'm having trouble with this proof: Prove that there are infinitely many prime numbers, using proof by contradiction. My teacher gave it to us the first day of class, but I'm a little lost:

Assume there are finitely many prime number,
P1, P2, P3,.....,Pn.

Let q=(P1*P2*P3*.....*Pn)+1

Then, for all 1≤i≤n, Pi does not divide q, so therefore there must be at least Pn more prime, Pn+1.

Here we reach a contradiction since we assumed there were only n primes. Therefore our assumption is in error and there are infinitely many primes. #

I don't understand the portion in red. Can anyone please explain it in simple terms?

Thanks.

vela
Staff Emeritus
Homework Helper
What part do you specifically not understand? That pi doesn't divide q?

It just means that based on how q is defined (all n primes multiplied, then one added) there is no prime that can divide q.

This suggests that p is either a prime itself or is not composed of prime factors.

The second case is impossible, and the first contradicts our claim of there being only n primes.

SammyS
Staff Emeritus
Homework Helper
Gold Member
I'm having trouble with this proof: Prove that there are infinitely many prime numbers, using proof by contradiction. My teacher gave it to us the first day of class, but I'm a little lost:

Assume there are finitely many prime number,
P1, P2, P3,.....,Pn.

Let q=(P1*P2*P3*.....*Pn)+1

Then, for all 1≤i≤n, Pi does not divide q, so therefore there must be at least Pn more prime, Pn+1.

Here we reach a contradiction since we assumed there were only n primes. Therefore our assumption is in error and there are infinitely many primes. #

I don't understand the portion in red. Can anyone please explain it in simple terms?

Thanks.

Then, for all 1≤i≤n, Pi does not divide q, so therefore there must be at least Pn more prime, Pn+1.
you could expand this a little and say

Then, for all 1 ≤ i ≤ n, q ≡ 1 (mod Pi). Thus, Pi does not divide q, so therefore there must be at least one more prime, Pn+1.

I'm not sure how convincing this is, but maybe this will make it clear:

Let
$k = x_{1}x_{2}....x_{n}$ and $x_{i} =/= 1$

In other words, k equals a bunch of numbers multiplied, and we aren't letting any of them be one (because they have no effect on the value of k.)

Now consider k + 1.

$k + 1 = x_{1}x_{2}....x_{n} + 1$

Now lets assume that $k + 1$ is divisible by some $x_{i}$.

Then, there exists some integer $l$ such that $x_{i}l = k + 1$

Then $l = \frac{k}{x_{i}} + \frac{1}{x{i}}$

But this doesn't make sense. $\frac{k}{x_{i}}$ is guaranteed to be an integer because we know that k is divisible by $x_{i}$, and $\frac{1}{x_{i}}$ is guaranteed to not be an integer, because it is the reciprocal of some non-one number.

So, adding them together is guaranteed not to be an integer.

Therefore, there isn't a single $x_{i}$ that divides $k+1$.