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