Euclid's proof of infinitude of primes. http://en.wikipedia.org/wiki/Euclid's_theorem
I just read Euclid's proof for the existence of infinitely many primes (I have never used his proof earlier to prove this). It seems to me that he assumes it exist a finite number and he constructs the number $x=p_1 \cdot... \cdot p_n + 1$, then he says that $x$ is either prime or not, if it is we are done, if not it must exist a prime that divides it, and so on...(see link). 
However this proof makes no sense, it relies on the fact that if $x$ is not prime then it exist a prime that divides it which is exacly the (weak) fundamental theorem of arithmetics, however this theorem immediately implies that it exist infinite number of primes, because if it didnt then any number $n > p_1 \cdot... \cdot p_n$ cant have a prime factorization.
What am I missing here? To me it seems as Euclid's proof is just stupid.

Theorem: Any $n\in N$ with $n>1$ is divisible by a prime. Proof: Among the divisors of $n$ that are greater than $1$ (noting that $n$ itself is a divisor of $n$), there is a LEAST one,  $M.$  Now $M$ is prime because $1<M, $ and if $M=A B$ with $A>1<B$ then $A$ would be a divisor of $n$ with $1<A<M$, which is absurd by the def'n of $M$.
Theorem (Euclid).If $p_1,...,p_k$ are primes then there is a prime  $p$ not equal to any of $p_1,...,p_k.$ Proof: Let $n=1+\prod_{j=1}^kp_j.$   Now $n$ is $1$ more than a multiple of $p_j$ for $j=1,...,k$ so $n$ is not divisible by any of $p_1,...,p_k .$ But $n>1$ so by the previous theorem, $n$ has a prime divisor $p.$
Remark. For $1\leq j\leq k$ we have $n-1=p_j A_j$ with $A_j\in N.$  If $p_j$ divides $n$ then $n=p_j B_j$ with $B_j\in N.$ But then $1=n-(n-1)=p_j(B_j-A_j), $ implying that $p_j$ divides $1, $ which is absurd.
