Register to reply

The infinity of primes

by kenewbie
Tags: euclid proof primes
Share this thread:
kenewbie
#1
Jan21-10, 06:27 AM
P: 236
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
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
HallsofIvy
#2
Jan21-10, 06:36 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,323
Because dividing by any of those primes gives a remainder of 1, not 0:

[tex]\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}[/tex]
The first term is an integer but the second is not.
Hurkyl
#3
Jan21-10, 12:34 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,099
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".

Hurkyl
#4
Jan21-10, 12:35 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,099
The infinity of primes

Quote Quote by kenewbie View Post
How can I know this?
Try dividing.
kenewbie
#5
Jan22-10, 07:54 AM
P: 236
Quote Quote by HallsofIvy View Post
[tex]\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}[/tex]
The first term is an integer but the second is not.
That made perfect sense, thank you!

k


Register to reply

Related Discussions
Pythagorean Primes and Gaussian Primes, divisibility question Linear & Abstract Algebra 3
A Definite integral where solution. involves infinity - infinity Calculus & Beyond Homework 8
A Definite integral where solution. involves infinity - infinity Calculus & Beyond Homework 3
Integral of a delta function from -infinity to 0 or 0 to +infinity Quantum Physics 31
Limits As X Approaches Infinity and Negative Infinity Calculus & Beyond Homework 15