Help With Euclid's Proof that there are Infinite Primes I need some help understanding a given proof so that I can in turn prove something.
In a question I am given that:

In order to prove that there is no "largest" prime number, for any prime $p$ just show there is a new prime $q$ such that $q>p$. Write $$N=(2\cdot3\cdot5\cdot...\cdot p)+1,$$ and if $N$ is prime we are done, otherwise $N$ is divisible by some prime $q$.

I am told to prove $q>p$. I think I can figure out how to do this, but there is one thing I don't understand in the above box. I understand how the proof is done when $N$ is prime, but I don't understand why "$N$ is divisible by some prime $q$" otherwise.
May somebody please help me understand why this is true. Thanks in advance!
 A: Assume the primes are finite. So $N=(2^{k_1}⋅3^{k_2}⋅...⋅p^{k_n})+1$. But since there are finitely many, $N$ should also be written as a product of our finite number of primes (since it is NOT in its present form). Now, what happens then you try to do this? I.E., can you divide N by 2? how about 3? How about $p$?....
Hint:
$$N=2(2^{k_1-1}3^{k_2}5^{k_3}...p^{k_n})+1 \text{ so } 2\text{ does not divide }N$$
$$N=3(2^{k_1}3^{k_2-1}5^{k_3}...p^{k_n})+1 \text{ so } 3\text{ does not divide }N$$
$$...$$
$$N=p(2^{k_1}3^{k_2}5^{k_3}...p^{k_n-1})+1 \text{ so } p\text{ does not divide }N$$
Turns out you can not divide $N$ by any of our primes given, but $N$ $must$ be written as a product of primes, then there must exist a prime $q$ that divides $N$, and I think it's easy to see that this prime is greater than $p$
A: $\textit{Every}$ integer is divisible by some prime, so if $N$ is not itself prime, then $N$ is divisible by some prime $q<N$.
You know that $q$ is greater than $p$ because $N$ is one more than a multiple of any prime less than or equal to $p$ (you can probably make this a little more formal, but that's the basic idea).
