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.
Best Answer
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.