Exploration 5: Irreducibility

If an element $r$ is associate to $1$, it means $r=1u$ for some unit $u$, which implies $r$ is that unit.

This is because if two nonzero elements $a,b$ generate each other, then $a=bx$ and $b=ay$ implying $a\mid b$ and $b\mid a$.

Assume $a\mid b$. If $c$ is an arbitrary associate of $a$ ($c\sim a$), then $a=uc$ for some unit $u$, thus: $$\begin{aligned} a&\mid b\\ uc&\mid b\\ uc&=bd&\text{ for some }d\\ c&=b(u^{-1}d)\\ c&\mid b \end{aligned}$$

• Recall that elements that divide each other are associate.
• If there are two GCDs, then by definition they divide each other and are thus associates.
• Similarly, if there are two LCMs, then by definition they are a multiple of each other, meaning they divide each other, and are thus associates.

• It is enough to prove that the two sides divide each other.
• $\gcd(ca,cb)\mid c\cdot\gcd(a,b)$: any divisor of both $a$ and $b$ must divide $\gcd(a,b)$, by definition of GCD. Multiplying by $c$, any divisor of both $ca$ and $cb$ must divide $c\cdot\gcd(a,b)$. But $\gcd(ca,cb)$ is such a divisor.
• $c\cdot\gcd(a,b)\mid\gcd(ca,cb)$: since $\gcd(a,b)$ divides both $a$ and $b$, multiply by $c$ to find that $c\cdot\gcd(a,b)$ divides both $ca$ and $cb$. Therefore it also divides their greatest common divisor, $\gcd(ca,cb)$.

• ($\to$)
  • Since every irreducible is prime in a factorization domain, it’s a UFD (proof) and therefore every element has a unique factorization into prime elements.
  • Then to get the GCD, you can just take the unique product of all the common factors of two elements, which means taking the minimum exponent of each common prime power factor.
  • (Note that you can similarly get the LCM by taking the unique product of all the common multiples of two elements, which means taking the maximum exponent of each common prime power factor.)
• ($\from$)
  • Given irreducible $p$, WTS it is prime.
  • If $p\mid ab$, then $d=\gcd(a,p)$ is a divisor of $p$.
  • Since $p$ is irreducible, either $d\sim p$ or $d\sim 1$.
  • If $d\sim p$, we already know that $d\mid a$ by definition of GCD. Since associates of divisors are also divisors (proof), we have $p\mid a$.
  • Otherwise, $d\sim 1$ means $\gcd(a,p)\sim 1$. Multiply by $b$ on both sides to get $\gcd(a,p)b\sim b$. Then by the lemma, $\gcd(ab,pb)\sim b$, and therefore $ab\mid b$. Recalling that $p\mid ab$, this implies $p\mid b$.
  • So either $p\mid a$ or $p\mid b$, meaning irreducible $p$ is prime.

This is because a factorization domain is a UFD iff every irreducible is prime, which we just proved is equivalent to saying GCDs exist.

• If we divide some $f\in R$ by some nonzero $g\in R$, we have $f=gq_1+r_1$ for some $q_1,r_1\in F[x]$ (where either $r_1=0$ or $\deg r_1<\deg g$.)
• If $r_1=0$, we are done: then $\gcd(f,g)=f$ and we have $\gcd(f,g)=1f+0g$.
• Otherwise, dividing $g$ by $r_1$ gives $g=r_1q_2+r_2$.
• If $r_2=0$, we are done: then $\gcd(f,g)=r_1$ and $f=gq_1+r_1$ implies $\gcd(f,g)=1f-q_1g$.
• Otherwise, dividing $r_1$ by $r_2$ gives $r_1=r_2q_3+r_3$.
• If $r_3=0$, we are done: then $\gcd(f,g)=r_2$ and $g=r_1q_2+r_2$ implies $\gcd(f,g)=g-r_1q_2$, which simplifies to $$\begin{aligned} \gcd(f,g)&=g-r_1q_2\\ &=g-(f-gq_1)q_2&\text{ using }f=gq_1+r_1\\ &=g-fq_2+gq_1q_2\\ &=(-q_2)f+(1+q_1q_2)g\\ \end{aligned}$$
• Otherwise, the idea is to continue doing this until you get $r_k=0$, thus $\gcd(f,g)=r_{k-1}$ and you can backsubstitute each $r_i$ to express the GCD as a linear combination $\gcd(f,g)=af+bg$ for some $a,b$.

Coprime means the GCD is associate to $1$, so $\gcd(f,g)=af+bg$ becomes $1=af+bg$.

Since $f$ is prime, its only nonunit divisor is $f$. Therefore $\gcd(f,g)=f$ if $f\mid g$, and $\gcd(f,g)=1$ otherwise.

$(p)$ (being a nonzero principal ideal) contains every element with a factor of $p$, so any element $r\in R$ outside of $(p)$ must be coprime to $p$. Since adding any outside element $r$ to $(p)$ makes it equal to $(p,r)=(\gcd(p,r))=(1)=R$, i.e. not a proper ideal anymore, $(p)$ must be maximal.

Since Euclidean domains are PIDs, and nonzero prime ideals $(p)$ are maximal in PIDs, either $(p)$ is zero or a maximal ideal. If $(p)$ is zero then $R/(p)\cong R$ results in the same ring, which is a Euclidean domain. If $(p)$ is maximal, then $R/(p)$ is a field and therefore a Euclidean domain.

This is because polynomial rings defined over a field are Euclidean domains.

According to the factor theorem, having a root $a$ means $f=(x-a)q$, where $\deg q$ is at least $1$ since $\deg f$ is at least $2$. But that means you just factored into two non-unit factors $(x-a)$ and $q$, meaning that $f$ is reducible.

When we factor a polynomial $f$ into a product $ab$, we have $f=ab$ implies $\deg f=\deg a+\deg b$. If $\deg f$ is $2$ or $3$ and has no roots (i.e. linear ($\deg 1$) factors, by the factor theorem), necessarily one of $\deg a$ and $\deg b$ must be $0$, meaning $f$ is irreducible.

• Towards contradiction, assume $f$ is not irreducible in $\QQ[x]$. Then there is a proper factorization $f=gh$, where $\deg g<\deg f$.
• We know that $\deg\bar{g}\le\deg g$ since it’s possible that the leading coefficient of $g$ gets mapped to $0$, decreasing its degree. This isn’t possible for $\bar{f}$ since it’s given that $p$ doesn’t divide the leading coefficient of $f$. So overall, we have $$\deg\bar{g}\le\deg g<\deg f=\deg\bar{f}$$
• Similarly for $h$, $$\deg\bar{h}\le\deg h<\deg f=\deg\bar{f}$$
• But since $f=gh$, we know $\bar{f}=\bar{g}\bar{h}$ where $\deg\bar{g}<\deg\bar{f}$ and $\deg\bar{h}<\deg\bar{h}$, implying there is a proper factorization for $f$ in $\ZZ_p[x]$. But this contradicts our second assumption.

The rational roots theorem works, but reduction $\bmod~3$ is much easier. Reduction becomes $x^3+x^2+2$ in $\ZZ_3[x]$. Trying each of $x=0,1,2$ shows that this has no root, therefore irreducible, therefore the original polynomial is irreducible.

Reduction $\bmod~2$ gives $x^4+x^2+1$ in $\ZZ_2[x]$. Trying each of $x=0,1$ shows that this has no root, so to be irreducible it must factor into two quadratics with no root. The only quadratic with no root in $\ZZ_2[x]$ is $x^2+x+1$ (Example 5) so that must be the factor. But $(x^2+x+1)^2=x^4+2x^3+3x^2+2x+1$ which is not $f$. So there is no proper factorization of $x^4+x^2+1$ in $\ZZ_2[x]$, so $x^4+2x^3+2x^2-x+1$ is irreducible in $\QQ[x]$.

• If $a_i$ and $b_j$ are the coefficients of $f$ and $g$ respectively, then every coefficient of $fg$ is some sum $\sum a_ib_j$.
• But $c(fg)$, being the GCD of every coefficient $\sum a_ib_j$, contains exactly the irreducible factors common to all $a_ib_j$.
• In a UFD, factorization is unique (up to associates), so containing all irreducible factors common to all $a_ib_j$ implies containing all irreducible factors common to all $a_i$ ($=c(f)$) along with all irreducible factors common to all $b_j$ ($=c(g)$).
• This implies $c(fg)$ and $c(f)c(g)$ have the same unique factorization up to associates, and are therefore associate.

• We need to prove that (1) the ACCP holds in $R[x]$ and (2) all irreducible elements of $R[x]$ are prime.
• Since $R$ is a UFD, it satisfies ACCP, and therefore $R[x]$ satisfies ACCP.
• WTS irreducibles are primes. Say we have some irreducible $p$. Then, note that the quotient $R[x]/(p)$, polynomials where $p$ is sent to $0$, is isomorphic to $R_p[x]$, polynomials where coefficents are mod $p$.
• Then for every irreducible $p\in R$:

• This requires proving the converse of the above: $R[x]$ is a UFD implies $R$ is a UFD.
• Take any constant polynomial $c\in R[x]$. Since $R[x]$ is a UFD, there is a unique factorization of $c$ into irreducibles in $R[x]$. Since for $c=ab$ we must have $\deg c=\deg a+\deg b$, and $\deg c=0$, the degree of every factor in the factorization of $c$ must be $0$. This implies that any factorization of $c$ involves only constant polynomials $\in R$, and therefore if it’s unique in $R[x]$, it’s unique in $R$.
• Then we need only prove that the units of $R[x]$ are the units of $R$, and that the irreducibles in $R[x]$ are also irreducible in $R$.
  • If $r\in R[x]$ is a unit, then $rr^{-1}=1$ by the same degree argument means both $r$ and $r^{-1}$ must be constant polynomials, and therefore units in $R$.
  • Any $a\in R$ reducible in $R$ is reducible in $R[x]$. Taking the contrapositive, any $a\in R$ irreducible in $R[x]$ is irreducible in $R$.
• Therefore, the unique factorization of $c$ into irreducibles in $R[x]$ (up to associates in $R[x]$) is also a unique factorization of $c$ into irreducibles in $R$ (up to associates in $R$). Since this is true for every $c\in R$, $R$ is a UFD.

• WTS if $\gcd(a,b)=c$ in $R$, then $\gcd(\frac{a}{1},\frac{b}{1})=\frac{c}{1}$ in $F$.
• Take any common divisor $d/f$ of $\frac{a}{1},\frac{b}{1}$ in $F$. Since $F$ is a field, we can consider numerators and denominators separately. The numerators imply $d\mid a$ and $d\mid b$ in $R$, and since $1$ has only the divisor $1$, the denominators imply $f=1$.
• WTS $\frac{d}{1}$ divides the GCD $\frac{c}{1}$. Since $d$ is a common divisor of $a,b$ in $R$, and $c$ is the GCD of $a,b$ in $R$, $d$ divides $c$. But then $\frac{d}{1}$ divides $\frac{c}{1}$. Therefore, $\frac{c}{1}$ is also the GCD in $F$.

• ($\to$) Let $f$ be a primitive polynomial in $R[x]$. By Gauss’ lemma, which states $c(ab)\sim c(a)c(b)$, any factors $f_i$ of $f$ are also primitive. Since primitive polynomials in $R[x]$ are primitive in $F[x]$, $f_i$ are primitive in $F[x]$. That means there are no factors to be pulled out of each $f_i$ in $F[x]$, implying the two factorizations are the same (up to associates).
• ($\from$) Let $f$ be a primitive polynomial in $F[x]$. Let $f=\frac{a}{b}\cdot\frac{c}{d}$ for $a,b,c,d\in R[x]$ where $b,d$ are nonzero. Then $bdf=ac$, and this equation should also hold true in $R[x]$. Since $f$ is primitive, $ac$ is also primitive (by Gauss’ lemma), and therefore $bd$ must be a unit. Therefore $f=ac$, and the factorizations are the same (up to associates)

Recall that the representative example of fields of fractions is $\QQ$ being the field of fractions of $\ZZ$.

• First, we prove that if $p$ divides all coefficients of $f\in\ZZ[x]$ except the leading coefficient, then $f$ being reducible in $\ZZ[x]$ implies $p^2$ must divide the constant coefficient.
  • If every coefficient of $f$ but the leading coefficient has a factor $p$, then take the reduction mod $p$ to get $\bar{f}=ax^n\in\ZZ_p[x]$.
  • Since $f$ is reducible in $\ZZ[x]$, it is reducible and therefore has a proper factorization in $\ZZ_p[x]$.
  • $p$ is prime, so $\ZZ_p[x]$ is a UFD. (proof) Then the unique proper factorization of $ax^n$ looks like $ax^n=(bx^i)(cx^j)$.
  • Since the factors $bx^i,cx^j$ are all zero in their non-leading coefficients, then back in $\ZZ[x]$ they both must have a factor $p$ in all non-leading coefficients.
  • But this implies that the constant coefficient of $ax^n=(bx^i)(cx^j)$ in $\ZZ_[x]$ has a factor $p^2$.
• Take the contrapositive: if the constant coefficient has no factor $p^2$, then $f$ is irreducible in $\ZZ[x]$.
• Then use Gauss’ Lemma: $f$ irreducible over $\ZZ[x]$ iff $f$ irreducible over $\QQ[x]$.

• This shift is an automorphism on $R[x]$, therefore it preserves irreducibility.
• Combine with Eisenstein to show that if the criterion holds after a shift, the original polynomial is irreducible.
• TODO explain this better

Eisenstein criterion with $p=3$.

This polynomial is $x^n-2$, which is irreducible by the Eisenstein criterion with $p=2$.

Eisenstein Criterion: For a polynomial $f\in\ZZ[x]$ of degree $\ge 1$, suppose there is a prime $p$ where

1. $p$ divides all coefficients of $f$, except
2. $p$ does not divide the leading coefficient, and
3. $p^2$ does not divide the constant coefficient.

Then $f$ is irreducible in $\QQ[x]$.

TODO

Replace $x$ with $x+1$ and apply binomial theorem. TODO