I can intuitively understand that there are infinitely many irreducible polynomials in $\Bbb{F}_p[X]$, where $p$ is a prime number, but I'm having a hard time actually proving it. What proof strategy should I take for this?
$\begingroup$
$\endgroup$
13
asked Apr 6, 2015 at 5:23
-
2$\begingroup$ Remember Euclid. $\endgroup$– KarankoApr 6, 2015 at 5:25
-
$\begingroup$ I was thinking about his proof of infinitely many primes... $\endgroup$– Patrick ShambayatiApr 6, 2015 at 5:26
-
$\begingroup$ ... and what happened? $\endgroup$– KarankoApr 6, 2015 at 5:27
-
$\begingroup$ Suppose all primes are on this list: $p_1,...,p_r$. Then $p_1p_2\cdots p_r+1$ is also prime thus there are infinitely many $\endgroup$– Patrick ShambayatiApr 6, 2015 at 5:27
-
1$\begingroup$ (continued: ) Every element $\pi_i\in \{\pi_1,\cdots,\pi_r\}$ has remainder 1 after division with $\pi_1\pi_2\cdots\pi_r+1$. Thus, $\pi_1\pi_2\cdots\pi_r+1$ is also irreducible. Therefore, there are infinitely many irreducible elements in $\Bbb{F}_p[X]$. $\endgroup$– Patrick ShambayatiApr 6, 2015 at 6:54
|
Show 8 more comments
2 Answers
$\begingroup$
$\endgroup$
2
Assume that there are finitely many (monic) irreducible polynomials in $\mathbf F_{p}[X]$,$p_{1}(x), p_{2}(x), \dots, p_{n}(x)$. Consider $f(x)=p_{1}(x)p_{2}(x) \cdots p_{n}(x)+1$. Now $f(x)$ is not divisible by any irreducible, and hence is irreducible and is not in the list of irreducibles. Contradiction.
-
$\begingroup$ @AndréNicolas Why? It's known that any reducible polynomial is divisibile by an irreducible polynomial; since $f$ isn't, it must be irreducible. After all, this is a proof by contradiction, isn't it? I would make it into a direct proof, and in this case your remark would apply. $\endgroup$– egregApr 6, 2015 at 14:04
-
$\begingroup$
$\endgroup$
Mimic Euclid: $\, f_{n+1}\! = 1+f_1\cdots f_n\,$ is an infinite sequence of coprimes $\,f_i.\,$ Choosing $\,g_i\,$ to be an irreducible factor of $\,f_i\,$ yields an infinite sequence of coprime (so nonassociate) irreducibles.
Alternatively, recall that the sequence of polynomials $\rm\:f_n = (x^n\!-\!1)/(x\!-\!1)\:$ is a strong divisibility sequence, i.e. $\rm\:(f_m,f_n) = f_{(m,n)}$ in $\rm\mathbb Z[x].\:$ Hence the subsequence with prime indices yields an infinite sequence of pairwise coprime polynomials. Further the linked proof shows the gcd has linear (Bezout) form $\rm\:(f_m,f_n) = f_{(m,n)}\! = g\, f_m + h\, f_n,\,$ $\rm\, g,h\in\mathbb Z[x],\:$ so said coprimality persists in every ring $\,R[x].\,$ Thus, for each prime $\rm\:q,\:$ choosing a factor of $\rm\:f_q\:$ irreducible in $R[x]$ yields infinitely many irreducible polynomials, pariwise nonassociate (being pairwise coprime).
answered Apr 6, 2015 at 13:44