# Euclid's Proof of infinite prime numbers

I think this should probably be obvious, but I having trouble understanding part of the proof: If $N=p_1p_2\cdots p_n+1$, then why is it necessarily true that any given $p$ does not divide $N$?

-
Because it leaves a remainder of $1$. – Brian M. Scott Jan 21 '13 at 23:50
Dividing by any of the given $p_k$ leaves a remainder of $1$. – Henry T. Horton Jan 21 '13 at 23:50
Oh alright I see thanks – user58437 Jan 21 '13 at 23:51
You can also use $\, N = p_1 p_2\cdots p_k +\, p_{k+1}\cdots p_n,\ \$ or, more simply, note that $N(N+1)$ has more prime factors than $N.\ \$ – Math Gems Jan 21 '13 at 23:54
Caveat: Note that this does not generate all prime numbers, only creates a new one. For example, $2 \cdot 3 + 1 = 7$, but the next prime is $5$. – George V. Williams Jan 22 '13 at 1:09

Because the rest of division for all $p_{i}$ is $1$. For example we can suppose that there are only $3$ prime numbers: $(2,3,5)$. So you can define a new number $N$ as $2*3*5+1=31$. So it results that $31=2*15+1=6*5+1=3*10+1$. Then $N$ is a new prime number!

-
Or is divisible by a new prime number, in general. – Charles Jan 22 '13 at 0:17