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 > 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.