Trouble understanding proof- infinitely many primes?

[SMA_01]

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]

What part do you specifically not understand? That p_i doesn't divide q?

 

[1MileCrash]

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]

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.

Instead of saying

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

you could expand this a little and say

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

 

[1MileCrash]

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 let's 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$.