Euclid's Proof: Infinity of Primes

  • Context: Undergrad 
  • Thread starter Thread starter kenewbie
  • Start date Start date
  • Tags Tags
    Infinity Primes
Click For Summary

Discussion Overview

The discussion revolves around Euclid's proof of the infinitude of primes, specifically examining the reasoning behind the assertion that a number constructed from the product of all known primes plus one cannot be divisible by any of those primes. The scope includes mathematical reasoning and conceptual clarification.

Discussion Character

  • Mathematical reasoning
  • Conceptual clarification

Main Points Raised

  • One participant questions why the number X, defined as the product of all known primes plus one, cannot be divided by any of those primes, expressing uncertainty about this aspect of the proof.
  • Another participant explains that dividing X by any prime results in a remainder of 1, indicating that it cannot be divisible by those primes.
  • A third participant comments on the grammatical phrasing of "the infinity of primes," suggesting that "infinite" would be more appropriate.
  • A participant reiterates the explanation regarding division, confirming their understanding after the clarification.

Areas of Agreement / Disagreement

Participants appear to agree on the mathematical reasoning behind the divisibility argument, though there is a noted disagreement regarding the grammatical phrasing of the thread title. The initial question about the proof remains open, as it reflects a participant's uncertainty.

Contextual Notes

The discussion includes assumptions about the properties of prime numbers and division, which are not explicitly stated. The grammatical critique does not impact the mathematical content but highlights a potential misunderstanding in terminology.

Who May Find This Useful

This discussion may be useful for individuals interested in number theory, particularly those exploring foundational proofs regarding prime numbers and their properties.

kenewbie
Messages
238
Reaction score
0
Euclid's proof:

1) Assume there is a finite number of primes.
2) Let Pn be the largest prime.
3) Let X be the P1 * P2 ... * Pn + 1

At this point the statement is that "X cannot be divided by P1 through Pn", but why is that? This is not self-obvious to me. How can I know this?

k
 
Mathematics news on Phys.org
Because dividing by any of those primes gives a remainder of 1, not 0:

\frac{P_1P_2...P_{i-1}P_iP_{i+1}...Pn+ 1}{Pi}= P_1P_2...P_{i-1}P_{i+1}...Pn+ \frac{1}{P_i}
The first term is an integer but the second is not.
 
Minor aside: "the infinity of primes" is bad grammar. The noun form is wrong here -- you want the adjective "infinite", such as in "the infinite set of primes".
 
kenewbie said:
How can I know this?
Try dividing.
 
HallsofIvy said:
\frac{P_1P_2...P_{i-1}P_iP_{i+1}...Pn+ 1}{Pi}= P_1P_2...P_{i-1}P_{i+1}...Pn+ \frac{1}{P_i}
The first term is an integer but the second is not.

That made perfect sense, thank you!

k
 

Similar threads

  • · Replies 10 ·
Replies
10
Views
3K
  • · Replies 0 ·
Replies
0
Views
3K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 24 ·
Replies
24
Views
3K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 8 ·
Replies
8
Views
4K
  • · Replies 16 ·
Replies
16
Views
3K