My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Thanks Tree3Thanks
  • 1 Post By Maschke
  • 1 Post By skipjack
  • 1 Post By JeffM1
Reply
 
LinkBack Thread Tools Display Modes
September 2nd, 2018, 07:54 AM   #1
Member
 
Joined: Sep 2014
From: Sweden

Posts: 94
Thanks: 0

Question Euclid's Proof of the Infinitude of Primes

So I'm going to refer to this link that the explanation is from:
https://primes.utm.edu/notes/proofs/...e/euclids.html

Theorem.
"There are more primes than found in any finite list of primes." (Chris K. Caldwell)

Proof.
"Call the primes in our finite list p1, p2, ..., pr.
Let P be any common multiple of these primes plus one (for example, P = p1p2...pr+1). Now P is either prime or it is not.
If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p.
Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible.
So this prime p is some prime that was not in our original list.
Either way, the original list was incomplete." (Chris K. Caldwell)

So all the parts of the proof is clear to me until he says:
Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible.

So p is a prime number that divide P in this case,
but I do not understand why p can't be any of p1, p2, ..., pr?
So using the definition of a prime number this tells me that I get 1 divided by p (1 / p) which is impossible?
Why is that impossible?
DecoratorFawn82 is offline  
 
September 2nd, 2018, 08:33 AM   #2
Global Moderator
 
Joined: Dec 2006

Posts: 19,882
Thanks: 1835

He means that 1/p can't be a positive integer, as it's a fraction lying strictly between 0 and 1. The number 1 isn't considered to be a prime.
skipjack is offline  
September 2nd, 2018, 08:58 AM   #3
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 504
Thanks: 283

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
Originally Posted by DecoratorFawn82 View Post
So I'm going to refer to this link that the explanation is from:
https://primes.utm.edu/notes/proofs/...e/euclids.html

Theorem.
"There are more primes than found in any finite list of primes." (Chris K. Caldwell)

Proof.
"Call the primes in our finite list p1, p2, ..., pr.
Let P be any common multiple of these primes plus one (for example, P = p1p2...pr+1). Now P is either prime or it is not.
If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p.
Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible.
So this prime p is some prime that was not in our original list.
Either way, the original list was incomplete." (Chris K. Caldwell)

So all the parts of the proof is clear to me until he says:
Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible.

So p is a prime number that divide P in this case,
but I do not understand why p can't be any of p1, p2, ..., pr?
So using the definition of a prime number this tells me that I get 1 divided by p (1 / p) which is impossible?
Why is that impossible?
If you have a sum of the form $A = B + C$ and a number $p$, divides both $A$ and $B$, then it must also divide $C$. In this case your sum looks like $P = p_1 \cdot ... \cdot p_r + 1$.
SDK is offline  
September 2nd, 2018, 10:11 AM   #4
Senior Member
 
Joined: Aug 2012

Posts: 2,082
Thanks: 595

Quote:
Originally Posted by DecoratorFawn82 View Post

So p is a prime number that divide P in this case,
but I do not understand why p can't be any of p1, p2, ..., pr?
Because dividing $p_1 p_2 \dots p_r + 1$ by any of the $p_i$'s leaves a remainder of 1.
Thanks from DecoratorFawn82
Maschke is online now  
September 2nd, 2018, 10:23 AM   #5
Member
 
Joined: Sep 2014
From: Sweden

Posts: 94
Thanks: 0

So p is a prime number that divide P in this case,
but I do not understand why p can't be any of p1, p2, ..., pr?

Is the reason that we have assumed that any of p1, p2, ..., pr are prime numbers and so are p. Definition: a prime number is only divisible by 1 and itself and is greater than 1. So a prime is not divisible by another prime number (so that the result is a positive integer).

So if p where any of p1, p2, ..., pr then:
if p1 = p --> p / p1 = 1 --> p = 1 * p1 --> 1 / p = p1
if p2 = p --> p / p2 = 1 --> p = 1 * p2 --> 1 / p = p2

So this shows me that it is impossible because 1 / p can't become a positive integer since p is a prime number.
DecoratorFawn82 is offline  
September 2nd, 2018, 11:23 AM   #6
Senior Member
 
Joined: Aug 2012

Posts: 2,082
Thanks: 595

Quote:
Originally Posted by DecoratorFawn82 View Post
So p is a prime number that divide P in this case,
but I do not understand why p can't be any of p1, p2, ..., pr?

Is the reason that we have assumed that any of p1, p2, ..., pr are prime numbers and so are p. Definition: a prime number is only divisible by 1 and itself and is greater than 1. So a prime is not divisible by another prime number (so that the result is a positive integer).

So if p where any of p1, p2, ..., pr then:
if p1 = p --> p / p1 = 1 --> p = 1 * p1 --> 1 / p = p1
if p2 = p --> p / p2 = 1 --> p = 1 * p2 --> 1 / p = p2

So this shows me that it is impossible because 1 / p can't become a positive integer since p is a prime number.

Look at an example. Consider $31 = 2 \times 3 \times 5 + 1$.

If you divide it by 2, you get remainder 1. If you divide it by 3, you get remainder 1. If you divide it by 5, you get remainder 1.

So 31 must be either be prime (which it is, in this case) or else divisible by some prime other than 2, 3, or 5.
Maschke is online now  
September 2nd, 2018, 11:35 AM   #7
Global Moderator
 
Joined: Dec 2006

Posts: 19,882
Thanks: 1835

Put simply, if p is one of the first r primes, p1p2p3p4...pr and p1p2p3p4...pr + p are consecutive integer multiples of p. As P must be strictly inbetween those two integers, it can't be an integer multiple of p, which means that p doesn't divide P, contrary to the assumption that it does.
Thanks from DecoratorFawn82
skipjack is offline  
September 3rd, 2018, 05:38 AM   #8
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

Another way of seeing what is going on is to use a more friendly notation.

$\mathbb L = \{p_1,\ ... \ p_r\} = \text { the FINITE LIST of primes.}$

$\text {Let } \displaystyle y = \prod_{j=1}^r p_j \implies y \in \mathbb Z,\ y > 1, \text { and }$

$\text {for any } p \in \mathbb L,\ y \ge p \text { and } \dfrac{y}{p} \in \mathbb Z \ \because p \text { is a factor of } y.$

$\text {Let } x = y + 1 \implies x \in \mathbb Z,\ x > y > 1 \text { and, for any } p \in \mathbb L,\ x > p .$

$x \text { is either a prime or else not a prime because } x \text { is an integer } > 1.$

$\text {Case I: } x \text { is a prime.}$

$p \in \mathbb L \implies x > p \implies x \not \in \mathbb L \implies$

$\text {there is at least one prime not in the finite list.}$

$\text {Case II: } x \text { is not a prime.}$

$\therefore \exists \text { a non-empty set } \mathbb F \text { of prime factors of } x.$

$\text {ASSUME } \exists \ u \text { such that } u \in \mathbb L \text { and } u \in \mathbb F.$

$v = \dfrac{x}{u} \implies v \in \mathbb Z \ \because \ u \in \mathbb F.$

$w = \dfrac{y}{u} \implies w \in \mathbb Z \ \because \ u \in \mathbb L.$

$v = \dfrac{x}{u} = \dfrac{y + 1}{u} = w + \dfrac{1}{u}.$

$\text {By hypothesis, } u \text { is a prime } \implies u > 1 \implies 0 < \dfrac{1}{u} < 1.$

$\therefore w < w + \dfrac{1}{u} < w + 1 \implies \left (w + \dfrac{1}{u} \right ) \not \in \mathbb Z \ \because \ w \in \mathbb Z.$

$\therefore v \not \in \mathbb Z, \text {a CONTRADICTION.}$

$\therefore \not \exists \ u \text { such that } u \in \mathbb L \text { and } u \in \mathbb F.$

$\text {But } \mathbb F \text { is not empty } \implies$

$\text {there is at least one prime not in the finite list.}$
Thanks from Sebastian Garth
JeffM1 is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
euclid, infinitude, primes, proof



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
The infinitude between random numbers Loren Number Theory 7 June 3rd, 2016 03:17 PM
Proof Regarding Primes to a Power magnuspaajarvi Applied Math 1 February 8th, 2014 11:08 PM
Help with an infinite primes of the form proof WheepWhoop Number Theory 7 October 20th, 2011 06:09 PM
A new proof of the infinitude of primes brunojo Number Theory 6 December 12th, 2008 08:57 AM
Reciprocal sum of primes diverges... proof? alpah Number Theory 5 December 30th, 2006 02:05 PM





Copyright © 2018 My Math Forum. All rights reserved.