Another problem about irreducible polynomials over a (finite) field

I want to know whether it is true that over a finite field $K$ (with characteristic $p$, say), and for any positive integer $m$, does there always exist a prime (or equivalently, irreducible, since the polynomial ring over a field is UFD) polynomial in $K[x]$ with degree $m$. I prefer some elementary proof.

• For an elementary proof, I'd first try to prove it for $K=\mathbb Z_p$. But I doubt you can find a simple elementary proof for the second result, if by elementary, you mean like Euclid's proof for the infinitude of primes. The second result states the existence of a prime in a certain range, while the first states just about the existence of a prime outside a finite set. In the natural numbers, then the second is more like Bertrand's Postulate, which is very tricky to prove. Oct 23 '13 at 16:32
• Thank you very much! I had thought it may be very difficult to prove, but I known the proof of your formula now, and it is not very complicated. For example, click this link: math.stackexchange.com/questions/152880/… Oct 24 '13 at 4:55
• It's definitely not as hard as Bertrand's postulate. The formula is still considered "elementary number theory" because it doesn't use any higher algebra or analysis. Oct 24 '13 at 13:05
• Aha, the proof there is a little surprising for me. Oct 24 '13 at 13:34
• I didn't say it wasn't surprising, just that it is considered "elementary number theory" by the way mathematicians use the term "elementary number theory." Oct 24 '13 at 13:39

Yes, you can. There is a formula for the number of monic primes of degree $m$ over a finite field of order $q$:

$$\nu_q(m)=\frac{1}{m}\sum_{d\mid m} \mu\left(\frac md\right)q^d$$

Where $\nu_q(m)$ counts the number of prime monic polymomials of degree $m$ over a field of size $q$.

You can easily show this gives $\nu_q(m)\geq \frac{1}{m}\left(q^m - \sum_{i=0}^{m-1} q^i\right)> 0$.

• Thank you! But I want to know whether the second question can be solved more "elementary", since the first question can also be solved in the same way as Euclid's proof that prime numbers are infinite in number. And I want to know what is the reference of your formula for the number of primes of degree m over a finite field of order q. Oct 23 '13 at 3:24
• If you knew how to resolve the first question, why did you write "I want to know,..." and never indicate that you knew how to show it? Ask the question you want answered. Oct 23 '13 at 3:25
• Oh, I'm sorry, I only think of this way just now. Oct 23 '13 at 3:28
• Just a tiny quibble--your colon placement seems to suggest that $v_q(m)$ is the number of degree $m$ primes, where it is, in fact, just the number of monic ones. Oct 23 '13 at 8:12
• Ah, I fixed that in the description after, but not before. Oct 23 '13 at 13:04