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

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.


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 Classical Introduction to Modern 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,3\ldots"$ 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 \leq 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 \leq 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.