I have the following theorem:
If no prime less than or equal to $\sqrt{n}$ divides $n$, then $n$ is a prime.
And the following proof (proof by contradiction) for said theorem:
Suppose that no prime less than or equal to $\sqrt{n}$ divides $n$ but $n = ab$, with neither $a$ nor $b$ equal to $1$.
Now $a$ and $b$ cannot both be strictly larger than $\sqrt{n}$ or their product would be larger than $n$.
So one of $a$ or $b$ is not larger than $\sqrt{n}$: assume (without loss of generality) that $a \le \sqrt{n}$.
Now $a$ cannot be prime (as we have assumed $n$ has no prime factor this small), and so is composite.
Therefore $a$ has a prime factor $p$, which must be less than $a$.
But then $p < a \le \sqrt{n}$ is a prime factor of $n$, and this contradicts our hypothesis.
Hence $n$ is prime.
We deduce that $a$ is composite. But why does this then mean that $a$ has a prime factor $p$? So this is saying that all composite numbers have a prime factor? Why?
I would greatly appreciate it if people could please take the time to clarify this.
PostScript: I am assuming that this is the definition of composite number being used here.
We have assumed $a>1$ (See the first line) and we have show it cannot be prime (otherwise $n$ has a prime factor $\leq\sqrt n$).
Typically, the definition of composite is that the number can be written as the product of more than one prime (that is, is greater than $1$ and isn’t prime). This follows from the Fundamental Theorem of Arithmetic.