Originally Posted by

**PaulRS** **1)** $\displaystyle n$ has to be greater than 1 !

If $\displaystyle n$ is prime we are done, so let's assume that $\displaystyle n$ is not prime. Then $\displaystyle n=a_1\cdot{b_1}$ for some $\displaystyle a_1,b_1\geq{2}$. If $\displaystyle a_1$ is prime, we are done. If this is not so, then $\displaystyle a_1=a_2\cdot b_2$ for some $\displaystyle a_2,b_2\geq{2}$ that is $\displaystyle n=a_2\cdot b_2 \cdot b_1 \geq{2^3}$

Now repeat this process. We can ensure it will end since after $\displaystyle m$ steps we get $\displaystyle n=a_m\cdot b_m\cdot b_{m-1}\cdot ..\cdot b_1\geq{2^{m+1}}$ and this doesn't hold for large enough $\displaystyle m$.

This proves that at some point $\displaystyle a_{m}$ is going to be prime. (since this ends if and only if $\displaystyle a_m$ is prime) .And we are done.

**2)**. Simple note that $\displaystyle 6k+2$ is even, ( so if k>0 then it is a number greater than 2 and divisible by it, hence not prime). $\displaystyle 6k+3=3(2k+1)$ is multiple of 3, so it only can be prime if it is 3 itself. $\displaystyle 6k+4=2(3k+2)$ (again even) ...