Proof of Lemma: Every nonzero integer can be written as a product of primes
$begingroup$
I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.
I encountered the classic lemma about every nonzero integer being the product of primes in a textbook about number theory. In this textbook there is also a proof for it provided, and I'd like to understand why it is that the proof actually works.
The proof is as follows:
Assume, for contradiction, that there is an integer $N$ that cannot be written as a product of primes. Let $N$ be the smallest positive integer with this property. Since $N$ cannot itself be prime we must have $N = mn$, where $1 < m$, $n < N$. However, since $m$, $n$ are positive and smaller than $N$ they must each be a product of primes. But then so is $N = mn$. This is a contradiction.
I feel like this proof kind of presupposes the lemma. I think this line of reasoning could be strengthened using induction, and I've seen other proofs of this lemma that use induction. Can someone help me out? What am I missing and why do I think that this proof of the lemma is circular?
elementary-number-theory prime-numbers proof-explanation integers
edited 3 hours ago
Robert Soupe
11.4k21950
asked 4 hours ago
Alena GusakovAlena Gusakov
162
New contributor
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.
I encountered the classic lemma about every nonzero integer being the product of primes in a textbook about number theory. In this textbook there is also a proof for it provided, and I'd like to understand why it is that the proof actually works.
The proof is as follows:
Assume, for contradiction, that there is an integer $N$ that cannot be written as a product of primes. Let $N$ be the smallest positive integer with this property. Since $N$ cannot itself be prime we must have $N = mn$, where $1 < m$, $n < N$. However, since $m$, $n$ are positive and smaller than $N$ they must each be a product of primes. But then so is $N = mn$. This is a contradiction.
I feel like this proof kind of presupposes the lemma. I think this line of reasoning could be strengthened using induction, and I've seen other proofs of this lemma that use induction. Can someone help me out? What am I missing and why do I think that this proof of the lemma is circular?
elementary-number-theory prime-numbers proof-explanation integers
edited 3 hours ago
Robert Soupe
11.4k21950
asked 4 hours ago
Alena GusakovAlena Gusakov
162
New contributor
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
2
$begingroup$
That argument is by induction. the result is easy to check for small numbers, so assume it holds up to $N-1$. Then $N$ is either prime, in which case we are done, or it factors as $atimes b$ with $1<a≤b<N-1$ and you can apply the inductive hypothesis to $a,b$. Same argument.
$endgroup$
– lulu
4 hours ago
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
4 hours ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
4 hours ago
$begingroup$
It's not circular, but it could be a lot clearer. It's not strictly necessary to say $n > 1$, since $m$ is positive and $mn$ is also positive.
$endgroup$
– Robert Soupe
3 hours ago
1
$begingroup$
It's a valid proof by infinite descent (a.k.a. minimal criminal), the contrapositive of induction - see the Remark here. You should master both this (negative) and the normal (positive) form of induction.
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
$begingroup$
I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.
I encountered the classic lemma about every nonzero integer being the product of primes in a textbook about number theory. In this textbook there is also a proof for it provided, and I'd like to understand why it is that the proof actually works.
The proof is as follows:
Assume, for contradiction, that there is an integer $N$ that cannot be written as a product of primes. Let $N$ be the smallest positive integer with this property. Since $N$ cannot itself be prime we must have $N = mn$, where $1 < m$, $n < N$. However, since $m$, $n$ are positive and smaller than $N$ they must each be a product of primes. But then so is $N = mn$. This is a contradiction.
I feel like this proof kind of presupposes the lemma. I think this line of reasoning could be strengthened using induction, and I've seen other proofs of this lemma that use induction. Can someone help me out? What am I missing and why do I think that this proof of the lemma is circular?
elementary-number-theory prime-numbers proof-explanation integers
edited 3 hours ago
Robert Soupe
11.4k21950
asked 4 hours ago
Alena GusakovAlena Gusakov
162
New contributor
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.
I encountered the classic lemma about every nonzero integer being the product of primes in a textbook about number theory. In this textbook there is also a proof for it provided, and I'd like to understand why it is that the proof actually works.
The proof is as follows:
Assume, for contradiction, that there is an integer $N$ that cannot be written as a product of primes. Let $N$ be the smallest positive integer with this property. Since $N$ cannot itself be prime we must have $N = mn$, where $1 < m$, $n < N$. However, since $m$, $n$ are positive and smaller than $N$ they must each be a product of primes. But then so is $N = mn$. This is a contradiction.
I feel like this proof kind of presupposes the lemma. I think this line of reasoning could be strengthened using induction, and I've seen other proofs of this lemma that use induction. Can someone help me out? What am I missing and why do I think that this proof of the lemma is circular?
elementary-number-theory prime-numbers proof-explanation integers
elementary-number-theory prime-numbers proof-explanation integers
edited 3 hours ago
Robert Soupe
11.4k21950
asked 4 hours ago
Alena GusakovAlena Gusakov
162
New contributor
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 3 hours ago
Robert Soupe
11.4k21950
asked 4 hours ago
Alena GusakovAlena Gusakov
162
New contributor
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 3 hours ago
Robert Soupe
11.4k21950
edited 3 hours ago
Robert Soupe
11.4k21950
edited 3 hours ago
Robert Soupe
11.4k21950
11.4k21950
asked 4 hours ago
Alena GusakovAlena Gusakov
162
New contributor
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Alena GusakovAlena Gusakov
162
asked 4 hours ago
Alena GusakovAlena Gusakov
162
162
New contributor
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Alena Gusakov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
$begingroup$
That argument is by induction. the result is easy to check for small numbers, so assume it holds up to $N-1$. Then $N$ is either prime, in which case we are done, or it factors as $atimes b$ with $1<a≤b<N-1$ and you can apply the inductive hypothesis to $a,b$. Same argument.
$endgroup$
– lulu
4 hours ago
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
4 hours ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
4 hours ago
$begingroup$
It's not circular, but it could be a lot clearer. It's not strictly necessary to say $n > 1$, since $m$ is positive and $mn$ is also positive.
$endgroup$
– Robert Soupe
3 hours ago
1
$begingroup$
It's a valid proof by infinite descent (a.k.a. minimal criminal), the contrapositive of induction - see the Remark here. You should master both this (negative) and the normal (positive) form of induction.
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
2
$begingroup$
That argument is by induction. the result is easy to check for small numbers, so assume it holds up to $N-1$. Then $N$ is either prime, in which case we are done, or it factors as $atimes b$ with $1<a≤b<N-1$ and you can apply the inductive hypothesis to $a,b$. Same argument.
$endgroup$
– lulu
4 hours ago
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
4 hours ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
4 hours ago
$begingroup$
It's not circular, but it could be a lot clearer. It's not strictly necessary to say $n > 1$, since $m$ is positive and $mn$ is also positive.
$endgroup$
– Robert Soupe
3 hours ago
1
$begingroup$
It's a valid proof by infinite descent (a.k.a. minimal criminal), the contrapositive of induction - see the Remark here. You should master both this (negative) and the normal (positive) form of induction.
$endgroup$
– Bill Dubuque
1 hour ago
2
2
$begingroup$
That argument is by induction. the result is easy to check for small numbers, so assume it holds up to $N-1$. Then $N$ is either prime, in which case we are done, or it factors as $atimes b$ with $1<a≤b<N-1$ and you can apply the inductive hypothesis to $a,b$. Same argument.
$endgroup$
– lulu
4 hours ago
$begingroup$
That argument is by induction. the result is easy to check for small numbers, so assume it holds up to $N-1$. Then $N$ is either prime, in which case we are done, or it factors as $atimes b$ with $1<a≤b<N-1$ and you can apply the inductive hypothesis to $a,b$. Same argument.
$endgroup$
– lulu
4 hours ago
1
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
4 hours ago
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
4 hours ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
4 hours ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
4 hours ago
$begingroup$
It's not circular, but it could be a lot clearer. It's not strictly necessary to say $n > 1$, since $m$ is positive and $mn$ is also positive.
$endgroup$
– Robert Soupe
3 hours ago
$begingroup$
It's not circular, but it could be a lot clearer. It's not strictly necessary to say $n > 1$, since $m$ is positive and $mn$ is also positive.
$endgroup$
– Robert Soupe
3 hours ago
1
1
$begingroup$
It's a valid proof by infinite descent (a.k.a. minimal criminal), the contrapositive of induction - see the Remark here. You should master both this (negative) and the normal (positive) form of induction.
$endgroup$
– Bill Dubuque
1 hour ago
$begingroup$
It's a valid proof by infinite descent (a.k.a. minimal criminal), the contrapositive of induction - see the Remark here. You should master both this (negative) and the normal (positive) form of induction.
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Although the proof by contradiction is correct, your feeling of unease is fine, because the direct proof by induction is so much clearer:
Take an integer $N$. If $N$ is prime, there is nothing to prove. Otherwise, we must have $N = mn$, where $1 < m, n < N$. By induction, since $m, n$ are smaller than $N$, they must each be a product of primes. Then so is $N = mn$. Done.
answered 4 hours ago
lhflhf
166k11172402
$endgroup$
add a comment |
$begingroup$
The proof is not circular, the key is in the second sentence: Let N be the smallest positive integer with this property.
We are allowed to say a least $N$ exists because of the well-ordering principle.
answered 4 hours ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
1165
$endgroup$
$begingroup$
I don't know if it's because of the well-ordering principle ... that's like using a hammer to slice through butter. One does not need the full strength of the AOC to prove such a simple statement.
$endgroup$
– Don Thousand
3 hours ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
3 hours ago
$begingroup$
@RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@DonThousand: I think "well-ordering principle" here refers to the statement "the usual ordering on the natural numbers is a well order". The Axiom of Choice equivalent is "every set admits an ordering which is a well order" - that wouldn't really even help with this proof, since it would only tell us that there is some ordering of the natural numbers which is a well order - it doesn't tell us that the usual ordering is one.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@NateEldredge: Indeed, the well-ordering principle (not the similarly-named well-ordering theorem) is equivalent to induction (and probably also to infinite descent, but I haven't worked through that one yet), so if you disallow WOP, then you are going to have a hard time proving a lot of things.
$endgroup$
– Kevin
1 hour ago
add a comment |
$begingroup$
A proof by induction has base case(s), Let m and n be said base cases. if it's true for m and true for n (not necessarily distinct), then because it's a product, it follows for mn. All the proof supposes, is N=mn for some base case ( primes or prime powers to start, in these cases) with m and n proved. Then it follows for N, which by saying N which
originally was consider the least element of a set of counterexamples, has one, it eliminates all possible least elements for the set we originally supposed existed.
answered 1 hour ago
Roddy MacPheeRoddy MacPhee
537118
$endgroup$
add a comment |
$begingroup$
I can definitely understand how this can feel a little off.
1) The lemma (as stated in the question) says all nonzero integers. Primes are integers and, by definition, cannot be products of primes. So, I think the lemma probably is actually more along the lines of: "all positive non-prime integers can be written as a product of primes".
2) Also, the statement "since 𝑚,𝑛 are positive and smaller than 𝑁 they must each be a product of primes" doesn't really explain why they must be a product of primes. Since, 𝑁 is the smallest positive non-prime integer that cannot be written as a product of primes (by supposition of the lemma), then 𝑚,𝑛 are either prime themselves or a product of primes (as they are less than 𝑁 and 𝑁 is the smallest number that isn't a product of primes). Either way, they will provide the primes necessary to create 𝑁, making 𝑁 able to be constructed as a product of primes.
Hopefully this helps to see why the proof by contradiction works.
answered 11 mins ago
dudemandudeman
1012
New contributor
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Alena Gusakov is a new contributor. Be nice, and check out our Code of Conduct.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3161147%2fproof-of-lemma-every-nonzero-integer-can-be-written-as-a-product-of-primes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Although the proof by contradiction is correct, your feeling of unease is fine, because the direct proof by induction is so much clearer:
Take an integer $N$. If $N$ is prime, there is nothing to prove. Otherwise, we must have $N = mn$, where $1 < m, n < N$. By induction, since $m, n$ are smaller than $N$, they must each be a product of primes. Then so is $N = mn$. Done.
answered 4 hours ago
lhflhf
166k11172402
$endgroup$
add a comment |
$begingroup$
Although the proof by contradiction is correct, your feeling of unease is fine, because the direct proof by induction is so much clearer:
Take an integer $N$. If $N$ is prime, there is nothing to prove. Otherwise, we must have $N = mn$, where $1 < m, n < N$. By induction, since $m, n$ are smaller than $N$, they must each be a product of primes. Then so is $N = mn$. Done.
answered 4 hours ago
lhflhf
166k11172402
$endgroup$
add a comment |
$begingroup$
Although the proof by contradiction is correct, your feeling of unease is fine, because the direct proof by induction is so much clearer:
Take an integer $N$. If $N$ is prime, there is nothing to prove. Otherwise, we must have $N = mn$, where $1 < m, n < N$. By induction, since $m, n$ are smaller than $N$, they must each be a product of primes. Then so is $N = mn$. Done.
answered 4 hours ago
lhflhf
166k11172402
$endgroup$
Although the proof by contradiction is correct, your feeling of unease is fine, because the direct proof by induction is so much clearer:
Take an integer $N$. If $N$ is prime, there is nothing to prove. Otherwise, we must have $N = mn$, where $1 < m, n < N$. By induction, since $m, n$ are smaller than $N$, they must each be a product of primes. Then so is $N = mn$. Done.
answered 4 hours ago
lhflhf
166k11172402
answered 4 hours ago
lhflhf
166k11172402
answered 4 hours ago
lhflhf
166k11172402
answered 4 hours ago
lhflhf
166k11172402
166k11172402
add a comment |
add a comment |
$begingroup$
The proof is not circular, the key is in the second sentence: Let N be the smallest positive integer with this property.
We are allowed to say a least $N$ exists because of the well-ordering principle.
answered 4 hours ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
1165
$endgroup$
$begingroup$
I don't know if it's because of the well-ordering principle ... that's like using a hammer to slice through butter. One does not need the full strength of the AOC to prove such a simple statement.
$endgroup$
– Don Thousand
3 hours ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
3 hours ago
$begingroup$
@RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@DonThousand: I think "well-ordering principle" here refers to the statement "the usual ordering on the natural numbers is a well order". The Axiom of Choice equivalent is "every set admits an ordering which is a well order" - that wouldn't really even help with this proof, since it would only tell us that there is some ordering of the natural numbers which is a well order - it doesn't tell us that the usual ordering is one.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@NateEldredge: Indeed, the well-ordering principle (not the similarly-named well-ordering theorem) is equivalent to induction (and probably also to infinite descent, but I haven't worked through that one yet), so if you disallow WOP, then you are going to have a hard time proving a lot of things.
$endgroup$
– Kevin
1 hour ago
add a comment |
$begingroup$
The proof is not circular, the key is in the second sentence: Let N be the smallest positive integer with this property.
We are allowed to say a least $N$ exists because of the well-ordering principle.
answered 4 hours ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
1165
$endgroup$
$begingroup$
I don't know if it's because of the well-ordering principle ... that's like using a hammer to slice through butter. One does not need the full strength of the AOC to prove such a simple statement.
$endgroup$
– Don Thousand
3 hours ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
3 hours ago
$begingroup$
@RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@DonThousand: I think "well-ordering principle" here refers to the statement "the usual ordering on the natural numbers is a well order". The Axiom of Choice equivalent is "every set admits an ordering which is a well order" - that wouldn't really even help with this proof, since it would only tell us that there is some ordering of the natural numbers which is a well order - it doesn't tell us that the usual ordering is one.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@NateEldredge: Indeed, the well-ordering principle (not the similarly-named well-ordering theorem) is equivalent to induction (and probably also to infinite descent, but I haven't worked through that one yet), so if you disallow WOP, then you are going to have a hard time proving a lot of things.
$endgroup$
– Kevin
1 hour ago
add a comment |
$begingroup$
The proof is not circular, the key is in the second sentence: Let N be the smallest positive integer with this property.
We are allowed to say a least $N$ exists because of the well-ordering principle.
answered 4 hours ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
1165
$endgroup$
The proof is not circular, the key is in the second sentence: Let N be the smallest positive integer with this property.
We are allowed to say a least $N$ exists because of the well-ordering principle.
answered 4 hours ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
1165
answered 4 hours ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
1165
answered 4 hours ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
1165
answered 4 hours ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
1165
1165
$begingroup$
I don't know if it's because of the well-ordering principle ... that's like using a hammer to slice through butter. One does not need the full strength of the AOC to prove such a simple statement.
$endgroup$
– Don Thousand
3 hours ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
3 hours ago
$begingroup$
@RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@DonThousand: I think "well-ordering principle" here refers to the statement "the usual ordering on the natural numbers is a well order". The Axiom of Choice equivalent is "every set admits an ordering which is a well order" - that wouldn't really even help with this proof, since it would only tell us that there is some ordering of the natural numbers which is a well order - it doesn't tell us that the usual ordering is one.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@NateEldredge: Indeed, the well-ordering principle (not the similarly-named well-ordering theorem) is equivalent to induction (and probably also to infinite descent, but I haven't worked through that one yet), so if you disallow WOP, then you are going to have a hard time proving a lot of things.
$endgroup$
– Kevin
1 hour ago
add a comment |
$begingroup$
I don't know if it's because of the well-ordering principle ... that's like using a hammer to slice through butter. One does not need the full strength of the AOC to prove such a simple statement.
$endgroup$
– Don Thousand
3 hours ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
3 hours ago
$begingroup$
@RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@DonThousand: I think "well-ordering principle" here refers to the statement "the usual ordering on the natural numbers is a well order". The Axiom of Choice equivalent is "every set admits an ordering which is a well order" - that wouldn't really even help with this proof, since it would only tell us that there is some ordering of the natural numbers which is a well order - it doesn't tell us that the usual ordering is one.
$endgroup$
– Nate Eldredge
2 hours ago
1
$begingroup$
@NateEldredge: Indeed, the well-ordering principle (not the similarly-named well-ordering theorem) is equivalent to induction (and probably also to infinite descent, but I haven't worked through that one yet), so if you disallow WOP, then you are going to have a hard time proving a lot of things.
$endgroup$
– Kevin
1 hour ago
$begingroup$
I don't know if it's because of the well-ordering principle ... that's like using a hammer to slice through butter. One does not need the full strength of the AOC to prove such a simple statement.
$endgroup$
– Don Thousand
3 hours ago
$begingroup$
I don't know if it's because of the well-ordering principle ... that's like using a hammer to slice through butter. One does not need the full strength of the AOC to prove such a simple statement.
$endgroup$
– Don Thousand
3 hours ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
3 hours ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
3 hours ago
$begingroup$
@RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
$endgroup$
– Nate Eldredge
2 hours ago
$begingroup$
@RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
$endgroup$
– Nate Eldredge
2 hours ago
1
1
$begingroup$
@DonThousand: I think "well-ordering principle" here refers to the statement "the usual ordering on the natural numbers is a well order". The Axiom of Choice equivalent is "every set admits an ordering which is a well order" - that wouldn't really even help with this proof, since it would only tell us that there is some ordering of the natural numbers which is a well order - it doesn't tell us that the usual ordering is one.
$endgroup$
– Nate Eldredge
2 hours ago
$begingroup$
@DonThousand: I think "well-ordering principle" here refers to the statement "the usual ordering on the natural numbers is a well order". The Axiom of Choice equivalent is "every set admits an ordering which is a well order" - that wouldn't really even help with this proof, since it would only tell us that there is some ordering of the natural numbers which is a well order - it doesn't tell us that the usual ordering is one.
$endgroup$
– Nate Eldredge
2 hours ago
1
1
$begingroup$
@NateEldredge: Indeed, the well-ordering principle (not the similarly-named well-ordering theorem) is equivalent to induction (and probably also to infinite descent, but I haven't worked through that one yet), so if you disallow WOP, then you are going to have a hard time proving a lot of things.
$endgroup$
– Kevin
1 hour ago
$begingroup$
@NateEldredge: Indeed, the well-ordering principle (not the similarly-named well-ordering theorem) is equivalent to induction (and probably also to infinite descent, but I haven't worked through that one yet), so if you disallow WOP, then you are going to have a hard time proving a lot of things.
$endgroup$
– Kevin
1 hour ago
add a comment |
$begingroup$
A proof by induction has base case(s), Let m and n be said base cases. if it's true for m and true for n (not necessarily distinct), then because it's a product, it follows for mn. All the proof supposes, is N=mn for some base case ( primes or prime powers to start, in these cases) with m and n proved. Then it follows for N, which by saying N which
originally was consider the least element of a set of counterexamples, has one, it eliminates all possible least elements for the set we originally supposed existed.
answered 1 hour ago
Roddy MacPheeRoddy MacPhee
537118
$endgroup$
add a comment |
$begingroup$
A proof by induction has base case(s), Let m and n be said base cases. if it's true for m and true for n (not necessarily distinct), then because it's a product, it follows for mn. All the proof supposes, is N=mn for some base case ( primes or prime powers to start, in these cases) with m and n proved. Then it follows for N, which by saying N which
originally was consider the least element of a set of counterexamples, has one, it eliminates all possible least elements for the set we originally supposed existed.
answered 1 hour ago
Roddy MacPheeRoddy MacPhee
537118
$endgroup$
add a comment |
$begingroup$
A proof by induction has base case(s), Let m and n be said base cases. if it's true for m and true for n (not necessarily distinct), then because it's a product, it follows for mn. All the proof supposes, is N=mn for some base case ( primes or prime powers to start, in these cases) with m and n proved. Then it follows for N, which by saying N which
originally was consider the least element of a set of counterexamples, has one, it eliminates all possible least elements for the set we originally supposed existed.
answered 1 hour ago
Roddy MacPheeRoddy MacPhee
537118
$endgroup$
A proof by induction has base case(s), Let m and n be said base cases. if it's true for m and true for n (not necessarily distinct), then because it's a product, it follows for mn. All the proof supposes, is N=mn for some base case ( primes or prime powers to start, in these cases) with m and n proved. Then it follows for N, which by saying N which
originally was consider the least element of a set of counterexamples, has one, it eliminates all possible least elements for the set we originally supposed existed.
answered 1 hour ago
Roddy MacPheeRoddy MacPhee
537118
answered 1 hour ago
Roddy MacPheeRoddy MacPhee
537118
answered 1 hour ago
Roddy MacPheeRoddy MacPhee
537118
answered 1 hour ago
Roddy MacPheeRoddy MacPhee
537118
537118
add a comment |
add a comment |
$begingroup$
I can definitely understand how this can feel a little off.
1) The lemma (as stated in the question) says all nonzero integers. Primes are integers and, by definition, cannot be products of primes. So, I think the lemma probably is actually more along the lines of: "all positive non-prime integers can be written as a product of primes".
2) Also, the statement "since 𝑚,𝑛 are positive and smaller than 𝑁 they must each be a product of primes" doesn't really explain why they must be a product of primes. Since, 𝑁 is the smallest positive non-prime integer that cannot be written as a product of primes (by supposition of the lemma), then 𝑚,𝑛 are either prime themselves or a product of primes (as they are less than 𝑁 and 𝑁 is the smallest number that isn't a product of primes). Either way, they will provide the primes necessary to create 𝑁, making 𝑁 able to be constructed as a product of primes.
Hopefully this helps to see why the proof by contradiction works.
answered 11 mins ago
dudemandudeman
1012
New contributor
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I can definitely understand how this can feel a little off.
1) The lemma (as stated in the question) says all nonzero integers. Primes are integers and, by definition, cannot be products of primes. So, I think the lemma probably is actually more along the lines of: "all positive non-prime integers can be written as a product of primes".
2) Also, the statement "since 𝑚,𝑛 are positive and smaller than 𝑁 they must each be a product of primes" doesn't really explain why they must be a product of primes. Since, 𝑁 is the smallest positive non-prime integer that cannot be written as a product of primes (by supposition of the lemma), then 𝑚,𝑛 are either prime themselves or a product of primes (as they are less than 𝑁 and 𝑁 is the smallest number that isn't a product of primes). Either way, they will provide the primes necessary to create 𝑁, making 𝑁 able to be constructed as a product of primes.
Hopefully this helps to see why the proof by contradiction works.
answered 11 mins ago
dudemandudeman
1012
New contributor
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I can definitely understand how this can feel a little off.
1) The lemma (as stated in the question) says all nonzero integers. Primes are integers and, by definition, cannot be products of primes. So, I think the lemma probably is actually more along the lines of: "all positive non-prime integers can be written as a product of primes".
2) Also, the statement "since 𝑚,𝑛 are positive and smaller than 𝑁 they must each be a product of primes" doesn't really explain why they must be a product of primes. Since, 𝑁 is the smallest positive non-prime integer that cannot be written as a product of primes (by supposition of the lemma), then 𝑚,𝑛 are either prime themselves or a product of primes (as they are less than 𝑁 and 𝑁 is the smallest number that isn't a product of primes). Either way, they will provide the primes necessary to create 𝑁, making 𝑁 able to be constructed as a product of primes.
Hopefully this helps to see why the proof by contradiction works.
answered 11 mins ago
dudemandudeman
1012
New contributor
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I can definitely understand how this can feel a little off.
1) The lemma (as stated in the question) says all nonzero integers. Primes are integers and, by definition, cannot be products of primes. So, I think the lemma probably is actually more along the lines of: "all positive non-prime integers can be written as a product of primes".
2) Also, the statement "since 𝑚,𝑛 are positive and smaller than 𝑁 they must each be a product of primes" doesn't really explain why they must be a product of primes. Since, 𝑁 is the smallest positive non-prime integer that cannot be written as a product of primes (by supposition of the lemma), then 𝑚,𝑛 are either prime themselves or a product of primes (as they are less than 𝑁 and 𝑁 is the smallest number that isn't a product of primes). Either way, they will provide the primes necessary to create 𝑁, making 𝑁 able to be constructed as a product of primes.
Hopefully this helps to see why the proof by contradiction works.
answered 11 mins ago
dudemandudeman
1012
New contributor
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 11 mins ago
dudemandudeman
1012
New contributor
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 11 mins ago
dudemandudeman
1012
answered 11 mins ago
dudemandudeman
1012
1012
New contributor
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
dudeman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
Alena Gusakov is a new contributor. Be nice, and check out our Code of Conduct.
Alena Gusakov is a new contributor. Be nice, and check out our Code of Conduct.
Alena Gusakov is a new contributor. Be nice, and check out our Code of Conduct.
Alena Gusakov is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3161147%2fproof-of-lemma-every-nonzero-integer-can-be-written-as-a-product-of-primes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
That argument is by induction. the result is easy to check for small numbers, so assume it holds up to $N-1$. Then $N$ is either prime, in which case we are done, or it factors as $atimes b$ with $1<a≤b<N-1$ and you can apply the inductive hypothesis to $a,b$. Same argument.
$endgroup$
– lulu
4 hours ago
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
4 hours ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
4 hours ago
$begingroup$
It's not circular, but it could be a lot clearer. It's not strictly necessary to say $n > 1$, since $m$ is positive and $mn$ is also positive.
$endgroup$
– Robert Soupe
3 hours ago
1
$begingroup$
It's a valid proof by infinite descent (a.k.a. minimal criminal), the contrapositive of induction - see the Remark here. You should master both this (negative) and the normal (positive) form of induction.
$endgroup$
– Bill Dubuque
1 hour ago