# Prove that every integer is either prime or composite

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.

• I think both proofs are essentially the same. They just show different levels of detail. However, the first proof can be made into a proof of the existential part of the fundamental theorem of arithmetic by small modification. Jul 12, 2013 at 9:24
• i agree with @Tunococ, the proof given in book implicitly involved the definition of divisibility while in your proof , you just used the term "divisible".
– Aang
Jul 12, 2013 at 9:28
• Thanks, @Tunococ and @Avatar! I was just worried that using "divisible" was jumping the gun, perhaps. You never know with Mathematics! :) Jul 12, 2013 at 9:31
• remark: not all integers are either prime or composite. $1$ and $-1$ are neither. And what about $0$? Jul 12, 2013 at 9:34
• True. Should have specified $>1$. Thanks. Jul 12, 2013 at 9:35

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.

• Thanks for the helpful commentary, especially the reference to the principle of tertium non datur! Since the book is just starting out with proofs, it hasn't touched upon prime factorization yet. I guess there will be more rigorous proofs coming later. Jul 13, 2013 at 11:56

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

• The symbolic apparatus behind this answer seems to assume a level of mathematical proficiency beyond the understanding of someone who needed to ask the question in the original post in the first place. For example, what is the neutral moltiplication element ... is moltiplication a typo, or is that actually a meaningful, but highly advanced, concept -- so rarely expressed that it doesn't even show up on Google? Aug 28, 2020 at 16:41

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