# primitive polynomial
## English
### Noun

primitive polynomial (plural primitive polynomials)$$
* (algebra, ring theory) A polynomial over an integral domain R such that no noninvertible element of R divides all its coefficients at once; (more specifically) a polynomial over a GCD domain R such that the greatest common divisor of its coefficients equals 1.
** 1992, T. T. Moh, Algebra, World Scientific, page 124:We claim that every primitive polynomial can be written as a product of irreducible elements in $\mathbf {D} [x]$. […] By induction on the degree of the primitive polynomials, we conclude that both $g(x),h(x)$ can be written as product of irreducible elements in $\mathbf {D} [x]$.
** 2000, David M. Arnold, Abelian Groups and Representations of Finite Partially Ordered Sets, Springer, page 114:If $f(x)\in \mathbb {Z} [x]$, the ring of polynomials with coefficients in $\mathbb {Z}$, then the content of $f$, denoted by $c(f)$, is the greatest common divisor of the coefficients of $f$. The polynomial $f(x)$ is called a primitive polynomial if $c(f)=1$. Since $c(fg)=c(f)c(g)$, by Gauss's lemma [Hungerford, 74], the set $S$ of primitive polynomials in $\mathbb {Z} [x]$ is a multiplicatively closed set. Define $\Lambda =\mathbb {Z} [x]_{S}$, the localization of $\mathbb {Z} [x]$ at $S$, a subring of the field of quotients $\mathbb {Q} (x)$ of $\mathbb {Z} [x]$. Elements of $\Lambda$ are of the form $f(x)/g(x)$ with $f(x),g(x)\in \mathbb {Z} [x]$ and $g(x)$ a primitive polynomial.
** 2000, Jun-ichi Igusa, An Introduction to the Theory of Local Zeta Functions, American Mathematical Society, page 1:According to the Gauss lemma, the product of primitive polynomials is primitive. Therefore if $f(x),g(x)$ are primitive and $f(x)=g(x)h(x)$ with $h(x)$ in $F[x]$, then necessarily $h(x)$ is in $A[x]$ and primitive. […] The irreducible elements of $A[x]$ are irreducible elements of $A$ and primitive polynomials which are irreducible in $F[x]$.
* (algebra, field theory) A polynomial over a given finite field whose roots are primitive elements; especially, the minimal polynomial of a primitive element of said finite field.
** 2002, Charles E. Stroud, A Designer's Guide to Built-in Self-Test, Kluwer Academic, page 69:Primitive polynomials make the initialization of LFSRs a simpler task since any nonzero state guarantees that all non-zero states will be visited in the maximum length sequence.
** 2003, Zhe-Xian Wan, Lectures on Finite Fields and Galois Rings, World Scientific, page 145:Definition 7.2 Let $f(x)$ be a monic polynomial of degree $n$ over $\mathbb {F} _{q}$. If $f(x)$ has a primitive element of $\mathbb {F} _{q^{n}}$ as one of its roots, $f(x)$ is called a primitive polynomial of degree $n$ over $\mathbb {F} _{q}$. Theorem 7.7 For any positive integer $n$ there always exist primitive polynomials of degree $n$ over $\mathbb {F} _{q}$. All the $n$ roots of a primitive polynomial of degree $n$ over $\mathbb {F} _{q}$ are primitive elements of $\mathbb {F} _{q^{n}}$. All primitive polynomials of degree $n$ over $\mathbb {F} _{q}$ are irreducible over $\mathbb {F} _{q}$. The number of primitive polynomials of degree $n$ over $\mathbb {F} _{q}$ is equal to $\phi (q^{n}-1)/n$.
** 2008, Stephen D. Cohen, Mateja Preŝern, “The Hansen-Mullen Primitivity Conjecture: Completion of Proof”, in James McKee, Chris Smyth, editors, Number Theory and Polynomials, Cambridge University Press, page 89:This paper completes an efficient proof of the Hansen-Mullen Primitivity Conjecture (HMPC) when n = 5, 6, 7 or 8. The HMPC (1992) asserts that, with some (mostly obvious) exceptions, there exists a primitive polynomial of degree n over any finite field with any coefficient arbitrarily prescribed.

#### Usage notes

* Since fields are rings, the domain of applicability of the ring theory definition includes that of the one specific to Galois fields. It is thus perfectly feasible for a given instance to be a primitive polynomial in both senses of the term: such is the case, for example, for the minimal polynomial (over a given finite field) of a primitive element (i.e., that has said primitive element as root).
* (polynomial over a finite field whose roots are primitive elements):
** More precisely, a primitive polynomial over (with coefficients in) $\mathbb {F} _{q}$ of order $n$ has roots that are primitive elements of $\mathbb {F} _{q^{n}}$.
** Given a primitive element $\alpha \in \mathbb {F} _{q}$, the set of powers $\{1,\alpha ,\dots \alpha ^{n-1}\}$ constitutes a polynomial basis of $\mathbb {F} _{q^{n}}$.
*** In consequence, a primitive polynomial is sometimes defined as a polynomial that generates $\mathbb {F} _{q^{n}}$.

#### Hyponyms

* (polynomial over an integral domain such that no noninvertible element divides all of its coefficients): monic polynomial

#### Related terms

* primitive part (of a polynomial)

#### Translations
### See also

* content (of a polynomial)
* irreducible
* primitivity

### Further reading

* Polynomial basis on Wikipedia.Wikipedia
* Gauss's lemma (polynomial) on Wikipedia.Wikipedia
* Polynomial ring on Wikipedia.Wikipedia
* Primitive polynomial on Encyclopedia of Mathematics
* Galois field structure on Encyclopedia of Mathematics
* Primitive Polynomial on Wolfram MathWorld