# Proof Verification: Infinitely many Primes Using Euclid's Algorithm

I'm trying to prove the infinitude or primes using division algorithm. Does the following proof work:

Assume that there are only finitely many primes in $\mathbb{Z}$. By letting $\mathcal{P}$ denote the set of primes,

\begin{align} p & = \min \mathcal{P} \\ P & = \max \mathcal{P}. \end{align}

By the Division algorithm, we have that there exists unique $q$ and $r$ such that,

\begin{align} P = pq + r, \quad 0 \leq r < p. \end{align}

If $r = 0$, we would have that $p \; | \; P,$ a contradction. So, we have that $0 < r < p$. If $r$ is prime, we get a contradiction. If $r$ is composite, then by the Fundamental Theorem of Arithmetic, $r$ has a prime decomposition,

But this, once again, contradicts the minimality of $p$ as a prime number.

I know the proof isn't as elementary as Euclid's original proof. The proof relies on both the Division Algorithm and the Fundamental Theorem of Arithmetic. But is it all right?

Ultimately, I wish to prove that $F[x]$ has infinitely many primes, where $F$ is a finite field, using the same reasoning.

Hint: Consider this case: what happens if $r=1$? for example, $3=2+1$ $2,3$ are primes and $1\neq 0$. $1$ is not a product of primes.

• Can the proof be tweaked to accommodate this single degenerate case? If $r > 1$, the proof works, I guess. Also, I suppose this argument won't be a problem for the case of $F[x]$. Because if $f(x) = g(x)h(x)$, where, say, $g(x)$ is a polynomial of degree 0, then $g(x) \in F^{\times}$, contradicting the irreducibility of $f(x)$ in the UFD, $F[x]$. – Junaid Aftab Oct 2 '17 at 11:26
• Here, $f(x)$ plays the role of $P$ and $g(x)$ plays the role of $r$. – Junaid Aftab Oct 2 '17 at 11:27