Irreducible polynomial

An irreducible polynomial is a nonconstant polynomial that cannot be written as a product of two nonconstant polynomials over its coefficient field. Over a general integral domain, neither factor may be a unit.

If $f$ is an irreducible polynomial over a field $F$, then a nonzero residue $[g]$ modulo $(f)$ has $\gcd (f,g)=1$. The Euclidean algorithm supplies $uf+vg=1$, giving inverse $[v]$ for $[g]$. Thus the quotient ring $F[X]/(f)$ is a field. If $\mathrm{deg}f=d$ and $F$ has $q$ elements, polynomial division supplies exactly $q^d$ residue classes.