Prove that the smallest factor of an integer is prime.

Question

The question is as follows: Prove that the smallest factor m > 1 of any given integer n > 1 is prime.

Here's what I'm thinking, you can divide any number by one of the following numbers: 2, 3, 5, 7. I can't think of a non-prime number that cannot be divided by at least one of these numbers without remainder.

I feel that this is enough proof in my head but I don't know how to express this proof formally. Where do I begin?

Answer 1

An assigment like this is usually best approached by taking a factor of $n$ and show that if it is not prime, then it is not the smallest factor of $n$. By showing this, you will show that any factor that is the smallest factor must be prime.

Therefore, take any factor $k$ of $n$, this means $k|n$. If $k$ is not prime, then $k=ab$ for some $1<a,b<k$. Because $a|n$ (why?) and $a<k$, this means that there exists a factor of $n$ which is smaller than $k$, so $k$ is not the smallest factor of $n$.

Answer 2

Assume $m$ is divisible by $k$, and $k$ is the smallest factor(other than 1).

Also assume $k$ is not prime, it must be divisible by some number $n$, such that $n\lt k$

But if $n$ divides $k$, it must also divide $m$. This contradicts our original statement that $k$ is the smallest factor. Thus $k$ must be prime.

Answer 3

If $m$ is not prime then $d|m$ for some $d$ with $1<d<m$. From $d|m$ combined with $m|n$ it follows that $d|n$ contradicting that $m$ is the smallest factor of $n$ with $m>1$. It is obvious that $d$ is a smaller one. The contradiction justifies the conclusion that $m$ is prime.