Ttyjukl

Why do IPv6 unique local addresses have to have a /48 prefix?

Does the Mind Blank spell prevent the target from being frightened?

Global amount of publications over time

Query about absorption line spectra

Has Darkwing Duck ever met Scrooge McDuck?

Is camera lens focus an exact point or a range?

A social experiment. What is the worst that can happen?

How to color a curve

Can someone explain how this makes sense electrically?

What major Native American tribes were around Santa Fe during the late 1850s?

How to align and center standalone amsmath equations?

Freedom of speech and where it applies

Are lightweight LN wallets vulnerable to transaction withholding?

Transformation of random variables and joint distributions

Can somebody explain Brexit in a few child-proof sentences?

Longest common substring in linear time

Can I use my Chinese passport to enter China after I acquired another citizenship?

What's the difference between 違法 and 不法?

Folder comparison

Did arcade monitors have same pixel aspect ratio as TV sets?

Gibbs free energy in standard state vs. equilibrium

How do I repair my stair bannister?

My friend sent me a screenshot of a transaction hash, but when I search for it I find divergent data. What happened?

Is there a conventional notation or name for the slip angle?

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

2

$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

share|cite|improve this question

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
  49 mins ago
  

  
  
  
  

add a comment | 

2

$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

share|cite|improve this question

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
  49 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

share|cite|improve this question

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$

share|cite|improve this question

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.

share|cite|improve this question

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

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

2 Answers
2

active

oldest

votes

2

$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.

share|cite|improve this answer

answered 1 hour ago

lhflhf

166k11172402

$endgroup$

add a comment | 

1

$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.

share|cite|improve this answer

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
  55 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.

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

2

$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.

share|cite|improve this answer

answered 1 hour ago

lhflhf

166k11172402

$endgroup$

add a comment | 

2

$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.

share|cite|improve this answer

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.

share|cite|improve this answer

answered 1 hour ago

lhflhf

166k11172402

$endgroup$

share|cite|improve this answer

answered 1 hour ago

lhflhf

166k11172402

answered 1 hour ago

lhflhf

166k11172402

answered 1 hour ago

lhflhf

166k11172402

1

$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.

share|cite|improve this answer

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
  55 mins ago
  

  
  
  
  

add a comment | 

1

$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.

share|cite|improve this answer

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
  55 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.

share|cite|improve this answer

answered 1 hour ago

Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez

965

$endgroup$

share|cite|improve this answer

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