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

Flux received by a negative charge

Hot bath for aluminium engine block and heads

Find last 3 digits of this monster number

How should I respond when I lied about my education and the company finds out through background check?

Customize circled numbers

Did US corporations pay demonstrators in the German demonstrations against article 13?

What is this type of notehead called?

Why has "pence" been used in this sentence, not "pences"?

Freedom of speech and where it applies

Will adding a BY-SA image to a blog post make the entire post BY-SA?

Proof of Lemma: Every nonzero integer can be written as a product of primes

Is a model fitted to data or is data fitted to a model?

Bob has never been a M before

How to align and center standalone amsmath equations?

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

Can I sign legal documents with a smiley face?

Is XSS in canonical link possible?

What (else) happened July 1st 1858 in London?

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

Why does Async/Await work properly when the loop is inside the async function and not the other way around?

Do Legal Documents Require Signing In Standard Pen Colors?

How do ground effect vehicles perform turns?

Drawing a topological "handle" with Tikz

Engineer refusing to file/disclose patents



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?










share|cite|improve this question









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
    2 hours ago






  • 1




    $begingroup$
    There is nothing missing in this proof. It is just fine. And why “two primes”?
    $endgroup$
    – José Carlos Santos
    2 hours ago










  • $begingroup$
    @JoséCarlosSantos Typo. Fixed.
    $endgroup$
    – Alena Gusakov
    2 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
    1 hour ago















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?










share|cite|improve this question









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
    2 hours ago






  • 1




    $begingroup$
    There is nothing missing in this proof. It is just fine. And why “two primes”?
    $endgroup$
    – José Carlos Santos
    2 hours ago










  • $begingroup$
    @JoséCarlosSantos Typo. Fixed.
    $endgroup$
    – Alena Gusakov
    2 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
    1 hour ago













2












2








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?










share|cite|improve this question









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






share|cite|improve this question









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









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




share|cite|improve this question








edited 1 hour ago









Robert Soupe

11.4k21950




11.4k21950






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 2 hours 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
    2 hours ago






  • 1




    $begingroup$
    There is nothing missing in this proof. It is just fine. And why “two primes”?
    $endgroup$
    – José Carlos Santos
    2 hours ago










  • $begingroup$
    @JoséCarlosSantos Typo. Fixed.
    $endgroup$
    – Alena Gusakov
    2 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
    1 hour ago












  • 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
    2 hours ago






  • 1




    $begingroup$
    There is nothing missing in this proof. It is just fine. And why “two primes”?
    $endgroup$
    – José Carlos Santos
    2 hours ago










  • $begingroup$
    @JoséCarlosSantos Typo. Fixed.
    $endgroup$
    – Alena Gusakov
    2 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
    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
2 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
2 hours ago




1




1




$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
2 hours ago




$begingroup$
There is nothing missing in this proof. It is just fine. And why “two primes”?
$endgroup$
– José Carlos Santos
2 hours ago












$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
2 hours ago




$begingroup$
@JoséCarlosSantos Typo. Fixed.
$endgroup$
– Alena Gusakov
2 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
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
1 hour ago










2 Answers
2






active

oldest

votes


















2












$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









$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
    1 hour ago










  • $begingroup$
    @RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
    $endgroup$
    – Nate Eldredge
    28 mins 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
    26 mins ago


















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









$endgroup$












    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


















    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









    2












    $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









    $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
      1 hour ago










    • $begingroup$
      @RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
      $endgroup$
      – Nate Eldredge
      28 mins 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
      26 mins ago















    2












    $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









    $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
      1 hour ago










    • $begingroup$
      @RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
      $endgroup$
      – Nate Eldredge
      28 mins 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
      26 mins ago













    2












    2








    2





    $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









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







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 2 hours ago









    Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez

    1065




    1065











    • $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
      1 hour ago










    • $begingroup$
      @RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
      $endgroup$
      – Nate Eldredge
      28 mins 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
      26 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$
      @Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
      $endgroup$
      – Robert Soupe
      1 hour ago










    • $begingroup$
      @RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
      $endgroup$
      – Nate Eldredge
      28 mins 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
      26 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
    1 hour ago




    $begingroup$
    @Don What's AOC? I presume you're not talking about Alexandria Ocasio-Cortez.
    $endgroup$
    – Robert Soupe
    1 hour ago












    $begingroup$
    @RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
    $endgroup$
    – Nate Eldredge
    28 mins ago





    $begingroup$
    @RobertSoupe: Axiom of choice. The more usual abbreviation is AC.
    $endgroup$
    – Nate Eldredge
    28 mins 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
    26 mins 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
    26 mins ago











    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









    $endgroup$

















      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









      $endgroup$















        2












        2








        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









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








        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 1 hour ago









        lhflhf

        166k11172402




        166k11172402




















            Alena Gusakov is a new contributor. Be nice, and check out our Code of Conduct.









            draft saved

            draft discarded


















            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            Möglingen Índice Localización Historia Demografía Referencias Enlaces externos Menú de navegación48°53′18″N 9°07′45″E / 48.888333333333, 9.129166666666748°53′18″N 9°07′45″E / 48.888333333333, 9.1291666666667Sitio web oficial Mapa de Möglingen«Gemeinden in Deutschland nach Fläche, Bevölkerung und Postleitzahl am 30.09.2016»Möglingen

            Virtualbox - Configuration error: Querying “UUID” failed (VERR_CFGM_VALUE_NOT_FOUND)“VERR_SUPLIB_WORLD_WRITABLE” error when trying to installing OS in virtualboxVirtual Box Kernel errorFailed to open a seesion for the virtual machineFailed to open a session for the virtual machineUbuntu 14.04 LTS Virtualbox errorcan't use VM VirtualBoxusing virtualboxI can't run Linux-64 Bit on VirtualBoxUnable to insert the virtual optical disk (VBoxguestaddition) in virtual machine for ubuntu server in win 10VirtuaBox in Ubuntu 18.04 Issues with Win10.ISO Installation

            Torre de la Isleta Índice Véase también Referencias Bibliografía Enlaces externos Menú de navegación38°25′58″N 0°23′02″O / 38.43277778, -0.3838888938°25′58″N 0°23′02″O / 38.43277778, -0.38388889Torre de la Illeta de l’Horta o Torre Saleta. Base de datos de bienes inmuebles. Patrimonio Cultural. Secretaría de Estado de CulturaFicha BIC Torre de la Illeta de l’Horta. Dirección General de Patrimonio Cultural. Generalitat ValencianaLugares de interés. Ayuntamiento del CampelloTorre de la Isleta en CastillosNet.org