Prove that every integer is either prime or composite

Question

In the book I'm reading, the following proof is given for the stated theorem:

Let n be any integer that is greater than 1. Consider all pairs of positive integers $r$ and $s$ such that $n = rs$. There exist at least two such pairs, namely $r = n$ and $s = 1$ and $r = 1$ and s = n. Moreover, since $n = rs$, all such pairs satisfy the inequalities $1 ≤ r ≤ n$ and $1 ≤ s ≤ n$. If $n$ is prime, then the two displayed pairs are the only ways to write $n$ as $rs$. Otherwise, there exists a pair of positive integers $r$ and $s$ such that $n = rs$ and neither $r$ nor $s$ equals either 1 or $n$. Therefore, in this case $1 < r < n$ and $1 < s < n$, and hence $n$ is composite.

When I attempted the proof myself, I came up with the following reasoning: Consider all integers $1<k<n$. Now, either $n$ is divisible by one of them or not. If not, $n$ is prime; if it is, $n$ is composite. Therefore, every integer is either prime or composite.

I was wondering if my proof is incorrect or less rigorous in some sense. Isn't the textbook complicating things unnecessarily? Or is that a better demonstration of mathematical thinking? Some thoughts are appreciated.

P.S.: I was also not sure whether this question belonged to proof-writing or proof-strategy.

Answer 1

What do you mean exactly by "composite"? Disregarding $0$ and $\pm1$ for the sake of simplicity, if you define composite as divisible by something else then $1$ and itself (i.e. "non-prime") the proof you need is just an obvious appealing to the principle of tertium non datur.

If, on the other hand, you define composite a number which can be written as a product of at least two primes you actually need some argument to show that primes and composites exhaust all numbers.

Certainly, your suggestion that if $n$ is not prime then there's a number $1<k<n$ that divides $n$ is correct, but it is not the end of it since $n=k\cdot(n/k)$ needs not to be a decomposition into prime factors. I'd say that you need a little inductive argument to come to a conclusion.

Answer 2

The reason of the complication is that if you have a generic commutative ring, you want to define a prime element and you can't use (directly) the fact that $\forall_{t \in 2..n-1}$ that $t \nmid n$.

You have to construct a structure that "measure" an element ($N$ a special norm) that:

• $N(a) \geq 0 , \forall_a$
• If $a \mid b$ , $N(a) | N(b)$
• If $N(a) = 1 $, $a$ is a unit
• $N(1) = 1$ where $1$ is the neutral moltiplication element.

In that particular (and more general) environment, you can define the meaning of a prime element using this norm such as :

Let $C$ a commutative ring and $N$ his special norm. $a \in C $ (with $N(a) > 1$) is prime if $\forall_{b,c \in C}$ with $N(a) \mid N(b)N(c) $ , then $N(a) | N(b)$ or $N(a)| N(c)$ .

The reason of this choose is that in more abstract space, there can be some element that are not prime and you can't decompose in that space! Like $3$ in $\mathbb{Z}[\sqrt{-5}]$. It's not prime but is irreducible.

But in the case of $\mathbb{Z}$, we have that $N(a) = \lvert a \rvert$. If we are considering only the positive value, $N(a) = a$. $\mathbb{Z}_+$ (alias $\mathbb{N}$) is a unique factorization domain.

Let $C = \mathbb{Z}_+$ with $N(a) = a$. $a \in C $ (with $a > 1$) is prime if $\forall_{b,c \in C}$ with $a \mid bc $ ($a < bc$) , then $a | b$ or $a | c$ .

So $b = ak + r_1$ and $c = aj + r_2$ with $0\leq r_1,r_2 < a$. $bc = (ak + r_1)(aj + r_2)$ and, because we work on a ring, $bc = aakj + akr_1 + ajr_2 + r_1r_2 = a(akj + kr_1 + jr_2) + r_1r_2 = aq + r_1r_2$.

So $a \mid bc$ if $r_1 = 0$ or $r_2 = 0$.

If we fix $bc$ and see if there's an $a$ that $a \mid bc$, we have found all the factorization of $bc$. With that, we can easily say (in $\mathbb{Z}_+$) if is prime or not.

Your proof is impecable and is really usefull in the normal daily activity.

Then you start to abstract your space, it "falls" because is really specific.

Your book probably took the general definition and "smoothed" in an easier way.

PS: Maybe there's some errors somewhere. I don't have all the books here at work :)

Answer 3

I think the proof is right, an integer number is either $1$, a prime or a product of some primes, so it is either prime or composite, or $1$.