Number of Irreducible Polynomials - Maple Help

Home : Support : Online Help : Mathematics : Algebra : Polynomials : Number of Irreducible Polynomials

NumberTheory

 NumberOfIrreduciblePolynomials
 number of monic irreducible polynomials

 Calling Sequence NumberOfIrreduciblePolynomials(n, p) NumberOfIrreduciblePolynomials(n, p, m)

Parameters

 n - non-negative integer p - power of prime number m - (optional) positive integer; defaults to $1$

Description

 • The NumberOfIrreduciblePolynomials(n, p, m) command computes the number of monic irreducible univariate polynomials of degree n over a finite field of order ${p}^{m}$.
 • An explicit formula for this function is $\frac{1}{n}\sum _{d|n}\mathrm{\mu }\left(d\right){\left({p}^{m}\right)}^{\frac{n}{d}}$ where the sum is over the divisors of n and $\mathrm{\mu }$ is the Moebius function.

Examples

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{NumberOfIrreduciblePolynomials}\left(3,5\right)$
 ${40}$ (1)
 > $\mathrm{NumberOfIrreduciblePolynomials}\left(1,{2}^{4}\right)$
 ${16}$ (2)

The number of linear, quadratic, cubic, and quartics over $\mathrm{GF}\left(p\right)$.

 > $\mathrm{seq}\left(\mathrm{NumberOfIrreduciblePolynomials}\left(n,p\right),n=1..4\right)$
 ${p}{,}\frac{{1}}{{2}}{}{{p}}^{{2}}{-}\frac{{1}}{{2}}{}{p}{,}\frac{{1}}{{3}}{}{{p}}^{{3}}{-}\frac{{1}}{{3}}{}{p}{,}\frac{{1}}{{4}}{}{{p}}^{{4}}{-}\frac{{1}}{{4}}{}{{p}}^{{2}}$ (3)

The number of cubics over $\mathrm{GF}\left({p}^{m}\right)$.

 > $\mathrm{NumberOfIrreduciblePolynomials}\left(3,p,m\right)$
 $\frac{{\left({{p}}^{{m}}\right)}^{{3}}}{{3}}{-}\frac{{{p}}^{{m}}}{{3}}$ (4)

Compatibility

 • The NumberTheory[NumberOfIrreduciblePolynomials] command was introduced in Maple 2016.