Proof of Lemma: Every nonzero integer can be written as a product of primesComplete induction proof that every $n > 1$ can be written as a product of primesWhat's wrong with this proof of the infinity of primes?Induction Proof - Primes and Euclid's LemmaEuclid's proof of Infinitude of Primes: If a prime divides an integer, why would it have to divide 1?Proof or disproof that every integer can be written as the sum of a prime and a square.Prove two subsequent primes cannot be written as a product of two primesProof by well ordering: Every positive integer greater than one can be factored as a product of primes.Difficult Q: Show that every integer $n$ can be written in the form $n = a^2 b$….product of distinct primesWhy is the proof not right ? Every positive integer can be written as a product of primes?Proof by well ordering: Every positive integer greater than one can be factored as a product of primes. Part II
Greco-Roman egalitarianism
Does the Mind Blank spell prevent the target from being frightened?
Divine apple island
Should I install hardwood flooring or cabinets first?
Could solar power be utilized and substitute coal in the 19th Century
Gibbs free energy in standard state vs. equilibrium
Why is Arduino resetting while driving motors?
How can "mimic phobia" be cured or prevented?
How will losing mobility of one hand affect my career as a programmer?
How to decide convergence of Integrals
How to color a curve
Can I sign legal documents with a smiley face?
Create all possible words using a set or letters
Is a model fitted to data or is data fitted to a model?
Why do IPv6 unique local addresses have to have a /48 prefix?
Open a doc from terminal, but not by its name
Global amount of publications over time
How much character growth crosses the line into breaking the character
Customize circled numbers
Fuse symbol on toroidal transformer
What does this horizontal bar at the first measure mean?
Is it improper etiquette to ask your opponent what his/her rating is before the game?
Can the Supreme Court overturn an impeachment?
Did arcade monitors have same pixel aspect ratio as TV sets?
Proof of Lemma: Every nonzero integer can be written as a product of primes
Complete induction proof that every $n > 1$ can be written as a product of primesWhat's wrong with this proof of the infinity of primes?Induction Proof - Primes and Euclid's LemmaEuclid's proof of Infinitude of Primes: If a prime divides an integer, why would it have to divide 1?Proof or disproof that every integer can be written as the sum of a prime and a square.Prove two subsequent primes cannot be written as a product of two primesProof by well ordering: Every positive integer greater than one can be factored as a product of primes.Difficult Q: Show that every integer $n$ can be written in the form $n = a^2 b$….product of distinct primesWhy is the proof not right ? Every positive integer can be written as a product of primes?Proof by well ordering: Every positive integer greater than one can be factored as a product of primes. Part II
$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 1 hour ago
Robert Soupe
11.4k21950
asked 1 hour ago
Alena GusakovAlena Gusakov
112
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 1 hour ago
Robert Soupe
11.4k21950
asked 1 hour ago
Alena GusakovAlena Gusakov
112
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
1 hour ago
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
1 hour ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
1 hour 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
52 mins 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 1 hour ago
Robert Soupe
11.4k21950
asked 1 hour ago
Alena GusakovAlena Gusakov
112
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 1 hour ago
Robert Soupe
11.4k21950
asked 1 hour ago
Alena GusakovAlena Gusakov
112
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 1 hour ago
Robert Soupe
11.4k21950
asked 1 hour ago
Alena GusakovAlena Gusakov
112
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 1 hour ago
Robert Soupe
11.4k21950
edited 1 hour ago
Robert Soupe
11.4k21950
edited 1 hour ago
Robert Soupe
11.4k21950
11.4k21950
asked 1 hour ago
Alena GusakovAlena Gusakov
112
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 1 hour ago
Alena GusakovAlena Gusakov
112
asked 1 hour ago
Alena GusakovAlena Gusakov
112
112
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
1 hour ago
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
1 hour ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
1 hour 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
52 mins 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
1 hour ago
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
1 hour ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
1 hour 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
52 mins 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
1 hour 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
1 hour ago
1
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
1 hour ago
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
1 hour ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
1 hour ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
1 hour 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
52 mins 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
52 mins ago
add a comment |
2 Answers
2
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 1 hour 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 1 hour ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
965
$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
1 hour ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
57 mins ago
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
2 Answers
2
active
oldest
votes
2 Answers
2
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 1 hour 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 1 hour 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 1 hour 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 1 hour ago
lhflhf
166k11172402
answered 1 hour ago
lhflhf
166k11172402
answered 1 hour ago
lhflhf
166k11172402
answered 1 hour 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 1 hour ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
965
$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
1 hour ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
57 mins 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 1 hour ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
965
$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
1 hour ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
57 mins 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 1 hour ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
965
$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 1 hour ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
965
answered 1 hour ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
965
answered 1 hour ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
965
answered 1 hour ago
Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez
965
965
$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
1 hour ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
57 mins 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
1 hour ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
57 mins 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
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
1 hour ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
57 mins ago
$begingroup$
@Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
$endgroup$
– Robert Soupe
57 mins ago
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
1 hour ago
1
$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
1 hour ago
$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
1 hour 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
52 mins ago