# Euclid's proof of the infinitude of primes to prove this question

I'm trying to prove that if $k$ is a field, then there are an infinite number of irreducible monic polynomials in $k[X]$.

My attempt of solution is use almost the same strategy of the Euclid's proof of the infinitude of primes supposing $F_1,\ldots,F_n$ are all irreducible monic polynomials in $k[X]$ and construct a new irreducible monic polynomial different the $F_i$.

My guess is $F=F_1\cdots F_n +1$ which clearly is monic, but I'm having problems to proof the irreducibility part.

Should I keep trying to solve this question using this strategy or it's better to use a new one?

Thanks

-
You can make this strategy work. The key is knowing that in $k[X]$ being a prime and being irreducible are equivalent properties. –  hardmath Jul 19 '14 at 1:48
You don't need it to be irreducible, you just need to show that it isn't divisible by any of the $F_i$. (Euclid's original proof also doesn't prove the new number isn't irreducible...) –  Thomas Andrews Jul 19 '14 at 2:03
@MichaelHardy: Your comment surprised me. I understand that $S$ is then extended to a larger finite set of primes. If it is error to call it a proof by contradiction it is a common error. Would you mind elaborating briefly? –  daniel Jul 19 '14 at 2:42
@daniel: If in doing a proof by contradiction you assume $A$ and prove not $A$, then you should be very suspicious about whether you really needed to do proof by contradiction. In Euclid's case, you are proving a set $S$ of primes has the following property: If $T \subset S$ is finite, then $S \setminus T$ is nonempty. Of course, any set with this property is infinite. –  RghtHndSd Jul 19 '14 at 3:18
@daniel : Indeed, lots of well-known mathematicians have been guilty of this error, including no less than Dirichlet and G. H. Hardy (in a 1908 edition of one of his books, changed in a later edition) and some of today's best-known number theorists. See this paper: Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52. –  Michael Hardy Jul 19 '14 at 3:21

Hint $\ f_{n+1}\! = 1+f_1\cdots f_n\,$ constructs an infinite sequence of coprimes $\,f_i.\,$ Choosing $\,g_i\,$ to be a monic irreducible factor of $\,f_i\,$ yields an infinite sequence of coprime (so distinct) irreducibles.

-
interesting approach, thanks. –  user42912 Jul 19 '14 at 12:17

Good strategy. You cannot expect to prove that $F$ is irreducible. However, it is a product of (monic) irreducibles. You will be able to show easily that any irreducible monic divisor $P$ of $F$, where $P$ has degree $\ge 1$, must be different from all the $F_i$.

For infinite fields, this is vast overkill, since there are infinitely many irreducibles of degree $1$.

-

Your strategy is doomed to fail. Just like in Euclid's proof, you can't possibly prove that $1+\prod p_{i}$ is prime. Same here, you can't possibly prove that what you get is irreducible, because it might as well isn't. For example, $1+x(x+1)$ is not irreducible in $\mathbb{C}$. Try to prove that, if $1+\prod F_{i}$ can be factored, then there exist an irreducible monic polynomial that divide it.

Now, I got an analytic/combinatoric (kinda) proof, just for a change of flavor.

If the $k$ is infinite, then $X-\alpha$ for each $\alpha$ provide the infinite prime you need.

Assume $k$ is finite. Assume there are only a finite number of monic irreducible polynomial: let $r$ be the number of them. Then since all monic polynomial can be factored into monic irreducible polynomial uniquely, the number of possible monic polynomial with degree no more than $n$ is bounded above by $\begin{pmatrix}r+n\\n\end{pmatrix}$ (formula for choosing $n$ out of $r+1$ choice with repetition: this is because in best case all monic polynomial have degree $1$ an their sum cannot exceed $n$; $r+1$ is because we have to account for those that do not use up all the $n$ allowed monic irreducible polynomial by allowing us to choose $1$ as a possible choice). We have $\lim\limits_{n\rightarrow\infty}\frac{\begin{pmatrix}r+n+1\\n+1\end{pmatrix}}{\begin{pmatrix}r+n\\n\end{pmatrix}}=\lim\limits_{n\rightarrow\infty}\frac{r+n+1}{n+1}=1$.

Number of monic polynomial up to degree $n$ however is $|k|^{n}$. We have $\lim\limits_{n\rightarrow\infty}\frac{|k|^{n+1}}{|k|^{n}}=|k|>1$. Hence asymptotically, $|k|^{n}>\begin{pmatrix}r+n\\n\end{pmatrix}$, producing the contradiction.

-

When I saw this question, two things popped into my head that may make it easier to understand what is going on:

1. When $k$ is a finite field, you can find an irreducible (=prime) polynomial of any degree; that obviously proves infinitude. Not that proving this very statement is actually productive, because:

2. When $k$ is algebraically closed, the only irreducible polynomials are of degree 1.

It would be conceivable to execute a proof that distinguished between finite fields (proving statement 1) from infinite fields (in which you just have to observe that any $X - a$, for $a \in k$, is irreducible). But this is clumsy, and so we are faced with the problem of finding an argument that is oblivious to the size of the field.

Euclid's argument will deal with polynomials of arbitrarily high degree; your polynomial $F$ will always have degree at least $n$. And yet, if $k$ is algebraically closed, fact 2 shows that it is not irreducible. Nonetheless, by factoring it you can produce a root that was not a root of any of the $F_i$'s with $i \leq n$, and this fact has nothing to do with the nature of $k$; it's just Euclid's original argument adapted to polynomials.

In this way you can more easily remember that the "product plus one" appearing in Euclid's proof is unlikely to itself be prime, but simply include a novel prime factor.

-