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,

\begin{align} r = \prod_{i}^{n} p_i , \quad \quad p_i \in \mathcal{P} \quad \text{and} \quad p_i < r < p \quad \forall i \end{align}

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.

  • $\begingroup$ 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]$. $\endgroup$ – Junaid Aftab Oct 2 '17 at 11:26
  • $\begingroup$ Here, $f(x)$ plays the role of $P$ and $g(x)$ plays the role of $r$. $\endgroup$ – Junaid Aftab Oct 2 '17 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.