Understanding the proof of “Every integer greater than $1$ has a prime divisor”

elementary-number-theoryproof-explanationproof-writing

The proof is by contradiction, starting by stating that some integer $n\gt 1$, "has no prime divisor. By the well-ordering property, we may assume that
$n$ is the least such integer. Now $n|n$; since $n$ has no prime divisor, $n$ is not prime. So $n$ is composite and consequently there exist $a,b \in \mathbb{Z}$ such that $n=ab$, $1<a<n$, and $1<b<n$. Since $1<a<n$, we have that $a$ has a prime divisor, say $p$, so that $p|a$. But $a|n$ so we have that $p|n$ by Proposition 1.1 (which states if $a|b$ and $b|c$, then $a|c$) from which $n$ has a prime divisor, a contradiction. So every integer greater
than $1$ has a prime divisor." (End proof)

I am having trouble understanding the last line "$n$ has no prime divisor, $n$ is not prime. So $n$ is composite". I understand it's the purpose of the proof, but how does $n$ not having a prime divisor mean it must be composite?

Using this example: "If $B$ is prime, its divisors/factors are $1$ and $B$. Since $B$ is prime, it has a prime divisor $B$". So then, am I supposed to assume I don't know about prime factorization for the purpose of this proof and this is why $n$ must be composite?

Best Answer

In the original proof you provided, the assumption is that n has no prime divisor. Based on this assumption, the proof demonstrates that n cannot be a prime number because a prime number, by definition, must have at least two distinct positive divisors (1 and itself), and since n has no prime divisor, it cannot satisfy this condition. Therefore, the conclusion is that n must be composite.

Two distinct divisors that are talked about and seems you are confused with are : 

 - 1 (Not a prime divisor)
 - n itself (It is also not a prime divisor due to our assumption that number n doesn't have any prime divisor)

I understand it's the purpose of the proof, but how does n not having a prime divisor mean it must be composite?

If n has no prime divisor, it means there is no prime number that can divide n exactly. If n were a prime number, by definition, it would have exactly two distinct positive divisors: 1 and n itself. But since n has no prime divisor, it cannot have these two distinct divisors, contradicting the definition of a prime number. Therefore, if n has no prime divisor, it cannot be a prime number, and the only alternative is that n must be composite.

So then, am I supposed to assume I don't know about prime factorization for the purpose of this proof

So, if you are working on the proof without assuming prior knowledge of prime factorization, the proof still holds, as it relies on the basic definitions and properties of prime and composite numbers.

In summary, the last line of the proof is stating that if an integer n has no prime divisor, it cannot be a prime number and must be composite and why it is to be composite is stated above.

If it isn't clear still, feel free to ask!

Related Question