Euclid Proof of Infinite Primes

  • Thread starter Pupil
  • Start date
  • #1
124
0

Main Question or Discussion Point

Near the end of Euclid's proof he says that if you multiply all our known primes from 2 to Pn and then add 1 to it, the number isn't divisible by any of our primes up to Pn, because it leaves the remainder 1. Why is that? How does he know that it will always leave the remainder 1? Couldn't adding 1 just make a slightly larger number that has a factor that might be 2 or Pn? If someone can set my stoopid brain straight I'd be very happy. Thanks.
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
We have that 2,..,p_n is a supposed list of all primes and we have constructed

2*3*..*p_n+1

By construction it is one more than a multiple of any known prime (i.e. 2,..,p_n).

Or, let me put it this way, I have something that is a multiple of 2, and I add one to it. Is the result a multiple of 2?
 
  • #3
124
0
We have that 2,..,p_n is a supposed list of all primes and we have constructed

2*3*..*p_n+1

By construction it is one more than a multiple of any known prime (i.e. 2,..,p_n).

Or, let me put it this way, I have something that is a multiple of 2, and I add one to it. Is the result a multiple of 2?
No, as far as I can tell by doing a few examples in my head. I can maybe see how 2n + 1 never yields a multiple of 2 since 2n is always even, and adding 1 makes it odd, thereby making it indivisible by 2. Your multiple of 2 example is really simple, so I can see easily how to prove that result, but I don't see how it is known that multiplying all the primes and adding 1 constructs a number such that it isn't a multiple of any known prime.
 
  • #4
124
0
To kind of clarify the problem I'm having: how do we know kn+1 is not divisible by k or any of the factors that make up k?
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,794
925
Because if you divide kn+ 1 by k you get a quotient of n with remainder 1.
 
  • #6
CRGreathouse
Science Advisor
Homework Helper
2,820
0
To kind of clarify the problem I'm having: how do we know kn+1 is not divisible by k or any of the factors that make up k?
Because kn is divisible by k (leaving a remainder of 0), so one more than that would leave a remainder of 1.
 
  • #7
112
0
[tex]\frac{kn+1}{k}=n+\frac{1}{k},[/tex]

where n is an integer.

If p is a factor of k, then

[tex]\frac{kn+1}{p}=n'+\frac{1}{k},[/tex] where n' is an integer.
 
  • #8
290
2
To kind of clarify the problem I'm having: how do we know kn+1 is not divisible by k or any of the factors that make up k?
perhaps it would be easier to see it this way: if you cycle through the integers, a multiple of k will appear ever k integers starting with 0 then k then 2k, 3k, etc. If P is the product of all known primes, then it is divisible by every prime, so in order to get a number that's divisible by any factor of P (ie any prime) you need to add at least 2 (the smallest prime) but 1>2 so [tex]2\not| P[/tex]
 

Related Threads for: Euclid Proof of Infinite Primes

Replies
3
Views
1K
Replies
2
Views
208
Replies
3
Views
2K
Replies
9
Views
6K
  • Last Post
Replies
8
Views
3K
Replies
1
Views
2K
  • Last Post
Replies
7
Views
8K
Replies
16
Views
4K
Top