Mixing
Question on a proof that there are infinitely many primes
Clash Royale CLAN TAG#URR8PPP
up vote
7
down vote
favorite
There are several ways to prove this fact, and I can think of two reasonably clear ways, but my professor presented a sketch of a proof that I can't quite follow. I'm going to replicate his logic as best as I can.
Theorem. There are infinitely many primes.
Proof. Assume for a contradiction that there are only finitely many primes, which we can list as $p_1, p_2, p_3, ldots, p_m$ for some $m in mathbbN$. Then, form the product
beginalign*
N = mathopPilimits_i=1^m p_i + 1.
endalign*
From here there are several ways to proceed. But, this is where I find myself getting confused.
Since $mathbbZ$ is closed under multiplication and addition, $N in mathbbZ$, and since $N > p_i, forall i$, $N$ is not a prime. So, there exists some $p_i$ such that $p_i mid N$, so $exists a in mathbbZ, a cdot p_i = N$, i.e., $a cdot p_i = p_1 cdot p_2 cdot p_3 cdots p_m + 1$.
From here, my professor concluded that $frac1p_i in mathbbZ$, an absurdity and thus a contradiction. I can't quite figure out how to get there. If we divide both sides through by $p_i$, since $1 leq i leq m$, we get $a$ on the LHS and two terms on the RHS, one of which is a product of $m - 1$ primes (after cancelling) and one of which is $frac1p_i$. From here, perhaps we could subtract the product of $m - 1$ terms, clearly an integer by closure under multiplication, from $a$, also an integer. Then, by closure under subtraction, $a$ less this product is also an integer, in which case we've found our contradiction.
Is this correct?
Thanks in advance.
number-theory prime-numbers proof-explanation
edited Aug 30 at 0:55
João Ramos
1,024719
asked Aug 30 at 0:47
Matt.P
930414
add a comment |Â
up vote
7
down vote
favorite
There are several ways to prove this fact, and I can think of two reasonably clear ways, but my professor presented a sketch of a proof that I can't quite follow. I'm going to replicate his logic as best as I can.
Theorem. There are infinitely many primes.
Proof. Assume for a contradiction that there are only finitely many primes, which we can list as $p_1, p_2, p_3, ldots, p_m$ for some $m in mathbbN$. Then, form the product
beginalign*
N = mathopPilimits_i=1^m p_i + 1.
endalign*
From here there are several ways to proceed. But, this is where I find myself getting confused.
Since $mathbbZ$ is closed under multiplication and addition, $N in mathbbZ$, and since $N > p_i, forall i$, $N$ is not a prime. So, there exists some $p_i$ such that $p_i mid N$, so $exists a in mathbbZ, a cdot p_i = N$, i.e., $a cdot p_i = p_1 cdot p_2 cdot p_3 cdots p_m + 1$.
From here, my professor concluded that $frac1p_i in mathbbZ$, an absurdity and thus a contradiction. I can't quite figure out how to get there. If we divide both sides through by $p_i$, since $1 leq i leq m$, we get $a$ on the LHS and two terms on the RHS, one of which is a product of $m - 1$ primes (after cancelling) and one of which is $frac1p_i$. From here, perhaps we could subtract the product of $m - 1$ terms, clearly an integer by closure under multiplication, from $a$, also an integer. Then, by closure under subtraction, $a$ less this product is also an integer, in which case we've found our contradiction.
Is this correct?
Thanks in advance.
number-theory prime-numbers proof-explanation
edited Aug 30 at 0:55
João Ramos
1,024719
asked Aug 30 at 0:47
Matt.P
930414
2
Yes, that's correct.
– quid♦
Aug 30 at 0:51
1
Excellent. Thank you.
– Matt.P
Aug 30 at 0:54
add a comment |Â
up vote
7
down vote
favorite
up vote
7
down vote
favorite
There are several ways to prove this fact, and I can think of two reasonably clear ways, but my professor presented a sketch of a proof that I can't quite follow. I'm going to replicate his logic as best as I can.
Theorem. There are infinitely many primes.
Proof. Assume for a contradiction that there are only finitely many primes, which we can list as $p_1, p_2, p_3, ldots, p_m$ for some $m in mathbbN$. Then, form the product
beginalign*
N = mathopPilimits_i=1^m p_i + 1.
endalign*
From here there are several ways to proceed. But, this is where I find myself getting confused.
Since $mathbbZ$ is closed under multiplication and addition, $N in mathbbZ$, and since $N > p_i, forall i$, $N$ is not a prime. So, there exists some $p_i$ such that $p_i mid N$, so $exists a in mathbbZ, a cdot p_i = N$, i.e., $a cdot p_i = p_1 cdot p_2 cdot p_3 cdots p_m + 1$.
From here, my professor concluded that $frac1p_i in mathbbZ$, an absurdity and thus a contradiction. I can't quite figure out how to get there. If we divide both sides through by $p_i$, since $1 leq i leq m$, we get $a$ on the LHS and two terms on the RHS, one of which is a product of $m - 1$ primes (after cancelling) and one of which is $frac1p_i$. From here, perhaps we could subtract the product of $m - 1$ terms, clearly an integer by closure under multiplication, from $a$, also an integer. Then, by closure under subtraction, $a$ less this product is also an integer, in which case we've found our contradiction.
Is this correct?
Thanks in advance.
number-theory prime-numbers proof-explanation
edited Aug 30 at 0:55
João Ramos
1,024719
asked Aug 30 at 0:47
Matt.P
930414
There are several ways to prove this fact, and I can think of two reasonably clear ways, but my professor presented a sketch of a proof that I can't quite follow. I'm going to replicate his logic as best as I can.
Theorem. There are infinitely many primes.
Proof. Assume for a contradiction that there are only finitely many primes, which we can list as $p_1, p_2, p_3, ldots, p_m$ for some $m in mathbbN$. Then, form the product
beginalign*
N = mathopPilimits_i=1^m p_i + 1.
endalign*
From here there are several ways to proceed. But, this is where I find myself getting confused.
Since $mathbbZ$ is closed under multiplication and addition, $N in mathbbZ$, and since $N > p_i, forall i$, $N$ is not a prime. So, there exists some $p_i$ such that $p_i mid N$, so $exists a in mathbbZ, a cdot p_i = N$, i.e., $a cdot p_i = p_1 cdot p_2 cdot p_3 cdots p_m + 1$.
From here, my professor concluded that $frac1p_i in mathbbZ$, an absurdity and thus a contradiction. I can't quite figure out how to get there. If we divide both sides through by $p_i$, since $1 leq i leq m$, we get $a$ on the LHS and two terms on the RHS, one of which is a product of $m - 1$ primes (after cancelling) and one of which is $frac1p_i$. From here, perhaps we could subtract the product of $m - 1$ terms, clearly an integer by closure under multiplication, from $a$, also an integer. Then, by closure under subtraction, $a$ less this product is also an integer, in which case we've found our contradiction.
Is this correct?
Thanks in advance.
number-theory prime-numbers proof-explanation
edited Aug 30 at 0:55
João Ramos
1,024719
asked Aug 30 at 0:47
Matt.P
930414
edited Aug 30 at 0:55
João Ramos
1,024719
edited Aug 30 at 0:55
João Ramos
1,024719
edited Aug 30 at 0:55
João Ramos
1,024719
1,024719
asked Aug 30 at 0:47
Matt.P
930414
asked Aug 30 at 0:47
Matt.P
930414
asked Aug 30 at 0:47
Matt.P
930414
930414
2
Yes, that's correct.
– quid♦
Aug 30 at 0:51
1
Excellent. Thank you.
– Matt.P
Aug 30 at 0:54
add a comment |Â
2
Yes, that's correct.
– quid♦
Aug 30 at 0:51
1
Excellent. Thank you.
– Matt.P
Aug 30 at 0:54
2
2
Yes, that's correct.
– quid♦
Aug 30 at 0:51
Yes, that's correct.
– quid♦
Aug 30 at 0:51
1
1
Excellent. Thank you.
– Matt.P
Aug 30 at 0:54
Excellent. Thank you.
– Matt.P
Aug 30 at 0:54
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
13
down vote
accepted
I disagree with the use of "division" in any proof for elementary number theory. The concept of division is usually only formally introduced much later in a course from where you appear to be at the moment.
So, we get to letting $N=prodlimits_i=1^mp_i + 1$ and we determined that $N>p_i$ for all $i$ and so $N$ is not one of the elements in our list of primes. Ergo, $N$ must be composite (by theorem proved earlier, every natural number is either 0, 1, prime, or composite). That is, there is some naturals $j$ and $a$ such that $N=acdot p_j$.
That is, $acdot p_j = p_1cdot p_2cdots p_jcdots p_m + 1$
Now, by subtracting and factoring, we have $1 = p_jcdot(a - p_1cdot p_2cdots p_j-1cdot p_j+1cdots p_m)$
Note, however, that $(a-p_1cdots p_m)$ is an integer and so too is $p_j$. Notice that this would then imply that $p_j$ is a divisor of $1$, but $1$ has no divisors except itself. This is our contradiction.
Note, the above argument completely bypassed the need for referring to division, though it does make use of divisibility (something which is perfectly acceptable to refer to and use in these level of proofs).
answered Aug 30 at 0:57
JMoravitz
44.7k33582
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
13
down vote
accepted
I disagree with the use of "division" in any proof for elementary number theory. The concept of division is usually only formally introduced much later in a course from where you appear to be at the moment.
So, we get to letting $N=prodlimits_i=1^mp_i + 1$ and we determined that $N>p_i$ for all $i$ and so $N$ is not one of the elements in our list of primes. Ergo, $N$ must be composite (by theorem proved earlier, every natural number is either 0, 1, prime, or composite). That is, there is some naturals $j$ and $a$ such that $N=acdot p_j$.
That is, $acdot p_j = p_1cdot p_2cdots p_jcdots p_m + 1$
Now, by subtracting and factoring, we have $1 = p_jcdot(a - p_1cdot p_2cdots p_j-1cdot p_j+1cdots p_m)$
Note, however, that $(a-p_1cdots p_m)$ is an integer and so too is $p_j$. Notice that this would then imply that $p_j$ is a divisor of $1$, but $1$ has no divisors except itself. This is our contradiction.
Note, the above argument completely bypassed the need for referring to division, though it does make use of divisibility (something which is perfectly acceptable to refer to and use in these level of proofs).
answered Aug 30 at 0:57
JMoravitz
44.7k33582
add a comment |Â
up vote
13
down vote
accepted
I disagree with the use of "division" in any proof for elementary number theory. The concept of division is usually only formally introduced much later in a course from where you appear to be at the moment.
So, we get to letting $N=prodlimits_i=1^mp_i + 1$ and we determined that $N>p_i$ for all $i$ and so $N$ is not one of the elements in our list of primes. Ergo, $N$ must be composite (by theorem proved earlier, every natural number is either 0, 1, prime, or composite). That is, there is some naturals $j$ and $a$ such that $N=acdot p_j$.
That is, $acdot p_j = p_1cdot p_2cdots p_jcdots p_m + 1$
Now, by subtracting and factoring, we have $1 = p_jcdot(a - p_1cdot p_2cdots p_j-1cdot p_j+1cdots p_m)$
Note, however, that $(a-p_1cdots p_m)$ is an integer and so too is $p_j$. Notice that this would then imply that $p_j$ is a divisor of $1$, but $1$ has no divisors except itself. This is our contradiction.
Note, the above argument completely bypassed the need for referring to division, though it does make use of divisibility (something which is perfectly acceptable to refer to and use in these level of proofs).
answered Aug 30 at 0:57
JMoravitz
44.7k33582
add a comment |Â
up vote
13
down vote
accepted
up vote
13
down vote
accepted
I disagree with the use of "division" in any proof for elementary number theory. The concept of division is usually only formally introduced much later in a course from where you appear to be at the moment.
So, we get to letting $N=prodlimits_i=1^mp_i + 1$ and we determined that $N>p_i$ for all $i$ and so $N$ is not one of the elements in our list of primes. Ergo, $N$ must be composite (by theorem proved earlier, every natural number is either 0, 1, prime, or composite). That is, there is some naturals $j$ and $a$ such that $N=acdot p_j$.
That is, $acdot p_j = p_1cdot p_2cdots p_jcdots p_m + 1$
Now, by subtracting and factoring, we have $1 = p_jcdot(a - p_1cdot p_2cdots p_j-1cdot p_j+1cdots p_m)$
Note, however, that $(a-p_1cdots p_m)$ is an integer and so too is $p_j$. Notice that this would then imply that $p_j$ is a divisor of $1$, but $1$ has no divisors except itself. This is our contradiction.
Note, the above argument completely bypassed the need for referring to division, though it does make use of divisibility (something which is perfectly acceptable to refer to and use in these level of proofs).
answered Aug 30 at 0:57
JMoravitz
44.7k33582
I disagree with the use of "division" in any proof for elementary number theory. The concept of division is usually only formally introduced much later in a course from where you appear to be at the moment.
So, we get to letting $N=prodlimits_i=1^mp_i + 1$ and we determined that $N>p_i$ for all $i$ and so $N$ is not one of the elements in our list of primes. Ergo, $N$ must be composite (by theorem proved earlier, every natural number is either 0, 1, prime, or composite). That is, there is some naturals $j$ and $a$ such that $N=acdot p_j$.
That is, $acdot p_j = p_1cdot p_2cdots p_jcdots p_m + 1$
Now, by subtracting and factoring, we have $1 = p_jcdot(a - p_1cdot p_2cdots p_j-1cdot p_j+1cdots p_m)$
Note, however, that $(a-p_1cdots p_m)$ is an integer and so too is $p_j$. Notice that this would then imply that $p_j$ is a divisor of $1$, but $1$ has no divisors except itself. This is our contradiction.
Note, the above argument completely bypassed the need for referring to division, though it does make use of divisibility (something which is perfectly acceptable to refer to and use in these level of proofs).
answered Aug 30 at 0:57
JMoravitz
44.7k33582
answered Aug 30 at 0:57
JMoravitz
44.7k33582
answered Aug 30 at 0:57
JMoravitz
44.7k33582
answered Aug 30 at 0:57
JMoravitz
44.7k33582
44.7k33582
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2898981%2fquestion-on-a-proof-that-there-are-infinitely-many-primes%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
Yes, that's correct.
– quid♦
Aug 30 at 0:51
1
Excellent. Thank you.
– Matt.P
Aug 30 at 0:54