Is the smallest non-1 divisor of a number always prime? I am working on some things related to arithmetic derivatives, and I was writing a program to calculate the arithmetic derivative. In working on my program I came across an assumption that I have made, but I could not prove that it was true and it was quite frustrating to me. 
My hypothesis is for any $n \in \mathbb{N}$, the smallest number, $a \in \mathbb{N}/\{1\}$ such that $a \vert n$ should be prime. My beginning of a proof for this was this
Using the fundamental theorem of arithmetic, for all $n \in \mathbb{N}/\{1\}$, that either $n$ is prime, or that $n$ has a unique prime factorization. If $n$ is prime, the proof is trivial, as the prime factorization for all $p \in \mathbb{P}$ is just $p$; however, for the case of $n$ being composite, the proof became quite difficult for me. 
For the case of a number $c$ such that $c \in \mathbb{N}/\{1\}$ and $c \notin \mathbb{P}$, we can say that there exists at least two numbers, $a$ and $b$ such that fulfill the following four statement


*

*$1 < a \le b < c$

*$a \vert c$

*$b \vert c$

*$ab = c$


My thought process thereby went into dividing $c$ into odds and evens. We can say that this theorem is true for all even numbers, $e$, rather trivially as well because for all $e \in \{2k:\mathbb{N}/\{1\}\}$ that $2\vert e$ and $2$ is also the smallest integer that could possibly fulfill the above criteria thereby making $a = 2$ and fulfilling the theorem for all even numbers.
The part that I cannot figure out however is odd numbers. My intuition is telling me this must be true, but I cannot figure out a proof of this theorem for odds and I was wondering if 


*

*Is this theorem actually true?

*If so, how can this be proven for odds?

 A: Let $n\in\Bbb N$ and let $a\in\Bbb N\setminus\{1\}$ be the smallest divisor of $n$. If $a$ is prime, you're done. If not, then $a$ is composite, and so can be written $a = bc$ for $b,c\in\Bbb N\setminus\{1\}$. But then $b,c < a$, and $b\mid n$, contradicting the assumption that $a$ was the smallest divisor.
A: One can also avoid a proof by contradiction. By the fundamental theorem of arithmetic, every divisor $d > 1$ of $n$ is a product of some primes dividing $n$.
Let $p$ the smallest prime divisor of $n$. By the above, all divisors $d > 1$ of $n$ are greater than or equal to $p$, as every such $d$ is a product of factors all greater than or equal to $p$.
A: If you just want to prove that the smallest non 1 divisor of a number is always prime, all you have to do is proceed by contradiction. 
Let N be a composite number ( even or odd doesn't matter ). Let's assume that N's smallest non 1 divisor is not a prime, let's call this composite divisor c. 
If c is composite then using the fundamental theorem of arithmetic, c can be expressed as the factorisation of prime numbers all < to c. Let p be one of c's factors. 
Then since c | N and p | c then p | N , but p < c ( since p is a factor of c ), which contradicts the assumption that the smallest divisor of N is c. 
I don't know if this is what you wanted and if I have been clear enough.
A: No contradiction: just use the definition of prime number.
Consider the set $D=\{a\in\mathbb{N}:a\mid n, a>1\}$. The set is non empty, because $n\in D$ (assuming $n>1$, of course).
Let $p=\min D$. If $x\mid p$, then $x\mid n$ and $x\le p$. If also $x>1$, then $x\in D$. By minimality of $p$, we conclude $x=p$. Therefore $p$ is prime.
