# Induction in the proof of the existence of prime factorizations

The fundamental theorem of arithmetic states that every positive integer greater than 1 is either a prime or a product of primes.

First question: why "either a prime or a product of primes", if every prime is in fact a product of primes with one factor? Wouldn't it be simpler to just say that every positive integer greater than 1 can be written as a product of primes?

The fundamental theorem of arithmetic is proved using strong induction. The formal definition of strong induction (in its transfinite version) is: $$\forall n [\forall k [k. In this case, $$P(x)$$ is substituted by "if x>1, then x is prime or x is a product of primes".

Second question: which are the formal definitions of x is prime and of x is a product of primes? Velleman says that x is not prime is the same of $$\exists a\exists b[n=ab \land a. Therefore, I would assume that x is prime would be $$\forall a\forall b[n=ab \rightarrow a \geq n \lor b \geq n]$$. Is it correct? How about x is a product of primes?

Now, expanding the inductive hypothesis inside the scope of the natural numbers and excluding the vacuosly true statements, we end up with the following result:

$$P(2) \land [P(2) \rightarrow P(3)] \land[P(2)\land P(3) \rightarrow P(4)] \land ... \rightarrow \forall n P(n)$$

Third question: how is it possible that if 2 is prime or a product of primes implies that 3 is prime or a product of primes?

• Language, especially when interpreted naturally, can be ambiguous. I can imagine someone thinking that a "product of primes" must necessarily require strictly more than one prime in the product. One might argue that $1$ is also a product of primes if we were to go with a more pedantic interpretation, $1$ being represented by the empty product, which people who are more used to natural language might have forgotten the existence of. By wording it in a way that even if interpreted as natural language cannot be misinterpreted, you will have more people understand it. Feb 11, 2020 at 18:35
• "if every prime is in fact a product of primes with one factor?" Why sacrifice clarity for efficiency? "Wouldn't it be simpler to just say" Simpler for whom? Certainly not for the student or anyone reading the text. It'd be simplest for me not to say anything at all as I know what I mean, so what do I care if anyone else does. Feb 11, 2020 at 18:45
• ... I could just as legitimately ask that as you had to clarify "if every prime is in fact a product of primes with one factor" wouldn't it have been "simpler" for you to just accept the terminology than to actually form your question. Simplicity involves 1) saying something and 2) being understood. Paucity of words is not the end-all and be all. Feb 11, 2020 at 18:50
• You've written that $P(x)$ is “if $x>1$, then $x$ is a prime or a product of primes.” I think you mean that $P(x)$ is “$x$ is a prime or a product of primes.” The theorem is then, “For all integers $x$, $x > 1 \rightarrow P(x)$.” Feb 11, 2020 at 18:50
• "how is it possible that if 2 is prime or a product of primes implies that 3 is prime or a product of primes?" Three is either prime or a product of integers less than it. The integers less than it are all product of primes or prime so the product of integers less than it is a product of primes. Feb 11, 2020 at 18:54

There is nothing wrong with the phrasing, even allowing "product of primes" to be understood to include the case of a product with one factor (which most mathematicians allow). Phrasing need not be the shortest possible, nor does the "or" need to be exclusive: the most important thing is that it not be misunderstood. You could just as well phrase the existence part of the Fundamental Theorem of Arithmetic as:

Every positive integer is a (possibly empty) product of primes.

Why do we not phrase it that way? In part, for historical reasons. Euclid excluded $$1$$ (it wasn't a "number"); Gauss phrases the theorem as follows (Disquisitiones Arithmeticae, Section II.16, from the English edition translated by Arthur A. Clarke):

Theorem. A composite number can be resolved into prime factors in only one way.

thus putting primes themselves on a separate category. Traditionally, people said numbers were either "primes or products of primes", before allowing $$1$$ to be considered a "number." The idea of having products with one or fewer factors is relative new.

I will note that your phrasing is incomplete: an oft-ignored part of the FTA is the uniqueness of the decomposition (up to order and, in modern parlance, associates). In fact, that's the part that Gauss is concerned with, saying

"It is clear from elementary considerations that any composite number can be resolved into prime factors, but it is often wrongly taken for granted that this cannot be done in several different ways."

Gauss was the first to prove it explicitly (Euclid only proves it for square-free composite integers).

There are other ways to phrase it; you can specify that the uniqueness is only "up to order of the factors" if you want to make sure people don't think that $$21$$ can be factored two ways (as $$3\times 7$$ and as $$7\times 3$$). You can specify "up to associates" if you suddenly discover that negative numbers exist and that if $$p$$ is a (positive) prime number, then so is $$-p$$ (under the divisibility definition). Etc.

The formal definition of "$$x$$ is a prime" is

Definition. A (positive) integer $$p$$ is prime if and only if it is not $$0$$, not $$1$$ (or $$-1$$), and whenever $$p$$ divides a product $$ab$$, it divides one of the factors.

This is not the classical definition. Euclid defines a prime as a number (hence greater than $$1$$) which is divisible only by $$1$$ and itself; in modern parlance, this would be an irreducible, not a prime (though in the integers, the two concepts coincide).

"A product of primes" would be harder; you would want to have an operator that takes an arbitrary but finite number of integers and assigns an integer to it (their product). Or you could say that $$m$$ is a product of primes if

there exists a positive integer $$n$$ [greater than $$1$$ if you want to exclude the one-factor product] and positive integers $$p_1,\ldots,p_n$$ such that $$p_i$$ is prime for each $$i$$ and $$m=p_1p_2\cdots p_n$$.

In fact, the inductive step is usually proven as follows:

Assuming that for any $$k$$, $$1\lt k\lt n$$, $$k$$ is either prime or a product of primes, consider $$n$$. If $$n$$ is prime, we are done. If $$n$$ is not prime, then there exist $$a,b$$, $$1\lt a,b\lt n$$ such that $$n=ab$$ (*). Applying the inductive argument to $$a$$ and $$b$$.... etc.

Now, (*) is not the definition of prime, but it is an equivalent property to "prime" in the integers.

Theorem. let $$m$$ be a positive integer, $$m>1$$. The following are equivalent:

1. If $$m=ab$$ with $$a,b$$ positive integers, then $$a=1$$ or $$b=1$$.
2. If $$m=ab$$ with $$a,b$$ positive integers, then $$a=m$$ or $$b=m$$.
3. If $$m|ab$$ with $$a,b$$ integers, then $$m|a$$ or $$m|b$$.
4. If $$1\leq k\lt m$$, $$k$$ an integer, then $$\gcd(k,m)=1$$.
5. For any integer $$a$$, $$\gcd(a,m)=1$$ or $$\gcd(a,m)=m$$.

And so the argument uses 1 or 2 to guarantee the existence of $$a$$ and $$b$$.

The implication "$$2$$ is a prime or a product of primes $$\Rightarrow$$ $$3$$ is a prime or a product of primes" holds because the consequent is true. For that matter, the implication "$$6$$ is a prime $$\Rightarrow$$ $$7$$ is a prime" is also true... because the consequent is true.

$$(1)\$$ Yes, it's natural to allow $$\rm\color{#90f}{singleton\ (and\ empty)}$$ products since it simplifies proofs like this, i.e. a prime is a (singleton) product of primes (and an empty product $$= 1$$).

$$(2)\$$ In this elementary context a "prime" denotes an "irreducible" natural, i.e. an $$\,n> 1\,$$ with only trivial factorizations: $$\, n = ab\,\Rightarrow\, a = 1\,$$ or $$\,b = 1$$.

$$(3)$$ The strong inductive proof that every natural $$\,n>1\,$$ has a prime factorization essentially has all primes as base case(s). Let's examine the proof: if $$\,n\,$$ is prime then it factors as itself (base case). Else $$\,n = ab\,$$ for $$\,1 < a,b < n\,$$ so by strong induction the smaller $$\,a,b\,$$ have prime factorizations, which $$\rm\color{#0a0}{appended}$$ yield a prime factorization of $$\,n = ab.$$

This may be deduced from a more general result that's both simpler to prove and more clearly highlights the algebraic structure underlying the induction (including its base cases). Namely, the result follows immediately by the below frequently applicable multiplicative form of induction, which shows that for $$\rm\color{#0a0}{multiplicative}$$ sets we need only check the $$\rm\color{#c00}{generators}$$ (here $$\color{#c00}1$$ and $$\rm\color{#c00}{primes}$$). This gives a clearer answer to your 3rd question concerning the "basis" of the strong induction.

Lemma $$\,\Bbb N$$ is the only set of naturals containing $$\color{#c00}1$$ & $$\rm\color{#c00}{all\ primes}$$ & $$\rm\color{#0a0}{closed\ under\ multiplication}$$

Proof $$\$$ Suppose $$\rm\!\ S\subset \mathbb N\:$$ has said properties.  We prove by strong induction every natural $$\rm\!\ n\in S,\,$$ so $$\rm\,S = \Bbb N.\,$$ If $$\rm\:n\:$$ is $$\,\color{#c00}1\,$$ or $$\color{#c00}{\rm prime}$$ then by hypothesis $$\rm\:n\in S.\:$$ Else $$\rm\,n\,$$ is composite,  hence $$\rm\ n = j k\$$ for $$\rm\: 1 < j,k < n.\:$$ By strong induction the smaller $$\rm\ j,k\in S,\:$$ $$\rm\color{#0a0}{therefore}$$ $$\rm\: n = jk\in S.\$$ QED

Corollary $$\$$ Every natural $$> 0\,$$ is a product of primes (i.e. irreducibles).

Proof $$\:\!$$ The set $$\,\rm S\,$$ of naturals that are products of primes is $$\rm\color{#0a0}{closed\ under\ multiplication}$$, so by the Lemma, $$\rm\,S = \Bbb N\!\iff\! S\,$$ contains $$\color{#c00}1$$ and $$\rm\color{#c00}{all\ primes}$$ - true, being $$\rm\color{#90f}{empty\ \&\ singleton}$$ products.

Remark  This is a prototypical example of the method of structural induction, a type of induction that shows a result holds true for all elements of an inductively (recursively) generated structure by "piggybacking" on its inductive generation. Above the structure is the multiplicative monoid of naturals, which is (freely) generated by its irreducible (prime) elements.

• I will try to reconstruct your explanation using only sentential logic. Let $P(x)= x>1 \rightarrow$ x is prime or x is a product of primes. By strong induction, $\forall n [\forall k [k < n \rightarrow P(k)] \rightarrow P(n) ] \rightarrow \forall n P(n)$. If 'n is prime' is false, then 'n is a product of primes' = $\exists a \exists b [n=ab \land a<n \land b<n]$ must be true. Thus, we have $\forall n [\forall k [k < n \rightarrow P(k)] \rightarrow \exists a \exists b [n=ab \land a<n \land b<n] ] \rightarrow \forall n P(n)$. Now, I can't deduce how the consequent in the inductive step is true. Feb 11, 2020 at 23:39
• @TylerD007 What is your goal? To understand the essence of this inductive proof or to gain practice with the formal syntax of mathematical logic? If it is the former then that's the wrong way to go: it's like trying to understand a computer program written in a high-level language by looking only at its compilation into low-level assembly language. Feb 11, 2020 at 23:44
• My goal is to understand how the inductive hypothesis $\forall k [k<n \rightarrow P(k)]$ leads to the consequent in this specific case. If we instantiate a and b in the inductive hypothesis, we'd have $a<n \rightarrow P(a) \land b<n \rightarrow P(b)$. Now, even if we'd consider that 'a is a product of primes' $\land$ 'b is a product of primes' $\land n=ab \rightarrow$ 'n is a product of primes', we couldn't infer that from my construction as it is now, which means it is wrong somewhere. Feb 11, 2020 at 23:54
• Another possibility would be to consider 'x is not prime' = $\exists a \exists b [x=ab \land a<x \land b<x]$. Then, by strong induction: $\forall n [\forall k [k<n \rightarrow P(k)] \rightarrow P(n)] \rightarrow \forall nP(n)$. Substituting P(n), $\forall n [\forall k [k<n \rightarrow P(k)] \rightarrow n>1 \rightarrow$ 'n is prime' or 'n is a product of primes'$] \rightarrow \forall nP(n)$. Then, $\forall n [\forall k [k<n \rightarrow P(k)] \land n>1 \land$ n is not prime $\rightarrow$ 'n is a product of primes'$] \rightarrow \forall nP(n)$. (continues) Feb 12, 2020 at 0:13
• Then, $\forall n [\forall k [k<n \rightarrow P(k)] \land n>1 \land \exists a \exists b [n=ab \land a<n \land b<n] \rightarrow$ 'n is a product of primes'$] \rightarrow \forall nP(n)$. Instantiating k, a and b, $\forall n [ (a<n \rightarrow P(a) ) \land (b<n \rightarrow P(b) ) \land n>1 \land n=ab \land a<n \land b<n \rightarrow$ 'n is a product of primes'$] \rightarrow \forall nP(n)$. Making the proper deductions, $\forall n [ P(a) \land P(b) \land n>1 \land n=ab \land a<n \land b<n \rightarrow$ 'n is a product of primes'$] \rightarrow \forall nP(n)$. (continues) Feb 12, 2020 at 0:21

The wording is proper. A prime (say $$7$$) is not a product of primes. Since $$1$$ is not a prime, $$7$$ is not a product of primes--that is, one that requires the operation of multiplication. What product could that possibly be?? (The "empty product" is explicitly not a product.) Taken alone, $$7$$ is not a product, any more than $$28$$ is a "product."

Such a weird attempt then makes every number prime: $$28 = \prod\limits_{i\in I}$$ where $$I = \{ 28 \}$$. What an absurdity and mess!!!

Attempts to define a prime by some novel interpretation of product that has no argument, such as $$7 = \prod\limits_{i\in I}$$ where $$I = \{ 7 \}$$, have no justification. The product function must take an argument, and this ad-hoc approach (which I've never seen in 40 years of working in mathematics) requires a redefinition of what a function is... i.e., something that takes no argument.

From the Dictionary of mathematics:

product: The result of multiplication or any operations on mathematical objects deemed close enough in resemblance to multiplication. (Such as the scalar product and the vector product in vectors.)

The dictionary highlights the key property of "product" which is of course multiplication. The ad-hoc attempts such as $$7 = \prod\limits_{i\in I}$$ where $$I = \{ 7 \}$$, involve no multiplication whatsoever, despite the symbol.

If you want to re-define prime in this way, you're forced to redefine product (and likely other foundational terms) in weird ways and admit that now every integer can be defined as a prime.

Good luck with that!

• $7 = \prod\limits_{i\in I}i$ where $I=\{7\}$. I would argue that the pedantic interpretation of $n$ being equal to a product of primes is that there exists some multiset $I$ consisting exclusively of primes such that $n = \prod\limits_{i\in I} i$. This does not require $|I|>1$ nor even require $|I|>0$. In natural language, perhaps the condition that $|I|>1$ is implied to some people, but not to all. Feb 11, 2020 at 18:52
• You seem to have taken offense to the idea that you can define a "product function" which maps finite multisets of reals (where the multiset is of any size including less than $2$) to a result of their multiplication based on how you have seen multiplication defined using natural language. If you are so convinced that an operation mapping such a multiset of size one or zero to a result should not receive the name "product" in that case, then why do you suppose we have the concept of an empty product? Feb 11, 2020 at 19:08
• You also seem to have misconstrued what I said. I did not suggest that $28$ is prime. Nor did I suggest that $7$ is composite. Composite to me is a number which is a product of more than one prime (possibly repeated). Prime to me is a number $p$ such that $p\mid ab\implies p\mid a$ or $p\mid b$, which agrees with the idea that it is not possible to represent it as a product of at least two integers each of which greater than $1$. Note that I included the "at least two" in that sentence which to me is not included automatically in the definition of what a "product is." Feb 11, 2020 at 19:12
• "Empty product" is explicitly defined to be distinct from "product." But my bigger point is that this attempt at re-definition of "prime" leads to the absurd notion that every integer can be defined by such a "null product" and thus can be considered "prime." Feb 11, 2020 at 19:13
• I think I've rebutted your first definition. I also don't see how your second definition ($p$ is prime if $p \mid a b \Rightarrow p \mid a$ or $p \mid b$) can be made operational. How can you prove there isn't some extraordinarily large product you've never tested for which this definition doesn't hold... unless you invoke the fundamental theorem of arithmetic to begin with? Feb 11, 2020 at 19:31