The result is given implicitly in ∑d|m d Nd = qm and explicitly in Nm = (1/m) ∑d|m μ(m/d) qd.
(Here μ(n) is the Möbius function, defined by μ(n) = (–1)e when n is the product of e different primes (and in particular μ(1) = 1), and μ(n) = 0 otherwise (i.e., when n is divisible by the square of a prime).)
For example, if q=2 then N1 = 2 (the irreducible
polynomials are x and x+1), N2 = 1 (the only
irreducible polynomial is x2+x+1), N3 = 2
(the irreducible polynomials are x3+x+1 and
x3+x2+1), N4 = 3,
N5 = 6, ...
The first formula says 4N4+2N2+N1 = 16,
and the second formula says N4 = (1/4)(16–4) = 3.
Since the largest power of q is larger than the sum of all other terms, Nd > 0.
That both formulas are equivalent is an example of Möbius inversion.
The above formulas for Nd follow immediately from the theory of finite fields. For example, in GF(qm) any element is root of its minimal polynomial. Such a minimal polynomial of degree d is irreducible over GF(q) and has d distinct roots in GF(qm). That gives the first formula. Or, to say the same thing differently: the polynomial Xqm-X factors over GF(q) in the product of all irreducible (in GF(q)) polynomials of degree dividing m.
Without use of GF(qm) one can derive these formulas
using generating functions.
There are qm monic polynomials of degree m.
Consequently, the generating function of monic polynomials
according to degree equals
f(X) = ∑m qm Xm
= 1/(1–qX).
On the other hand, each polynomial factors uniquely
into irreducible factors, and we find for this same generating function
f(X) = ∏(1 + Xd + X2d +
...)Nd.
(There is a factor (1 + Xd + X2d + ...)
for each irreducible polynomial of degree d.)
Hence f(X) = ∏d
(1/(1–Xd))Nd.
Compare and take logarithms, using that
log(1/(1–a)) = ∑i
ai/i.
We get ∑i (qX)i/i =
∑d,i Nd
Xdi/i.
Compare the coefficients of Xm on both sides. We get
the first formula.