• Support PF! Buy your school textbooks, materials and every day products Here!

Trouble understanding proof- infinitely many primes?

  • Thread starter SMA_01
  • Start date
  • #1
218
0
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.
 

Answers and Replies

  • #2
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,538
1,150
What part do you specifically not understand? That pi doesn't divide q?
 
  • #3
1,331
45
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.
 
  • #4
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,226
951
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, 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.
 
  • #5
1,331
45
I'm not sure how convincing this is, but maybe this will make it clear:



Let
[itex]k = x_{1}x_{2}....x_{n}[/itex] and [itex]x_{i} =/= 1[/itex]

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.

[itex]k + 1 = x_{1}x_{2}....x_{n} + 1[/itex]

Now lets assume that [itex]k + 1[/itex] is divisible by some [itex]x_{i}[/itex].

Then, there exists some integer [itex]l[/itex] such that [itex]x_{i}l = k + 1[/itex]

Then [itex]l = \frac{k}{x_{i}} + \frac{1}{x{i}}[/itex]

But this doesn't make sense. [itex]\frac{k}{x_{i}}[/itex] is guaranteed to be an integer because we know that k is divisible by [itex]x_{i}[/itex], and [itex]\frac{1}{x_{i}}[/itex] 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 [itex]x_{i}[/itex] that divides [itex]k+1[/itex].
 

Related Threads for: Trouble understanding proof- infinitely many primes?

Replies
0
Views
1K
Replies
1
Views
566
Replies
4
Views
2K
Replies
3
Views
4K
Replies
2
Views
2K
Replies
7
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
2K
Top