Feedback-polynomial parity condition for maximal period Created 2026-09-24 Updated 2026-11-05
For a binary linear-feedback shift register of length , a feedback polynomial with maximal period cannot have as a polynomial root. A root at would make the nonzero all-one state fixed, whereas maximal period requires all nonzero states to lie in one cycle of length greater than one.
Writing the monic polynomial as , this gives
Over the field with two elements, an even number of the feedback coefficients must therefore equal one, and has an odd number of nonzero coefficients. This is a necessary condition, not a sufficient test for a primitive polynomial. The restriction matters: for , has maximal nonzero-state period despite having as a polynomial root.
Irreducibility by degree-preserving reduction modulo a prime Created 2026-10-31 Updated 2026-11-05
Let be primitive polynomial and let be a prime number not dividing its leading coefficient. If its coefficientwise reduction is irreducible in , then is irreducible in . Indeed, a rational factorization would give an integer factorization by Gauss's lemma. The leading coefficients of both factors remain nonzero modulo , so reduction preserves their positive degrees, contradicting irreducibility of the reduction. For monic polynomials the leading-coefficient condition is automatic.
For a nonzero integer-coefficient polynomial , its polynomial content is the positive greatest common divisor of all its coefficients; one may set . A primitive polynomial has content one.
For , choose a positive integer clearing its denominators, so . Put . Then
where is an integer-coefficient primitive polynomial. This proves existence with .
For uniqueness, suppose , where both integer-coefficient polynomials are primitive and . Write in lowest terms with positive. Then has integer coefficients. Coprimality forces to divide every coefficient of , hence . Now has content , so . Therefore and .
Define the rational polynomial content by this unique positive multiplier. If and , Gauss lemma for polynomials says that is primitive. Thus
The uniqueness argument also shows that the construction is independent of the chosen denominator-clearing integer .
For a nonzero polynomial , its polynomial content is the positive greatest common divisor of its coefficients:
For nonzero , choose a positive integer with and define its rational polynomial content by
To check independence of the denominator, write with and . Then , while multiplication of all coefficients by a positive integer gives
Dividing by proves , as required.
For multiplication, write . The integer-coefficient content identity permitted in the source gives
Thus
We will also use the normalization , with content one: if , then . It is a primitive polynomial. For a nonzero rational constant , the same definition gives .
The nonzero ideal is principal because is a principal ideal domain. Choose a nonzero generator . Part (a) gives
The nonzero rational scalar is a unit in , so this rescaling does not change the generated principal ideal:
Part (b) now places in , since . Thus .
For the reverse inclusion, let be nonzero. The displayed equality supplies with . Multiplicativity of rational polynomial content gives
Since has integer coefficients, is a positive integer. The normalization from part (a) gives , so multiplying it by the integer proves . Consequently . The zero polynomial belongs as well, proving
This is the divisibility descent in Gauss lemma for polynomials: dividing an integer-coefficient polynomial by a primitive polynomial cannot introduce a denominator into an exact quotient. Here it yields the description of prime ideals of the integer polynomial ring above zero. The generator has positive polynomial degree, since a primitive constant would be a unit and would put in .
For the polynomial ring, use the Euclidean function on nonzero polynomials. If and , subtract the multiple of that cancels the leading term of . The leading coefficient of is invertible in the field, and every subtraction strictly lowers the degree of the remainder. This process terminates with and either or . Thus .
For the Gauss lemma for polynomials, call an integer polynomial primitive when its coefficient gcd is one. If two primitive polynomials had a nonprimitive product, a prime would divide every product coefficient. Reducing modulo would give a zero product of two nonzero polynomials in the integral domain , a contradiction. Therefore the product of primitive integer polynomials is primitive.
To transfer a rational factorization, write each nonzero rational factor as a rational scalar times a primitive integer polynomial by clearing denominators and removing the coefficient gcd. Thus with primitive and . Their product is primitive by the lemma. If in lowest terms, integrality of every coefficient of forces to divide every coefficient of , so . Hence ; absorbing into either factor produces the required integer factorization with the same positive factor degrees. In particular irreducibility of a primitive polynomial over and over is equivalent.
Finally, let in lowest terms, , be a rational root of a monic degree- integer polynomial. Multiplying the equation by shows . Coprimality forces . Thus .
For the polynomial ring, use the Euclidean function on nonzero polynomials. If and , subtract the multiple of that cancels the leading term of . The leading coefficient of is invertible in the field, and every subtraction strictly lowers the degree of the remainder. This process terminates with and either or . Thus .
For the Gauss lemma for polynomials, call an integer polynomial primitive when its coefficient gcd is one. If two primitive polynomials had a nonprimitive product, a prime would divide every product coefficient. Reducing modulo would give a zero product of two nonzero polynomials in the integral domain , a contradiction. Therefore the product of primitive integer polynomials is primitive.
To transfer a rational factorization, write each nonzero rational factor as a rational scalar times a primitive integer polynomial by clearing denominators and removing the coefficient gcd. Thus with primitive and . Their product is primitive by the lemma. If in lowest terms, integrality of every coefficient of forces to divide every coefficient of , so . Hence ; absorbing into either factor produces the required integer factorization with the same positive factor degrees. In particular irreducibility of a primitive polynomial over and over is equivalent.
Finally, let in lowest terms, , be a rational root of a monic degree- integer polynomial. Multiplying the equation by shows . Coprimality forces . Thus .
A polynomial in is a primitive polynomial when the greatest common divisor of its coefficients is one. The Gauss lemma for polynomials states that a product of primitive integer polynomials is primitive, and that a primitive positive-degree integer polynomial is reducible over exactly when it factors into positive-degree integer polynomials. More generally, polynomial content is multiplicative up to sign.
The Eisenstein criterion states that a primitive polynomial is irreducible over if there is a prime such that , for every , and . These criteria permit integer coefficient tests for rational irreducibility; the following parts apply them with their exact divisibility hypotheses.
A nonzero primitive polynomial in has greatest common divisor of its coefficients equal to one. Suppose primitive polynomials had a product whose coefficients were all divisible by some prime . Their reductions in are both nonzero, because neither polynomial has every coefficient divisible by . A polynomial ring over a field is an integral domain, so their product is nonzero modulo , a contradiction. Hence the product of primitive polynomials is primitive.
To deduce unique factorization, write any nonzero integer polynomial as its positive polynomial content times a primitive polynomial, with its sign treated as a unit. The preceding result gives multiplicativity of content. Factor the primitive part over the Euclidean polynomial ring , and rescale every irreducible rational factor to a primitive integer polynomial. If with all polynomials primitive and in lowest terms, the equality has contents and . Thus , forcing . The rational factorization therefore lifts to an integer factorization.
A primitive integer polynomial is irreducible over exactly when it is irreducible over : an integer factorization gives a rational one, and a rational factorization lifts by the same primitive-content argument. Factor the content into integer primes. Existence and uniqueness over the integers and over now give existence and uniqueness of the resulting factorization into constant prime factors and primitive irreducible polynomial factors, up to order and signs. Therefore . This is the full lifting step in Gauss lemma for polynomials.
Write , a monic primitive polynomial. If with , grouping terms gives a factorization in the polynomial ring :
Both factors have positive degree, so is not an irreducible polynomial.
Conversely, if is a prime number, change variables by . The binomial theorem gives
Every coefficient except the leading one is divisible by , because for , whereas the constant coefficient is not divisible by . The Eisenstein criterion makes this polynomial irreducible over . The substitution is an invertible ring homomorphism, so is also irreducible over ; the Gauss lemma for polynomials transfers this to . Hence
Eisenstein's criterion. Let be a nonconstant primitive polynomial. If a prime number satisfies , for , and , then is an irreducible polynomial over .
To prove the Eisenstein criterion, suppose a nontrivial factorization exists over . Gauss lemma for polynomials gives with of positive degree. Their leading coefficients are not divisible by , because their product is . Reduction modulo therefore preserves both degrees, and
Since the only irreducible factor of the right side is , both reduced factors are nonzero monomials of positive degree. Their constant coefficients are consequently divisible by . This would make , a contradiction.
For the requested polynomial, shift the variable by one. The binomial theorem gives
It is monic, all coefficients below the leading one are divisible by , and the constant coefficient is , not divisible by . The Eisenstein criterion proves irreducibility of this shifted polynomial. The substitution is an automorphism of , with inverse , so it preserves nontrivial factorizations. Hence
This is the cyclotomic polynomial for a prime index.
A unique factorization domain is an integral domain in which every nonzero nonunit is a finite product of irreducible elements, uniquely up to reordering and multiplication of factors by a unit in a ring. A principal ideal domain is an integral domain in which every ideal is generated by one element.
Gauss lemma for polynomials says that over a unique factorization domain , the product of two primitive polynomials is primitive, and the polynomial content satisfies up to a unit. In particular a primitive polynomial of positive degree is irreducible over exactly when it is irreducible over the fraction field of . Consequently a polynomial ring over a unique factorization domain is itself a unique factorization domain.
The Eisenstein criterion says that if has and there is a prime element with , for every , and , then is irreducible over the fraction field. If is primitive, it is also irreducible in . Over one may take to be an ordinary prime number. The primitivity qualification prevents a nonunit constant content from being overlooked.
The defining distinction is unique irreducible factorization versus generation of every ideal by one element.
Gauss lemma for polynomials says that the product of two primitive polynomials in is primitive. Equivalently, a primitive polynomial in is reducible over exactly when it is reducible over .
Gauss lemma for polynomials states that the product of two primitive polynomials over a unique factorization domain is primitive. In particular, a primitive polynomial in is reducible over exactly when it is reducible over .
Eisenstein criterion says that a primitive polynomial
is irreducible over if there is a prime such that , for every , and . To prove it, suppose with both factors of positive degree. After removing contents, Gauss's lemma lets us take primitive. Reduction modulo gives
so both reduced factors are monomials of positive degree. Their constant terms are therefore divisible by , making divide , a contradiction.
An algebraic integer is a complex number satisfying a monic polynomial in . Let be one and let be its monic minimal polynomial. The usual proof using polynomial content shows that . The set
is the kernel of the polynomial-evaluation ring homomorphism, hence an ideal. Every is divisible by in . Because is monic, polynomial division of by takes place in , and the remainder must vanish by minimality. Therefore
where is monic and irreducible.
For
translation gives
This is Eisenstein at , so and therefore are irreducible over . Hence
Irreducibility and Gauss's lemma also show that is a prime ideal of , so
It is not a field. The class of is nonzero but not a unit: reducing further modulo gives a nonzero quotient
in which the image of is zero, whereas a unit must remain a unit under every unital quotient map. Thus
Assume that the primitive polynomial factors in as , with both factors of positive degree. Clearing denominators and removing contents writes
where and are primitive. Then
By Gauss lemma for polynomials, is primitive. Since is also primitive, comparison of contents forces to be a unit of . Absorbing that unit into one factor gives a nontrivial factorization of in , contrary to its assumed irreducibility. Hence is irreducible in .
Let
be a primitive polynomial. The Eisenstein criterion states that if a prime number satisfies
then is an irreducible polynomial in , equivalently in by Gauss lemma for polynomials.
To prove it, suppose that with of positive degree. Primitivity and Gauss's lemma let us take such an integral factorisation if a factorisation over exists. Reducing modulo gives
Because does not divide the leading coefficient of , neither factor loses degree on reduction. The polynomial ring is a unique factorization domain, so both reductions are monomials of positive degree. In particular, divides both constant terms and . It follows that divides
a contradiction. This proves the criterion.
For a prime , translate the geometric sum by one:
Its leading coefficient is one, every other coefficient is divisible by , and its constant coefficient is , which is not divisible by . It is therefore Eisenstein at . Translation is an automorphism of , so
This is the geometric-sum irreducibility criterion.
The evaluation homomorphism
has image and contains in its kernel. Since is monic, division by in writes every as with . If , then ; the irreducibility of says that is the minimal polynomial of , so . Thus , and the first isomorphism theorem for rings gives
Now take . Then , and the Eisenstein integers are
Complex conjugation sends to , so the field norm is
Given , choose integers with . For ,
For with , apply this to and put . Then
Hence the norm is a Euclidean function, proving that is a Euclidean domain. This is the Euclidean norm on the Eisenstein integers.
Finally suppose satisfies . Make the free abelian group into a -module by defining
This is well-defined precisely because obeys the same polynomial relation as . The module is finitely generated. It is also torsion-free module: if and , multiplication by the conjugate of gives , and the additive group has no nonzero integer torsion.
A Euclidean domain is a principal ideal domain, and the structure theorem for finitely generated modules over a principal ideal domain says that a finitely generated torsion-free module over one is free. Thus
for some . Since has free module basis over , comparison of abelian ranks gives . There can consequently be no such matrix when is odd.
If , choose a -basis . Then
is a -basis, and . In this basis the matrix of is a direct sum of copies of
Every admissible matrix is therefore conjugate in to . Hence there is exactly one conjugacy class for even , and none for odd . This is the classification of integral matrices satisfying the third cyclotomic polynomial.
Polynomial content Created 2026-09-24 Updated 2026-11-05
For a nonzero polynomial over a unique factorization domain, its content is a greatest common divisor of its coefficients, defined up to a unit. Over , choose the positive gcd. For example, has content two and primitive part . Gauss lemma for polynomials says that content is multiplicative up to units in this setting.
For a polynomial over a general commutative ring, another common convention uses the ideal generated by its coefficients as its content. This convention does not require gcds. The two descriptions agree through a principal coefficient ideal when that ideal is principal, but a unit gcd need not make the coefficient ideal the whole ring. For example, the coefficients of over have gcd one and generate the proper ideal . State the convention before using content to define a primitive polynomial.
The prime ideals of with are the zero ideal and the principal ideals generated by nonconstant primitive polynomials that are irreducible in .
To prove the description, invert the nonzero integers to obtain the localization . The extension of an ideal consists of the polynomials with and . Its contraction is : if and , the defining condition puts , so primeness gives . The prime ideal correspondence for localization makes this extension a proper prime ideal of .
If , its extension has a nonzero generator because is a principal ideal domain. Dividing this generator by its rational polynomial content gives an integer-coefficient primitive polynomial generating the same extended ideal. Divisibility descent by Gauss lemma for polynomials then gives in . The proper prime ideal in makes irreducible there. Conversely, any such polynomial generates a prime ideal in whose contraction is and whose intersection with is zero.
The intersection condition is essential: is a maximal ideal of , since its quotient ring is , but it is not principal. A common divisor of and must be a unit, which would generate the whole ring.
Primitive polynomial over a finite field Created 2026-10-14 Updated 2026-11-05
A monic polynomial of degree over that is an irreducible polynomial is primitive in the finite-field sense when one of its roots generates the multiplicative group of a finite field . All its roots are Frobenius conjugates and then have the same order . This notion differs from a primitive polynomial over an integral domain, which concerns the common divisor of its coefficients. Primitive finite-field polynomials provide explicit field representations and primitive cyclic Reed-Solomon codes or BCH codes.
For a nonzero polynomial , choose a positive integer clearing its denominators and set , where the polynomial content of an integer-coefficient polynomial is the positive greatest common divisor of its coefficients. This is independent of : if , then , hence .
The integer-coefficient product formula from Gauss lemma for polynomials gives
Moreover is an integer-coefficient primitive polynomial: if , then . For example,
This normalization proves a useful divisibility descent. If is primitive, and for , then is an integer. Since , it follows that .