Why are all non-prime numbers divisible by a prime number? In Euclid's infinite prime numbers proof, the logic is as follows:

Assume a set $S$ of all prime numbers in existence is finite (there are a finite amount of primes)

Then there must be a greatest prime $p$

$$n = (2 \cdot 3 \cdot 5\cdots p) + 1$$

$n &gt; p$, and under the proof's assumption, $n$ cannot be prime.*

This is where the logic confuses me. Why is it that given that the if a number is not prime, then it is automatically divisible by a prime. I can't think of an example to contradict, but that's not proof that there exists no number that is not prime and non divisible by primes.
One can prove this for all integers greater than $1$ by induction: we know that $2$ is a prime. Now for ou inductive step assume that for all $i&lt;n$, $i$ is either prime or divisible by a prime. Case 1: $n$ is prime; we're done. Case 2: $n$ is composite, so $ab = n$ for $a, b &lt; n$. So each of those is divisible by a prime. We're done.

Essentially the same argument shows that all integers greater than $1$ can be written as a product of primes.
Let $n$ be a composite (i.e., non-prime) integer.

According to the Fundamental Theorem of Arithmetic, $n$ has a unique prime factorization:

$$ n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{k}^{\alpha_{k}}$$

where the $p_{i}$ are distinct prime numbers and the $\alpha_{i}$ are positive integers. 

Choose any of the $p_{i}$, say $p_{j}$. 

Now, $p_{j} | p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{k}^{\alpha_{k}}$, and so, 

$$p_{j}|n.$$ 

Therefore, $n$ is divisible by a prime number. (Actually $k$ of them in this case.)