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












10












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



Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.










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
    yesterday






  • 1




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






  • 4




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








  • 3




    $begingroup$
    $-1$ is an integer, and is not prime...
    $endgroup$
    – Gerrit0
    yesterday






  • 1




    $begingroup$
    @AndreasRejbrand According to the textbook, if p is a prime then -p is a prime :/
    $endgroup$
    – Alena Gusakov
    13 hours ago
















10












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



Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.










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
    yesterday






  • 1




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






  • 4




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








  • 3




    $begingroup$
    $-1$ is an integer, and is not prime...
    $endgroup$
    – Gerrit0
    yesterday






  • 1




    $begingroup$
    @AndreasRejbrand According to the textbook, if p is a prime then -p is a prime :/
    $endgroup$
    – Alena Gusakov
    13 hours ago














10












10








10


1



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



Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.










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?



Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.







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









mrtaurho

6,08771641




6,08771641






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 yesterday









Alena GusakovAlena Gusakov

515




515




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
    yesterday






  • 1




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






  • 4




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








  • 3




    $begingroup$
    $-1$ is an integer, and is not prime...
    $endgroup$
    – Gerrit0
    yesterday






  • 1




    $begingroup$
    @AndreasRejbrand According to the textbook, if p is a prime then -p is a prime :/
    $endgroup$
    – Alena Gusakov
    13 hours 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
    yesterday






  • 1




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






  • 4




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








  • 3




    $begingroup$
    $-1$ is an integer, and is not prime...
    $endgroup$
    – Gerrit0
    yesterday






  • 1




    $begingroup$
    @AndreasRejbrand According to the textbook, if p is a prime then -p is a prime :/
    $endgroup$
    – Alena Gusakov
    13 hours 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
yesterday




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




1




1




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




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




4




4




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






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






3




3




$begingroup$
$-1$ is an integer, and is not prime...
$endgroup$
– Gerrit0
yesterday




$begingroup$
$-1$ is an integer, and is not prime...
$endgroup$
– Gerrit0
yesterday




1




1




$begingroup$
@AndreasRejbrand According to the textbook, if p is a prime then -p is a prime :/
$endgroup$
– Alena Gusakov
13 hours ago




$begingroup$
@AndreasRejbrand According to the textbook, if p is a prime then -p is a prime :/
$endgroup$
– Alena Gusakov
13 hours ago










8 Answers
8






active

oldest

votes


















16












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









  • 11




    $begingroup$
    This is equivalent, so how is it "so much clearer"? Personally, I find the original clearer.
    $endgroup$
    – John Coleman
    17 hours ago










  • $begingroup$
    +1 for “the direct proof by induction is so much clearer”. I’ve seen so many unnecessary proofs by induction.
    $endgroup$
    – Bob Krueger
    16 hours ago










  • $begingroup$
    @JohnColeman Also, the OP might be interested in how the infinite descent method has been 'pushed' in number theory. And Euclid had no problem with it! en.wikipedia.org/wiki/Proof_by_infinite_descent#Number_theory
    $endgroup$
    – CopyPasteIt
    9 hours ago





















10












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









  • 1




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






  • 3




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






  • 1




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








  • 11




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






  • 4




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





















4












$begingroup$


I feel like this proof kind of presupposes the lemma.




Because it does.

It says so right in the first two sentences, which can be rephrased as:




Let $N$ be the smallest positive integer that cannot be written as a product of primes.




So yes, the proof assumes that all positive integers smaller than $N$ can be written as a product of primes.

This is OK, though, because it is trivially true for the smallest integers: 1, 2. The proof builds on that to infer that no such an $N$ exists where the lemma is not true.






share|cite|improve this answer








New contributor




walen is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$





















    3












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






    share|cite|improve this answer








    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$













    • $begingroup$
      As far as your (1) is concerned, I think this is just a matter of "over-mathematical" style in the question. 35 is a product of primes. It is a product of the two primes 5 and 7. 37 is a product of primes. It is a product of the one primes 37. But you have raised the extra, interesting point: the statement is "every non-zero integer" but the proof assumes integers >1. Which rather implies that 1 is either not an integer or not non-zero!
      $endgroup$
      – Martin Kochanski
      19 hours ago












    • $begingroup$
      @MartinKochanski The standard way of dealing with $1$ is that the product of zero terms is $1$ by convention, so $1$ is the product of zero primes.
      $endgroup$
      – Especially Lime
      16 hours ago



















    3












    $begingroup$

    An integer $n$ is said to be a composite if it can be expressed as the product of two integers $a$ and $b$ with $a notin {-1,0,1}$ and $b notin {-1,0,1}$.



    An integers $p notin {-1,0,1}$ that is not a composite is called a prime number.



    Recall the method of infinite descent used in mathematical proofs.



    Suppose $m notin {-1,0,1}$ and it can't be expressed as a product of primes. If $m lt 0$ then it is certainly true that the positive number $-m$ can't be factored into primes. So the existence of $m$ allows us to assert that there are positive integers greater than $1$ that can't be factored into a product of prime numbers.



    So using infinite descent, we have a minimal $n > 1$ that can't be written as a product of primes. In particular, $n$ can't be a prime. But then it must be a composite, and we can write



    $quad n = st text{ with } s,t gt 1$



    Note: The composite factors $s$ and $t$ must both be positive or negative.

    If they are both negative, replace $s$ with $-s$ and $t$ with $-t$.



    But then $s lt n$ and so it can be written as a product of primes. Similarly, $t$ can be written as a product of primes. But then $n$ itself is a product of primes. But this is not possible by our choice of $n$. So the initial assumption of the existence of $m notin {-1,0,1}$ with no prime factorization leads to a contradiction.



    So every $n notin {-1,0,1}$ has a prime factorization.






    share|cite|improve this answer











    $endgroup$





















      3












      $begingroup$


      I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.




      No apology is necessary since your question is by no means silly. It is not at all surprising that you are puzzled by the cited exposition since it is incredibly sloppy. Kudos to you for reading it very carefully and noticing these problems.




      Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.




      Let's examine closely that initial section on primes and prime factorizations.



      On page $1$ begins a section titled "Unique Factorization in $Bbb Z$" where they briefly review divisibility of "natural numbers $1,2,3ldots"$ This leads to the following "definition" of a prime:




      Numbers that cannot be factored further are called primes. To be more precise, we say that a number $p$ is a prime if its only divisors are $1$ and $p.$




      This is imprecise. Is $1$ a prime by this definition? In the next paragraph we find




      The first prime numbers are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,ldots$




      So $1$ is not prime. That agrees with modern conventions.



      On the next page they segue into factorization in the ring of integers $Bbb Z$ where they write




      If $p$ is a positive prime, $-p$ will also be a prime. We shall not consider $1$ or $-1$ as primes even though they fit the definition.




      This poses a few problems. They now claim that $1$ does fit the prior definition of a prime, but they didn't list it above (or explain why it was excluded). Further it implies that $ p = -2$ is a prime but it doesn't fit the above definition (it has divisors $,pm1, pm 2,,$ not only $1$ and $p$). They don't give any definition of a prime integer (vs. natural).



      Readers familiar with basic ring theory and factorization in integral domains will likely have no problem inferring what is intended (the notion of an irreducible or indecomposable element), but any careful reader lacking such background will likely be quite puzzled by these inconsistencies and gaps.



      As such, it comes as no surprise that the following proof employing these fuzzy notions may well prove troublesome for readers unfamiliar with the intended notions.




      Lemma $1.$ Every nonzero integer can be written as a product of primes.



      PROOF $ $ Assume that there is an integer 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$ and $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.




      The proof has many problems. It doesn't properly handle the (implied) prime factorization of $pm1$ and they forgot to handle the possibility that the counterexample is negative (w.l.o.g. reducing to a positive counterexample).



      Considering all of the above problems, it is no wonder that you found this proof confusing.




      The proof can be given in a more positive way by using mathematical
      induction. It is enough to prove the result for all positive integers. $2$ is a
      prime. Suppose that $2 < N$ and that we have proved the result for all
      numbers $m$ such that $2 < m < N.$ We wish to show that $N$ is a product of
      primes. If $N$ is a prime, there is nothing to do. If $N$ is not a prime, then
      $N = mn,$ where $2 < m,, n < N.$ By induction both $m$ and $n$ are products of
      primes and thus so is $N.$




      Here they've reformulated the induction from negative form - an (infinite) descent on counterexamples (or a "minimal criminal") - into a positive ascent, i.e. into a complete (or strong) induction, and they give some hint about the reduction to the positive case, but still there is no handling of $pm1$. What is actually intended can be inferred from the next theorem they present.




      Theorem $1.$ For every nonzero integer $n$ there is a prime factorization



      $$ n, = (-1)^{e(n)} prod_p p^{a(p)}$$



      with the exponents uniquely determined by $n$. Here $e(n) = 0$ or $1$ depending on whether $n$ is positive or negative and where the product is over all positive primes. The exponents $a(p)$ are nonnegative integers and, of course, $a(p) = 0$ for all but finitely many primes.




      That explains how they handle the prime factorization of $pm1$ and the reduction to positive primes. With that in mind you should be able to fix the proof of the lemma.



      As above, often when there is puzzling exposition in textbooks it can be clarified by reading a bit further to help infer what was intended. But - of course - that is no excuse for sloppy exposition.






      share|cite|improve this answer











      $endgroup$













      • $begingroup$
        Prima facie, by examining the Q&A/comments here, and even before your answer, I knew that the book could be depended on one thing - that any reader would be forced to put in their own finishing touches to make the material 'crystallize '. . (+1) for providing a (partial) critical review of the book.
        $endgroup$
        – CopyPasteIt
        1 hour ago










      • $begingroup$
        @CopyPasteIt It is a popular and widely-respected textbook.
        $endgroup$
        – Bill Dubuque
        59 mins ago










      • $begingroup$
        Sure hope that knowing that prime numbers can be negative is used in later chapters. And that we all nod our heads and say 'what a modern and elegant approach'.
        $endgroup$
        – CopyPasteIt
        51 mins ago



















      2












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






      share|cite|improve this answer









      $endgroup$





















        1












        $begingroup$

        There is a property of the natural numbers called well-order. A set is well-ordered if every non-empty subset has a least element. So given any property $P$:




        1. The set of numbers for which $P(n)$ is false is either empty or has a least element.


        2. Suppose there is some number $n_0$ such that $P(n_0)$ is false. If $n_0$ is the least such number, then obviously $P(n_0-1)$ is true [1] (otherwise $n_0-1$ would be a number for which $P$ is false that is smaller than $n_0$, and so $n_0$ wouldn't be the smallest such number).


        3. Thus, if we can prove that there is no number $n_0$ such that $P(n_0-1)$ is true and $P(n_0)$ is false (i.e. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$", then we have shown that the set of numbers for which $P$ is false has no least element.


        4. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$" is equivalent to "$forall n_0: (neg P(n_0-1) lor P(n_0))$", which is in turn equivalent to "$forall n_0: (P(n_0-1) rightarrow P(n_0))$".


        5. Thus, if we can prove $forall n_0: (P(n_0-1) rightarrow P(n_0))$, then it follows that the set of numbers for which $P(n)$ is false does not have a least element. Since all non-empty sets of natural numbers have a least element, this set must be empty. That is, there are no numbers for which $P(n)$ is false, i.e. $P(n)$ is true for all $n$.



        [1] There is also the possibility that $n_0-1$ isn't a natural number, which happens when $n_0=0$. Dealing with this possibility requires proving that $P(0)$ is true separately, which is why induction proofs require a base case.



        So that's the concept behind induction proofs: if the proposition isn't true for all numbers, then there is a non-empty set of numbers for which it is false, which has to have a least element, which means that we have to go from "true" to "false" at some point. Inductive proofs thus look a bit like circular reasoning: you start assuming that the proposition is true, and use that to prove that the proposition is true. But what makes it non-fallacious is that you prove that the proposition is true for a later number by assuming that it's true for an earlier number.



        The proof that you cite is using the same basic principle as induction, namely the well-order of the natural numbers, but it is skipping the one-by-one sort of process that induction proofs usually use. Instead of saying "If $P(n_0)$ is false, then $P(n_0-1)$ being true leads to a contradiction", it's saying "If $P(n_0)$ is false, then $P(n)$ being true for $n<n_0$ leads to a contradiction". Like a standard induction proof, it superficially looks like circular reasoning, but isn't, because it's proving that the proposition is true for $N$ using the fact that it's true for smaller numbers.






        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-integer-can-be-written-as-a-product-of-primes%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          8 Answers
          8






          active

          oldest

          votes








          8 Answers
          8






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          16












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









          • 11




            $begingroup$
            This is equivalent, so how is it "so much clearer"? Personally, I find the original clearer.
            $endgroup$
            – John Coleman
            17 hours ago










          • $begingroup$
            +1 for “the direct proof by induction is so much clearer”. I’ve seen so many unnecessary proofs by induction.
            $endgroup$
            – Bob Krueger
            16 hours ago










          • $begingroup$
            @JohnColeman Also, the OP might be interested in how the infinite descent method has been 'pushed' in number theory. And Euclid had no problem with it! en.wikipedia.org/wiki/Proof_by_infinite_descent#Number_theory
            $endgroup$
            – CopyPasteIt
            9 hours ago


















          16












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









          • 11




            $begingroup$
            This is equivalent, so how is it "so much clearer"? Personally, I find the original clearer.
            $endgroup$
            – John Coleman
            17 hours ago










          • $begingroup$
            +1 for “the direct proof by induction is so much clearer”. I’ve seen so many unnecessary proofs by induction.
            $endgroup$
            – Bob Krueger
            16 hours ago










          • $begingroup$
            @JohnColeman Also, the OP might be interested in how the infinite descent method has been 'pushed' in number theory. And Euclid had no problem with it! en.wikipedia.org/wiki/Proof_by_infinite_descent#Number_theory
            $endgroup$
            – CopyPasteIt
            9 hours ago
















          16












          16








          16





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









          lhflhf

          167k11172403




          167k11172403








          • 11




            $begingroup$
            This is equivalent, so how is it "so much clearer"? Personally, I find the original clearer.
            $endgroup$
            – John Coleman
            17 hours ago










          • $begingroup$
            +1 for “the direct proof by induction is so much clearer”. I’ve seen so many unnecessary proofs by induction.
            $endgroup$
            – Bob Krueger
            16 hours ago










          • $begingroup$
            @JohnColeman Also, the OP might be interested in how the infinite descent method has been 'pushed' in number theory. And Euclid had no problem with it! en.wikipedia.org/wiki/Proof_by_infinite_descent#Number_theory
            $endgroup$
            – CopyPasteIt
            9 hours ago
















          • 11




            $begingroup$
            This is equivalent, so how is it "so much clearer"? Personally, I find the original clearer.
            $endgroup$
            – John Coleman
            17 hours ago










          • $begingroup$
            +1 for “the direct proof by induction is so much clearer”. I’ve seen so many unnecessary proofs by induction.
            $endgroup$
            – Bob Krueger
            16 hours ago










          • $begingroup$
            @JohnColeman Also, the OP might be interested in how the infinite descent method has been 'pushed' in number theory. And Euclid had no problem with it! en.wikipedia.org/wiki/Proof_by_infinite_descent#Number_theory
            $endgroup$
            – CopyPasteIt
            9 hours ago










          11




          11




          $begingroup$
          This is equivalent, so how is it "so much clearer"? Personally, I find the original clearer.
          $endgroup$
          – John Coleman
          17 hours ago




          $begingroup$
          This is equivalent, so how is it "so much clearer"? Personally, I find the original clearer.
          $endgroup$
          – John Coleman
          17 hours ago












          $begingroup$
          +1 for “the direct proof by induction is so much clearer”. I’ve seen so many unnecessary proofs by induction.
          $endgroup$
          – Bob Krueger
          16 hours ago




          $begingroup$
          +1 for “the direct proof by induction is so much clearer”. I’ve seen so many unnecessary proofs by induction.
          $endgroup$
          – Bob Krueger
          16 hours ago












          $begingroup$
          @JohnColeman Also, the OP might be interested in how the infinite descent method has been 'pushed' in number theory. And Euclid had no problem with it! en.wikipedia.org/wiki/Proof_by_infinite_descent#Number_theory
          $endgroup$
          – CopyPasteIt
          9 hours ago






          $begingroup$
          @JohnColeman Also, the OP might be interested in how the infinite descent method has been 'pushed' in number theory. And Euclid had no problem with it! en.wikipedia.org/wiki/Proof_by_infinite_descent#Number_theory
          $endgroup$
          – CopyPasteIt
          9 hours ago













          10












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









          • 1




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






          • 3




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






          • 1




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








          • 11




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






          • 4




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


















          10












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









          • 1




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






          • 3




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






          • 1




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








          • 11




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






          • 4




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
















          10












          10








          10





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









          Edgar Jaramillo RodriguezEdgar Jaramillo Rodriguez

          1997




          1997








          • 1




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






          • 3




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






          • 1




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








          • 11




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






          • 4




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
















          • 1




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






          • 3




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






          • 1




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








          • 11




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






          • 4




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










          1




          1




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




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




          3




          3




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




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




          1




          1




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






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






          11




          11




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




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




          4




          4




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






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













          4












          $begingroup$


          I feel like this proof kind of presupposes the lemma.




          Because it does.

          It says so right in the first two sentences, which can be rephrased as:




          Let $N$ be the smallest positive integer that cannot be written as a product of primes.




          So yes, the proof assumes that all positive integers smaller than $N$ can be written as a product of primes.

          This is OK, though, because it is trivially true for the smallest integers: 1, 2. The proof builds on that to infer that no such an $N$ exists where the lemma is not true.






          share|cite|improve this answer








          New contributor




          walen is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.






          $endgroup$


















            4












            $begingroup$


            I feel like this proof kind of presupposes the lemma.




            Because it does.

            It says so right in the first two sentences, which can be rephrased as:




            Let $N$ be the smallest positive integer that cannot be written as a product of primes.




            So yes, the proof assumes that all positive integers smaller than $N$ can be written as a product of primes.

            This is OK, though, because it is trivially true for the smallest integers: 1, 2. The proof builds on that to infer that no such an $N$ exists where the lemma is not true.






            share|cite|improve this answer








            New contributor




            walen is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.






            $endgroup$
















              4












              4








              4





              $begingroup$


              I feel like this proof kind of presupposes the lemma.




              Because it does.

              It says so right in the first two sentences, which can be rephrased as:




              Let $N$ be the smallest positive integer that cannot be written as a product of primes.




              So yes, the proof assumes that all positive integers smaller than $N$ can be written as a product of primes.

              This is OK, though, because it is trivially true for the smallest integers: 1, 2. The proof builds on that to infer that no such an $N$ exists where the lemma is not true.






              share|cite|improve this answer








              New contributor




              walen is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              $endgroup$




              I feel like this proof kind of presupposes the lemma.




              Because it does.

              It says so right in the first two sentences, which can be rephrased as:




              Let $N$ be the smallest positive integer that cannot be written as a product of primes.




              So yes, the proof assumes that all positive integers smaller than $N$ can be written as a product of primes.

              This is OK, though, because it is trivially true for the smallest integers: 1, 2. The proof builds on that to infer that no such an $N$ exists where the lemma is not true.







              share|cite|improve this answer








              New contributor




              walen 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 answer



              share|cite|improve this answer






              New contributor




              walen is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.









              answered 13 hours ago









              walenwalen

              1493




              1493




              New contributor




              walen is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.





              New contributor





              walen is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              walen is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.























                  3












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






                  share|cite|improve this answer








                  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$













                  • $begingroup$
                    As far as your (1) is concerned, I think this is just a matter of "over-mathematical" style in the question. 35 is a product of primes. It is a product of the two primes 5 and 7. 37 is a product of primes. It is a product of the one primes 37. But you have raised the extra, interesting point: the statement is "every non-zero integer" but the proof assumes integers >1. Which rather implies that 1 is either not an integer or not non-zero!
                    $endgroup$
                    – Martin Kochanski
                    19 hours ago












                  • $begingroup$
                    @MartinKochanski The standard way of dealing with $1$ is that the product of zero terms is $1$ by convention, so $1$ is the product of zero primes.
                    $endgroup$
                    – Especially Lime
                    16 hours ago
















                  3












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






                  share|cite|improve this answer








                  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$













                  • $begingroup$
                    As far as your (1) is concerned, I think this is just a matter of "over-mathematical" style in the question. 35 is a product of primes. It is a product of the two primes 5 and 7. 37 is a product of primes. It is a product of the one primes 37. But you have raised the extra, interesting point: the statement is "every non-zero integer" but the proof assumes integers >1. Which rather implies that 1 is either not an integer or not non-zero!
                    $endgroup$
                    – Martin Kochanski
                    19 hours ago












                  • $begingroup$
                    @MartinKochanski The standard way of dealing with $1$ is that the product of zero terms is $1$ by convention, so $1$ is the product of zero primes.
                    $endgroup$
                    – Especially Lime
                    16 hours ago














                  3












                  3








                  3





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






                  share|cite|improve this answer








                  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.







                  share|cite|improve this answer








                  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.









                  share|cite|improve this answer



                  share|cite|improve this answer






                  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 yesterday









                  dudemandudeman

                  1393




                  1393




                  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.












                  • $begingroup$
                    As far as your (1) is concerned, I think this is just a matter of "over-mathematical" style in the question. 35 is a product of primes. It is a product of the two primes 5 and 7. 37 is a product of primes. It is a product of the one primes 37. But you have raised the extra, interesting point: the statement is "every non-zero integer" but the proof assumes integers >1. Which rather implies that 1 is either not an integer or not non-zero!
                    $endgroup$
                    – Martin Kochanski
                    19 hours ago












                  • $begingroup$
                    @MartinKochanski The standard way of dealing with $1$ is that the product of zero terms is $1$ by convention, so $1$ is the product of zero primes.
                    $endgroup$
                    – Especially Lime
                    16 hours ago


















                  • $begingroup$
                    As far as your (1) is concerned, I think this is just a matter of "over-mathematical" style in the question. 35 is a product of primes. It is a product of the two primes 5 and 7. 37 is a product of primes. It is a product of the one primes 37. But you have raised the extra, interesting point: the statement is "every non-zero integer" but the proof assumes integers >1. Which rather implies that 1 is either not an integer or not non-zero!
                    $endgroup$
                    – Martin Kochanski
                    19 hours ago












                  • $begingroup$
                    @MartinKochanski The standard way of dealing with $1$ is that the product of zero terms is $1$ by convention, so $1$ is the product of zero primes.
                    $endgroup$
                    – Especially Lime
                    16 hours ago
















                  $begingroup$
                  As far as your (1) is concerned, I think this is just a matter of "over-mathematical" style in the question. 35 is a product of primes. It is a product of the two primes 5 and 7. 37 is a product of primes. It is a product of the one primes 37. But you have raised the extra, interesting point: the statement is "every non-zero integer" but the proof assumes integers >1. Which rather implies that 1 is either not an integer or not non-zero!
                  $endgroup$
                  – Martin Kochanski
                  19 hours ago






                  $begingroup$
                  As far as your (1) is concerned, I think this is just a matter of "over-mathematical" style in the question. 35 is a product of primes. It is a product of the two primes 5 and 7. 37 is a product of primes. It is a product of the one primes 37. But you have raised the extra, interesting point: the statement is "every non-zero integer" but the proof assumes integers >1. Which rather implies that 1 is either not an integer or not non-zero!
                  $endgroup$
                  – Martin Kochanski
                  19 hours ago














                  $begingroup$
                  @MartinKochanski The standard way of dealing with $1$ is that the product of zero terms is $1$ by convention, so $1$ is the product of zero primes.
                  $endgroup$
                  – Especially Lime
                  16 hours ago




                  $begingroup$
                  @MartinKochanski The standard way of dealing with $1$ is that the product of zero terms is $1$ by convention, so $1$ is the product of zero primes.
                  $endgroup$
                  – Especially Lime
                  16 hours ago











                  3












                  $begingroup$

                  An integer $n$ is said to be a composite if it can be expressed as the product of two integers $a$ and $b$ with $a notin {-1,0,1}$ and $b notin {-1,0,1}$.



                  An integers $p notin {-1,0,1}$ that is not a composite is called a prime number.



                  Recall the method of infinite descent used in mathematical proofs.



                  Suppose $m notin {-1,0,1}$ and it can't be expressed as a product of primes. If $m lt 0$ then it is certainly true that the positive number $-m$ can't be factored into primes. So the existence of $m$ allows us to assert that there are positive integers greater than $1$ that can't be factored into a product of prime numbers.



                  So using infinite descent, we have a minimal $n > 1$ that can't be written as a product of primes. In particular, $n$ can't be a prime. But then it must be a composite, and we can write



                  $quad n = st text{ with } s,t gt 1$



                  Note: The composite factors $s$ and $t$ must both be positive or negative.

                  If they are both negative, replace $s$ with $-s$ and $t$ with $-t$.



                  But then $s lt n$ and so it can be written as a product of primes. Similarly, $t$ can be written as a product of primes. But then $n$ itself is a product of primes. But this is not possible by our choice of $n$. So the initial assumption of the existence of $m notin {-1,0,1}$ with no prime factorization leads to a contradiction.



                  So every $n notin {-1,0,1}$ has a prime factorization.






                  share|cite|improve this answer











                  $endgroup$


















                    3












                    $begingroup$

                    An integer $n$ is said to be a composite if it can be expressed as the product of two integers $a$ and $b$ with $a notin {-1,0,1}$ and $b notin {-1,0,1}$.



                    An integers $p notin {-1,0,1}$ that is not a composite is called a prime number.



                    Recall the method of infinite descent used in mathematical proofs.



                    Suppose $m notin {-1,0,1}$ and it can't be expressed as a product of primes. If $m lt 0$ then it is certainly true that the positive number $-m$ can't be factored into primes. So the existence of $m$ allows us to assert that there are positive integers greater than $1$ that can't be factored into a product of prime numbers.



                    So using infinite descent, we have a minimal $n > 1$ that can't be written as a product of primes. In particular, $n$ can't be a prime. But then it must be a composite, and we can write



                    $quad n = st text{ with } s,t gt 1$



                    Note: The composite factors $s$ and $t$ must both be positive or negative.

                    If they are both negative, replace $s$ with $-s$ and $t$ with $-t$.



                    But then $s lt n$ and so it can be written as a product of primes. Similarly, $t$ can be written as a product of primes. But then $n$ itself is a product of primes. But this is not possible by our choice of $n$. So the initial assumption of the existence of $m notin {-1,0,1}$ with no prime factorization leads to a contradiction.



                    So every $n notin {-1,0,1}$ has a prime factorization.






                    share|cite|improve this answer











                    $endgroup$
















                      3












                      3








                      3





                      $begingroup$

                      An integer $n$ is said to be a composite if it can be expressed as the product of two integers $a$ and $b$ with $a notin {-1,0,1}$ and $b notin {-1,0,1}$.



                      An integers $p notin {-1,0,1}$ that is not a composite is called a prime number.



                      Recall the method of infinite descent used in mathematical proofs.



                      Suppose $m notin {-1,0,1}$ and it can't be expressed as a product of primes. If $m lt 0$ then it is certainly true that the positive number $-m$ can't be factored into primes. So the existence of $m$ allows us to assert that there are positive integers greater than $1$ that can't be factored into a product of prime numbers.



                      So using infinite descent, we have a minimal $n > 1$ that can't be written as a product of primes. In particular, $n$ can't be a prime. But then it must be a composite, and we can write



                      $quad n = st text{ with } s,t gt 1$



                      Note: The composite factors $s$ and $t$ must both be positive or negative.

                      If they are both negative, replace $s$ with $-s$ and $t$ with $-t$.



                      But then $s lt n$ and so it can be written as a product of primes. Similarly, $t$ can be written as a product of primes. But then $n$ itself is a product of primes. But this is not possible by our choice of $n$. So the initial assumption of the existence of $m notin {-1,0,1}$ with no prime factorization leads to a contradiction.



                      So every $n notin {-1,0,1}$ has a prime factorization.






                      share|cite|improve this answer











                      $endgroup$



                      An integer $n$ is said to be a composite if it can be expressed as the product of two integers $a$ and $b$ with $a notin {-1,0,1}$ and $b notin {-1,0,1}$.



                      An integers $p notin {-1,0,1}$ that is not a composite is called a prime number.



                      Recall the method of infinite descent used in mathematical proofs.



                      Suppose $m notin {-1,0,1}$ and it can't be expressed as a product of primes. If $m lt 0$ then it is certainly true that the positive number $-m$ can't be factored into primes. So the existence of $m$ allows us to assert that there are positive integers greater than $1$ that can't be factored into a product of prime numbers.



                      So using infinite descent, we have a minimal $n > 1$ that can't be written as a product of primes. In particular, $n$ can't be a prime. But then it must be a composite, and we can write



                      $quad n = st text{ with } s,t gt 1$



                      Note: The composite factors $s$ and $t$ must both be positive or negative.

                      If they are both negative, replace $s$ with $-s$ and $t$ with $-t$.



                      But then $s lt n$ and so it can be written as a product of primes. Similarly, $t$ can be written as a product of primes. But then $n$ itself is a product of primes. But this is not possible by our choice of $n$. So the initial assumption of the existence of $m notin {-1,0,1}$ with no prime factorization leads to a contradiction.



                      So every $n notin {-1,0,1}$ has a prime factorization.







                      share|cite|improve this answer














                      share|cite|improve this answer



                      share|cite|improve this answer








                      edited 12 hours ago

























                      answered 12 hours ago









                      CopyPasteItCopyPasteIt

                      4,2631728




                      4,2631728























                          3












                          $begingroup$


                          I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.




                          No apology is necessary since your question is by no means silly. It is not at all surprising that you are puzzled by the cited exposition since it is incredibly sloppy. Kudos to you for reading it very carefully and noticing these problems.




                          Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.




                          Let's examine closely that initial section on primes and prime factorizations.



                          On page $1$ begins a section titled "Unique Factorization in $Bbb Z$" where they briefly review divisibility of "natural numbers $1,2,3ldots"$ This leads to the following "definition" of a prime:




                          Numbers that cannot be factored further are called primes. To be more precise, we say that a number $p$ is a prime if its only divisors are $1$ and $p.$




                          This is imprecise. Is $1$ a prime by this definition? In the next paragraph we find




                          The first prime numbers are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,ldots$




                          So $1$ is not prime. That agrees with modern conventions.



                          On the next page they segue into factorization in the ring of integers $Bbb Z$ where they write




                          If $p$ is a positive prime, $-p$ will also be a prime. We shall not consider $1$ or $-1$ as primes even though they fit the definition.




                          This poses a few problems. They now claim that $1$ does fit the prior definition of a prime, but they didn't list it above (or explain why it was excluded). Further it implies that $ p = -2$ is a prime but it doesn't fit the above definition (it has divisors $,pm1, pm 2,,$ not only $1$ and $p$). They don't give any definition of a prime integer (vs. natural).



                          Readers familiar with basic ring theory and factorization in integral domains will likely have no problem inferring what is intended (the notion of an irreducible or indecomposable element), but any careful reader lacking such background will likely be quite puzzled by these inconsistencies and gaps.



                          As such, it comes as no surprise that the following proof employing these fuzzy notions may well prove troublesome for readers unfamiliar with the intended notions.




                          Lemma $1.$ Every nonzero integer can be written as a product of primes.



                          PROOF $ $ Assume that there is an integer 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$ and $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.




                          The proof has many problems. It doesn't properly handle the (implied) prime factorization of $pm1$ and they forgot to handle the possibility that the counterexample is negative (w.l.o.g. reducing to a positive counterexample).



                          Considering all of the above problems, it is no wonder that you found this proof confusing.




                          The proof can be given in a more positive way by using mathematical
                          induction. It is enough to prove the result for all positive integers. $2$ is a
                          prime. Suppose that $2 < N$ and that we have proved the result for all
                          numbers $m$ such that $2 < m < N.$ We wish to show that $N$ is a product of
                          primes. If $N$ is a prime, there is nothing to do. If $N$ is not a prime, then
                          $N = mn,$ where $2 < m,, n < N.$ By induction both $m$ and $n$ are products of
                          primes and thus so is $N.$




                          Here they've reformulated the induction from negative form - an (infinite) descent on counterexamples (or a "minimal criminal") - into a positive ascent, i.e. into a complete (or strong) induction, and they give some hint about the reduction to the positive case, but still there is no handling of $pm1$. What is actually intended can be inferred from the next theorem they present.




                          Theorem $1.$ For every nonzero integer $n$ there is a prime factorization



                          $$ n, = (-1)^{e(n)} prod_p p^{a(p)}$$



                          with the exponents uniquely determined by $n$. Here $e(n) = 0$ or $1$ depending on whether $n$ is positive or negative and where the product is over all positive primes. The exponents $a(p)$ are nonnegative integers and, of course, $a(p) = 0$ for all but finitely many primes.




                          That explains how they handle the prime factorization of $pm1$ and the reduction to positive primes. With that in mind you should be able to fix the proof of the lemma.



                          As above, often when there is puzzling exposition in textbooks it can be clarified by reading a bit further to help infer what was intended. But - of course - that is no excuse for sloppy exposition.






                          share|cite|improve this answer











                          $endgroup$













                          • $begingroup$
                            Prima facie, by examining the Q&A/comments here, and even before your answer, I knew that the book could be depended on one thing - that any reader would be forced to put in their own finishing touches to make the material 'crystallize '. . (+1) for providing a (partial) critical review of the book.
                            $endgroup$
                            – CopyPasteIt
                            1 hour ago










                          • $begingroup$
                            @CopyPasteIt It is a popular and widely-respected textbook.
                            $endgroup$
                            – Bill Dubuque
                            59 mins ago










                          • $begingroup$
                            Sure hope that knowing that prime numbers can be negative is used in later chapters. And that we all nod our heads and say 'what a modern and elegant approach'.
                            $endgroup$
                            – CopyPasteIt
                            51 mins ago
















                          3












                          $begingroup$


                          I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.




                          No apology is necessary since your question is by no means silly. It is not at all surprising that you are puzzled by the cited exposition since it is incredibly sloppy. Kudos to you for reading it very carefully and noticing these problems.




                          Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.




                          Let's examine closely that initial section on primes and prime factorizations.



                          On page $1$ begins a section titled "Unique Factorization in $Bbb Z$" where they briefly review divisibility of "natural numbers $1,2,3ldots"$ This leads to the following "definition" of a prime:




                          Numbers that cannot be factored further are called primes. To be more precise, we say that a number $p$ is a prime if its only divisors are $1$ and $p.$




                          This is imprecise. Is $1$ a prime by this definition? In the next paragraph we find




                          The first prime numbers are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,ldots$




                          So $1$ is not prime. That agrees with modern conventions.



                          On the next page they segue into factorization in the ring of integers $Bbb Z$ where they write




                          If $p$ is a positive prime, $-p$ will also be a prime. We shall not consider $1$ or $-1$ as primes even though they fit the definition.




                          This poses a few problems. They now claim that $1$ does fit the prior definition of a prime, but they didn't list it above (or explain why it was excluded). Further it implies that $ p = -2$ is a prime but it doesn't fit the above definition (it has divisors $,pm1, pm 2,,$ not only $1$ and $p$). They don't give any definition of a prime integer (vs. natural).



                          Readers familiar with basic ring theory and factorization in integral domains will likely have no problem inferring what is intended (the notion of an irreducible or indecomposable element), but any careful reader lacking such background will likely be quite puzzled by these inconsistencies and gaps.



                          As such, it comes as no surprise that the following proof employing these fuzzy notions may well prove troublesome for readers unfamiliar with the intended notions.




                          Lemma $1.$ Every nonzero integer can be written as a product of primes.



                          PROOF $ $ Assume that there is an integer 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$ and $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.




                          The proof has many problems. It doesn't properly handle the (implied) prime factorization of $pm1$ and they forgot to handle the possibility that the counterexample is negative (w.l.o.g. reducing to a positive counterexample).



                          Considering all of the above problems, it is no wonder that you found this proof confusing.




                          The proof can be given in a more positive way by using mathematical
                          induction. It is enough to prove the result for all positive integers. $2$ is a
                          prime. Suppose that $2 < N$ and that we have proved the result for all
                          numbers $m$ such that $2 < m < N.$ We wish to show that $N$ is a product of
                          primes. If $N$ is a prime, there is nothing to do. If $N$ is not a prime, then
                          $N = mn,$ where $2 < m,, n < N.$ By induction both $m$ and $n$ are products of
                          primes and thus so is $N.$




                          Here they've reformulated the induction from negative form - an (infinite) descent on counterexamples (or a "minimal criminal") - into a positive ascent, i.e. into a complete (or strong) induction, and they give some hint about the reduction to the positive case, but still there is no handling of $pm1$. What is actually intended can be inferred from the next theorem they present.




                          Theorem $1.$ For every nonzero integer $n$ there is a prime factorization



                          $$ n, = (-1)^{e(n)} prod_p p^{a(p)}$$



                          with the exponents uniquely determined by $n$. Here $e(n) = 0$ or $1$ depending on whether $n$ is positive or negative and where the product is over all positive primes. The exponents $a(p)$ are nonnegative integers and, of course, $a(p) = 0$ for all but finitely many primes.




                          That explains how they handle the prime factorization of $pm1$ and the reduction to positive primes. With that in mind you should be able to fix the proof of the lemma.



                          As above, often when there is puzzling exposition in textbooks it can be clarified by reading a bit further to help infer what was intended. But - of course - that is no excuse for sloppy exposition.






                          share|cite|improve this answer











                          $endgroup$













                          • $begingroup$
                            Prima facie, by examining the Q&A/comments here, and even before your answer, I knew that the book could be depended on one thing - that any reader would be forced to put in their own finishing touches to make the material 'crystallize '. . (+1) for providing a (partial) critical review of the book.
                            $endgroup$
                            – CopyPasteIt
                            1 hour ago










                          • $begingroup$
                            @CopyPasteIt It is a popular and widely-respected textbook.
                            $endgroup$
                            – Bill Dubuque
                            59 mins ago










                          • $begingroup$
                            Sure hope that knowing that prime numbers can be negative is used in later chapters. And that we all nod our heads and say 'what a modern and elegant approach'.
                            $endgroup$
                            – CopyPasteIt
                            51 mins ago














                          3












                          3








                          3





                          $begingroup$


                          I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.




                          No apology is necessary since your question is by no means silly. It is not at all surprising that you are puzzled by the cited exposition since it is incredibly sloppy. Kudos to you for reading it very carefully and noticing these problems.




                          Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.




                          Let's examine closely that initial section on primes and prime factorizations.



                          On page $1$ begins a section titled "Unique Factorization in $Bbb Z$" where they briefly review divisibility of "natural numbers $1,2,3ldots"$ This leads to the following "definition" of a prime:




                          Numbers that cannot be factored further are called primes. To be more precise, we say that a number $p$ is a prime if its only divisors are $1$ and $p.$




                          This is imprecise. Is $1$ a prime by this definition? In the next paragraph we find




                          The first prime numbers are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,ldots$




                          So $1$ is not prime. That agrees with modern conventions.



                          On the next page they segue into factorization in the ring of integers $Bbb Z$ where they write




                          If $p$ is a positive prime, $-p$ will also be a prime. We shall not consider $1$ or $-1$ as primes even though they fit the definition.




                          This poses a few problems. They now claim that $1$ does fit the prior definition of a prime, but they didn't list it above (or explain why it was excluded). Further it implies that $ p = -2$ is a prime but it doesn't fit the above definition (it has divisors $,pm1, pm 2,,$ not only $1$ and $p$). They don't give any definition of a prime integer (vs. natural).



                          Readers familiar with basic ring theory and factorization in integral domains will likely have no problem inferring what is intended (the notion of an irreducible or indecomposable element), but any careful reader lacking such background will likely be quite puzzled by these inconsistencies and gaps.



                          As such, it comes as no surprise that the following proof employing these fuzzy notions may well prove troublesome for readers unfamiliar with the intended notions.




                          Lemma $1.$ Every nonzero integer can be written as a product of primes.



                          PROOF $ $ Assume that there is an integer 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$ and $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.




                          The proof has many problems. It doesn't properly handle the (implied) prime factorization of $pm1$ and they forgot to handle the possibility that the counterexample is negative (w.l.o.g. reducing to a positive counterexample).



                          Considering all of the above problems, it is no wonder that you found this proof confusing.




                          The proof can be given in a more positive way by using mathematical
                          induction. It is enough to prove the result for all positive integers. $2$ is a
                          prime. Suppose that $2 < N$ and that we have proved the result for all
                          numbers $m$ such that $2 < m < N.$ We wish to show that $N$ is a product of
                          primes. If $N$ is a prime, there is nothing to do. If $N$ is not a prime, then
                          $N = mn,$ where $2 < m,, n < N.$ By induction both $m$ and $n$ are products of
                          primes and thus so is $N.$




                          Here they've reformulated the induction from negative form - an (infinite) descent on counterexamples (or a "minimal criminal") - into a positive ascent, i.e. into a complete (or strong) induction, and they give some hint about the reduction to the positive case, but still there is no handling of $pm1$. What is actually intended can be inferred from the next theorem they present.




                          Theorem $1.$ For every nonzero integer $n$ there is a prime factorization



                          $$ n, = (-1)^{e(n)} prod_p p^{a(p)}$$



                          with the exponents uniquely determined by $n$. Here $e(n) = 0$ or $1$ depending on whether $n$ is positive or negative and where the product is over all positive primes. The exponents $a(p)$ are nonnegative integers and, of course, $a(p) = 0$ for all but finitely many primes.




                          That explains how they handle the prime factorization of $pm1$ and the reduction to positive primes. With that in mind you should be able to fix the proof of the lemma.



                          As above, often when there is puzzling exposition in textbooks it can be clarified by reading a bit further to help infer what was intended. But - of course - that is no excuse for sloppy exposition.






                          share|cite|improve this answer











                          $endgroup$




                          I'm new to number theory. This might be kind of a silly question, so I'm sorry if it is.




                          No apology is necessary since your question is by no means silly. It is not at all surprising that you are puzzled by the cited exposition since it is incredibly sloppy. Kudos to you for reading it very carefully and noticing these problems.




                          Edit: I'd like to add that this textbook states that if $p$ is a prime number, then so is $-p$. That's where my confusion stems from. The textbook is A Modern Introduction to Classical Number Theory by Ireland and Rosen.




                          Let's examine closely that initial section on primes and prime factorizations.



                          On page $1$ begins a section titled "Unique Factorization in $Bbb Z$" where they briefly review divisibility of "natural numbers $1,2,3ldots"$ This leads to the following "definition" of a prime:




                          Numbers that cannot be factored further are called primes. To be more precise, we say that a number $p$ is a prime if its only divisors are $1$ and $p.$




                          This is imprecise. Is $1$ a prime by this definition? In the next paragraph we find




                          The first prime numbers are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,ldots$




                          So $1$ is not prime. That agrees with modern conventions.



                          On the next page they segue into factorization in the ring of integers $Bbb Z$ where they write




                          If $p$ is a positive prime, $-p$ will also be a prime. We shall not consider $1$ or $-1$ as primes even though they fit the definition.




                          This poses a few problems. They now claim that $1$ does fit the prior definition of a prime, but they didn't list it above (or explain why it was excluded). Further it implies that $ p = -2$ is a prime but it doesn't fit the above definition (it has divisors $,pm1, pm 2,,$ not only $1$ and $p$). They don't give any definition of a prime integer (vs. natural).



                          Readers familiar with basic ring theory and factorization in integral domains will likely have no problem inferring what is intended (the notion of an irreducible or indecomposable element), but any careful reader lacking such background will likely be quite puzzled by these inconsistencies and gaps.



                          As such, it comes as no surprise that the following proof employing these fuzzy notions may well prove troublesome for readers unfamiliar with the intended notions.




                          Lemma $1.$ Every nonzero integer can be written as a product of primes.



                          PROOF $ $ Assume that there is an integer 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$ and $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.




                          The proof has many problems. It doesn't properly handle the (implied) prime factorization of $pm1$ and they forgot to handle the possibility that the counterexample is negative (w.l.o.g. reducing to a positive counterexample).



                          Considering all of the above problems, it is no wonder that you found this proof confusing.




                          The proof can be given in a more positive way by using mathematical
                          induction. It is enough to prove the result for all positive integers. $2$ is a
                          prime. Suppose that $2 < N$ and that we have proved the result for all
                          numbers $m$ such that $2 < m < N.$ We wish to show that $N$ is a product of
                          primes. If $N$ is a prime, there is nothing to do. If $N$ is not a prime, then
                          $N = mn,$ where $2 < m,, n < N.$ By induction both $m$ and $n$ are products of
                          primes and thus so is $N.$




                          Here they've reformulated the induction from negative form - an (infinite) descent on counterexamples (or a "minimal criminal") - into a positive ascent, i.e. into a complete (or strong) induction, and they give some hint about the reduction to the positive case, but still there is no handling of $pm1$. What is actually intended can be inferred from the next theorem they present.




                          Theorem $1.$ For every nonzero integer $n$ there is a prime factorization



                          $$ n, = (-1)^{e(n)} prod_p p^{a(p)}$$



                          with the exponents uniquely determined by $n$. Here $e(n) = 0$ or $1$ depending on whether $n$ is positive or negative and where the product is over all positive primes. The exponents $a(p)$ are nonnegative integers and, of course, $a(p) = 0$ for all but finitely many primes.




                          That explains how they handle the prime factorization of $pm1$ and the reduction to positive primes. With that in mind you should be able to fix the proof of the lemma.



                          As above, often when there is puzzling exposition in textbooks it can be clarified by reading a bit further to help infer what was intended. But - of course - that is no excuse for sloppy exposition.







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited 32 mins ago

























                          answered 3 hours ago









                          Bill DubuqueBill Dubuque

                          213k29195654




                          213k29195654












                          • $begingroup$
                            Prima facie, by examining the Q&A/comments here, and even before your answer, I knew that the book could be depended on one thing - that any reader would be forced to put in their own finishing touches to make the material 'crystallize '. . (+1) for providing a (partial) critical review of the book.
                            $endgroup$
                            – CopyPasteIt
                            1 hour ago










                          • $begingroup$
                            @CopyPasteIt It is a popular and widely-respected textbook.
                            $endgroup$
                            – Bill Dubuque
                            59 mins ago










                          • $begingroup$
                            Sure hope that knowing that prime numbers can be negative is used in later chapters. And that we all nod our heads and say 'what a modern and elegant approach'.
                            $endgroup$
                            – CopyPasteIt
                            51 mins ago


















                          • $begingroup$
                            Prima facie, by examining the Q&A/comments here, and even before your answer, I knew that the book could be depended on one thing - that any reader would be forced to put in their own finishing touches to make the material 'crystallize '. . (+1) for providing a (partial) critical review of the book.
                            $endgroup$
                            – CopyPasteIt
                            1 hour ago










                          • $begingroup$
                            @CopyPasteIt It is a popular and widely-respected textbook.
                            $endgroup$
                            – Bill Dubuque
                            59 mins ago










                          • $begingroup$
                            Sure hope that knowing that prime numbers can be negative is used in later chapters. And that we all nod our heads and say 'what a modern and elegant approach'.
                            $endgroup$
                            – CopyPasteIt
                            51 mins ago
















                          $begingroup$
                          Prima facie, by examining the Q&A/comments here, and even before your answer, I knew that the book could be depended on one thing - that any reader would be forced to put in their own finishing touches to make the material 'crystallize '. . (+1) for providing a (partial) critical review of the book.
                          $endgroup$
                          – CopyPasteIt
                          1 hour ago




                          $begingroup$
                          Prima facie, by examining the Q&A/comments here, and even before your answer, I knew that the book could be depended on one thing - that any reader would be forced to put in their own finishing touches to make the material 'crystallize '. . (+1) for providing a (partial) critical review of the book.
                          $endgroup$
                          – CopyPasteIt
                          1 hour ago












                          $begingroup$
                          @CopyPasteIt It is a popular and widely-respected textbook.
                          $endgroup$
                          – Bill Dubuque
                          59 mins ago




                          $begingroup$
                          @CopyPasteIt It is a popular and widely-respected textbook.
                          $endgroup$
                          – Bill Dubuque
                          59 mins ago












                          $begingroup$
                          Sure hope that knowing that prime numbers can be negative is used in later chapters. And that we all nod our heads and say 'what a modern and elegant approach'.
                          $endgroup$
                          – CopyPasteIt
                          51 mins ago




                          $begingroup$
                          Sure hope that knowing that prime numbers can be negative is used in later chapters. And that we all nod our heads and say 'what a modern and elegant approach'.
                          $endgroup$
                          – CopyPasteIt
                          51 mins ago











                          2












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






                          share|cite|improve this answer









                          $endgroup$


















                            2












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






                            share|cite|improve this answer









                            $endgroup$
















                              2












                              2








                              2





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






                              share|cite|improve this answer









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







                              share|cite|improve this answer












                              share|cite|improve this answer



                              share|cite|improve this answer










                              answered yesterday









                              Roddy MacPheeRoddy MacPhee

                              573118




                              573118























                                  1












                                  $begingroup$

                                  There is a property of the natural numbers called well-order. A set is well-ordered if every non-empty subset has a least element. So given any property $P$:




                                  1. The set of numbers for which $P(n)$ is false is either empty or has a least element.


                                  2. Suppose there is some number $n_0$ such that $P(n_0)$ is false. If $n_0$ is the least such number, then obviously $P(n_0-1)$ is true [1] (otherwise $n_0-1$ would be a number for which $P$ is false that is smaller than $n_0$, and so $n_0$ wouldn't be the smallest such number).


                                  3. Thus, if we can prove that there is no number $n_0$ such that $P(n_0-1)$ is true and $P(n_0)$ is false (i.e. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$", then we have shown that the set of numbers for which $P$ is false has no least element.


                                  4. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$" is equivalent to "$forall n_0: (neg P(n_0-1) lor P(n_0))$", which is in turn equivalent to "$forall n_0: (P(n_0-1) rightarrow P(n_0))$".


                                  5. Thus, if we can prove $forall n_0: (P(n_0-1) rightarrow P(n_0))$, then it follows that the set of numbers for which $P(n)$ is false does not have a least element. Since all non-empty sets of natural numbers have a least element, this set must be empty. That is, there are no numbers for which $P(n)$ is false, i.e. $P(n)$ is true for all $n$.



                                  [1] There is also the possibility that $n_0-1$ isn't a natural number, which happens when $n_0=0$. Dealing with this possibility requires proving that $P(0)$ is true separately, which is why induction proofs require a base case.



                                  So that's the concept behind induction proofs: if the proposition isn't true for all numbers, then there is a non-empty set of numbers for which it is false, which has to have a least element, which means that we have to go from "true" to "false" at some point. Inductive proofs thus look a bit like circular reasoning: you start assuming that the proposition is true, and use that to prove that the proposition is true. But what makes it non-fallacious is that you prove that the proposition is true for a later number by assuming that it's true for an earlier number.



                                  The proof that you cite is using the same basic principle as induction, namely the well-order of the natural numbers, but it is skipping the one-by-one sort of process that induction proofs usually use. Instead of saying "If $P(n_0)$ is false, then $P(n_0-1)$ being true leads to a contradiction", it's saying "If $P(n_0)$ is false, then $P(n)$ being true for $n<n_0$ leads to a contradiction". Like a standard induction proof, it superficially looks like circular reasoning, but isn't, because it's proving that the proposition is true for $N$ using the fact that it's true for smaller numbers.






                                  share|cite|improve this answer









                                  $endgroup$


















                                    1












                                    $begingroup$

                                    There is a property of the natural numbers called well-order. A set is well-ordered if every non-empty subset has a least element. So given any property $P$:




                                    1. The set of numbers for which $P(n)$ is false is either empty or has a least element.


                                    2. Suppose there is some number $n_0$ such that $P(n_0)$ is false. If $n_0$ is the least such number, then obviously $P(n_0-1)$ is true [1] (otherwise $n_0-1$ would be a number for which $P$ is false that is smaller than $n_0$, and so $n_0$ wouldn't be the smallest such number).


                                    3. Thus, if we can prove that there is no number $n_0$ such that $P(n_0-1)$ is true and $P(n_0)$ is false (i.e. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$", then we have shown that the set of numbers for which $P$ is false has no least element.


                                    4. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$" is equivalent to "$forall n_0: (neg P(n_0-1) lor P(n_0))$", which is in turn equivalent to "$forall n_0: (P(n_0-1) rightarrow P(n_0))$".


                                    5. Thus, if we can prove $forall n_0: (P(n_0-1) rightarrow P(n_0))$, then it follows that the set of numbers for which $P(n)$ is false does not have a least element. Since all non-empty sets of natural numbers have a least element, this set must be empty. That is, there are no numbers for which $P(n)$ is false, i.e. $P(n)$ is true for all $n$.



                                    [1] There is also the possibility that $n_0-1$ isn't a natural number, which happens when $n_0=0$. Dealing with this possibility requires proving that $P(0)$ is true separately, which is why induction proofs require a base case.



                                    So that's the concept behind induction proofs: if the proposition isn't true for all numbers, then there is a non-empty set of numbers for which it is false, which has to have a least element, which means that we have to go from "true" to "false" at some point. Inductive proofs thus look a bit like circular reasoning: you start assuming that the proposition is true, and use that to prove that the proposition is true. But what makes it non-fallacious is that you prove that the proposition is true for a later number by assuming that it's true for an earlier number.



                                    The proof that you cite is using the same basic principle as induction, namely the well-order of the natural numbers, but it is skipping the one-by-one sort of process that induction proofs usually use. Instead of saying "If $P(n_0)$ is false, then $P(n_0-1)$ being true leads to a contradiction", it's saying "If $P(n_0)$ is false, then $P(n)$ being true for $n<n_0$ leads to a contradiction". Like a standard induction proof, it superficially looks like circular reasoning, but isn't, because it's proving that the proposition is true for $N$ using the fact that it's true for smaller numbers.






                                    share|cite|improve this answer









                                    $endgroup$
















                                      1












                                      1








                                      1





                                      $begingroup$

                                      There is a property of the natural numbers called well-order. A set is well-ordered if every non-empty subset has a least element. So given any property $P$:




                                      1. The set of numbers for which $P(n)$ is false is either empty or has a least element.


                                      2. Suppose there is some number $n_0$ such that $P(n_0)$ is false. If $n_0$ is the least such number, then obviously $P(n_0-1)$ is true [1] (otherwise $n_0-1$ would be a number for which $P$ is false that is smaller than $n_0$, and so $n_0$ wouldn't be the smallest such number).


                                      3. Thus, if we can prove that there is no number $n_0$ such that $P(n_0-1)$ is true and $P(n_0)$ is false (i.e. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$", then we have shown that the set of numbers for which $P$ is false has no least element.


                                      4. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$" is equivalent to "$forall n_0: (neg P(n_0-1) lor P(n_0))$", which is in turn equivalent to "$forall n_0: (P(n_0-1) rightarrow P(n_0))$".


                                      5. Thus, if we can prove $forall n_0: (P(n_0-1) rightarrow P(n_0))$, then it follows that the set of numbers for which $P(n)$ is false does not have a least element. Since all non-empty sets of natural numbers have a least element, this set must be empty. That is, there are no numbers for which $P(n)$ is false, i.e. $P(n)$ is true for all $n$.



                                      [1] There is also the possibility that $n_0-1$ isn't a natural number, which happens when $n_0=0$. Dealing with this possibility requires proving that $P(0)$ is true separately, which is why induction proofs require a base case.



                                      So that's the concept behind induction proofs: if the proposition isn't true for all numbers, then there is a non-empty set of numbers for which it is false, which has to have a least element, which means that we have to go from "true" to "false" at some point. Inductive proofs thus look a bit like circular reasoning: you start assuming that the proposition is true, and use that to prove that the proposition is true. But what makes it non-fallacious is that you prove that the proposition is true for a later number by assuming that it's true for an earlier number.



                                      The proof that you cite is using the same basic principle as induction, namely the well-order of the natural numbers, but it is skipping the one-by-one sort of process that induction proofs usually use. Instead of saying "If $P(n_0)$ is false, then $P(n_0-1)$ being true leads to a contradiction", it's saying "If $P(n_0)$ is false, then $P(n)$ being true for $n<n_0$ leads to a contradiction". Like a standard induction proof, it superficially looks like circular reasoning, but isn't, because it's proving that the proposition is true for $N$ using the fact that it's true for smaller numbers.






                                      share|cite|improve this answer









                                      $endgroup$



                                      There is a property of the natural numbers called well-order. A set is well-ordered if every non-empty subset has a least element. So given any property $P$:




                                      1. The set of numbers for which $P(n)$ is false is either empty or has a least element.


                                      2. Suppose there is some number $n_0$ such that $P(n_0)$ is false. If $n_0$ is the least such number, then obviously $P(n_0-1)$ is true [1] (otherwise $n_0-1$ would be a number for which $P$ is false that is smaller than $n_0$, and so $n_0$ wouldn't be the smallest such number).


                                      3. Thus, if we can prove that there is no number $n_0$ such that $P(n_0-1)$ is true and $P(n_0)$ is false (i.e. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$", then we have shown that the set of numbers for which $P$ is false has no least element.


                                      4. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$" is equivalent to "$forall n_0: (neg P(n_0-1) lor P(n_0))$", which is in turn equivalent to "$forall n_0: (P(n_0-1) rightarrow P(n_0))$".


                                      5. Thus, if we can prove $forall n_0: (P(n_0-1) rightarrow P(n_0))$, then it follows that the set of numbers for which $P(n)$ is false does not have a least element. Since all non-empty sets of natural numbers have a least element, this set must be empty. That is, there are no numbers for which $P(n)$ is false, i.e. $P(n)$ is true for all $n$.



                                      [1] There is also the possibility that $n_0-1$ isn't a natural number, which happens when $n_0=0$. Dealing with this possibility requires proving that $P(0)$ is true separately, which is why induction proofs require a base case.



                                      So that's the concept behind induction proofs: if the proposition isn't true for all numbers, then there is a non-empty set of numbers for which it is false, which has to have a least element, which means that we have to go from "true" to "false" at some point. Inductive proofs thus look a bit like circular reasoning: you start assuming that the proposition is true, and use that to prove that the proposition is true. But what makes it non-fallacious is that you prove that the proposition is true for a later number by assuming that it's true for an earlier number.



                                      The proof that you cite is using the same basic principle as induction, namely the well-order of the natural numbers, but it is skipping the one-by-one sort of process that induction proofs usually use. Instead of saying "If $P(n_0)$ is false, then $P(n_0-1)$ being true leads to a contradiction", it's saying "If $P(n_0)$ is false, then $P(n)$ being true for $n<n_0$ leads to a contradiction". Like a standard induction proof, it superficially looks like circular reasoning, but isn't, because it's proving that the proposition is true for $N$ using the fact that it's true for smaller numbers.







                                      share|cite|improve this answer












                                      share|cite|improve this answer



                                      share|cite|improve this answer










                                      answered 9 hours ago









                                      AcccumulationAcccumulation

                                      7,1552619




                                      7,1552619






















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

                                          How to make a Squid Proxy server?

                                          Is this a new Fibonacci Identity?

                                          19世紀