Lecture 13 Notes: More Factorization

Lecture 13: More Factorization 13 More Factorization 13.1 Factoring Integer Polynomials We’ve seen that Z, F [x], and Z[i] are unique factorization domains — in fact, we’ll later look into a neat application of unique factorization in Z[i] to a problem in number theory. First we’ll discuss factorization in Z[x]. We previously stated the following theorem: Theorem 13.1 If R is a unique factorization domain, then R[x] is also a unique factorization domain. We’ll prove this for the case R = Z. The proof of the general case is very similar to the proof for Z — we essentially just have to replace the familiar construction of the gcd over integers with the more abstract notion of gcd in a general UFD, as discussed last time. Guiding Question Given a polynomial P ∈ Z[x], there’s two natural questions we can ask about its factorization: 1. Is it possible to factor P where the factors lie in Q[x]? 2. What about in Z[x]? There are more tools available for approaching the second question, factoring in Z[x], which make it possible to reduce the potential factorizations to a finite number of possibilities. One such tool is reducing mod a prime p. Example 13.2 Consider the polynomial P (x) = 3x2 + 2x + 2. We can show it’s impossible to factor P in Z[x] by reducing mod 2 — we have P (x) ≡ x3 (mod 2). But the only way x3 factors in F2 [x] is as x3 · 1 or x2 · x. If P factored as P1 P2 where P1 and P2 had positive degree, then since their leading coefficients must be odd (as these leading coefficients multiply to 3), they must still have positive degree in F2 [x]. So P1 and P2 must be congruent to x and x2 mod 2; in particular, both their free terms are divisible by 2. But the free term of P would then be divisible by 4, which is a contradiction. This example illustrates one possible trick that can be used to show that a polynomial is irreducible in Z[x]. There are various other tricks as well. For example, the product of the free terms of the factors must equal the free term of the original polynomial; so we can look at all possible factorizations of the free term. On the other hand, factoring polynomials in Q[x] seems much more difficult, since these tricks no longer work — there’s infinitely many ways to factor the free term of the original polynomial as a product of rationals, so this argument can’t be used to reduce our search to finitely many possibilities. Fortunately, it turns out that factoring over Z[x] and Q[x] are actually equivalent. To show this, recall the definition of a primitive polynomial from last class, here applied specifically to Z[x]: Definition 13.3 A polynomial P ∈ Z[x] is primitive if the gcd of all its coefficients is 1. Evidently, any nonzero P ∈ Z[x] can be written as a product P = nQ, where Q is primitive and n is the gcd of the coefficients of P . In fact, any P ∈ Q[x] can be scaled to a primitive polynomial, by clearing denominators and factoring out the gcd of its coefficients. The key point in relating factorization in Z[x] and Q[x] is Gauss’s Lemma, which we proved last class: Lemma 13.4 (Gauss’s Lemma) If P and Q are primitive, then P Q is as well. Lecture 13: More Factorization Proof Sketch. If P Q is not primitive, then there is some prime p which divides all coefficients of P Q. Now consider P and Q mod p; since both are nonzero mod p, it’s clear that their product is nonzero mod p as well — the integers mod p are a field, and for polynomials over a field, it’s impossible to multiply two nonzero polynomials and get the zero polynomial. Using Gauss’s Lemma, we can reduce questions about divisibility in Z[x] to ones about divisibility in Q[x], via the following corollary: Corollary 13.5 If P, Q ∈ Z[x] are such that P divides Q in Q[x] and P is primitive, then P divides Q in Z[x]. Proof. We have Q = P · S for some S ∈ Q[x]. Now write S = aT /b where T ∈ ZZ[x] is primitive, and a and b are integers with b ̸= 0. Then the equation can be rewritten as bQ = aP T. By Gauss’s Lemma, P T is primitive, so the gcd of all coefficients of aP T is exactly a. Meanwhile, b certainly divides all coefficients of bQ, so it divides all coefficients of aP T as well, which means b | a. As a result, a/b ∈ Z, so S ∈ Z[x] and P divides Q in Z[x] as well. Note 13.6 There’s a different way to phrase this proof — for polynomials P ∈ Z[x], we can define the content of P , denoted c(P ), as the gcd of the coefficients of P . It’s possible to extend this to polynomials in Q[x] as well, such that for any T ∈ Q[x] and a ∈ Q, we have c(aT ) = a · c(T ). Then Gauss’s Lemma states that c(P Q) = c(P )c(Q) for any P, Q ∈ Z[x], and therefore for any P, Q ∈ Q[x] as well. Now in this proof we have Q = P S, which means c(Q) = c(P )c(S). But c(Q) is an integer and c(P ) = 1, so c(S) must be an integer as well; therefore S has integer coefficients. As a result, factoring in Z[x] and Q[x] are in fact equivalent. Example 13.7 The polynomial 3x2 + 2x + 2 is irreducible in Z[x], so it cannot be factored in Q[x] either. Corollary 13.8 The irreducible elements in Z[x] fall into two categories: ±p for prime integers p, and primitive polynomials which are irreducible in Q[x]. It’s not necessarily easy to tell whether a polynomial is irreducible; but this does mean that answering the question of whether a polynomial is irreducible in Q[x] is as easy as answering it in Z[x]. Proof. It’s clear that both categories of elements are irreducible — the primes are clearly irreducible in Z[x], since the only way to factor a constant polynomial is as a product of constants. Meanwhile, if a polynomial is irreducible in Q[x], then the only way it can be factored is by pulling out constant factors; but this is impossible for a primitive polynomial, so all such polynomials must be irreducible in Z[x] as well. On the other hand, if P is not of either form, then we’ll show that P can be factored and therefore is not irreducible. First, if deg(P ) = 0 (meaning P is an integer), then it’s clear that it must be prime in order to be irreducible. Now assume that deg(P ) ≥ 1. If P is not primitive, then we can pull out the greatest common divisor of its coefficients. Meanwhile, if P is primitive but factors in Q[x], then P = Q1 Q2 . We can rescale Q1 by taking integers a and b such that aQ1 /b is in Z[x] and primitive. Then by Lemma 13.5, aQ1 /b must divide P in Z[x] as well, giving a nontrivial factorization of P . Theorem 13.1 for Z follows as a corollary. Lecture 13: More Factorization Corollary 13.9 The polynomials with integer coefficients, Z[x], form a unique factorization domain. Proof. As usual, we need to prove that a factorization exists and is unique. We’ll first prove existence. First, by factoring out constants we can write P = p1 · · · pℓ P1 such that P1 is primitive and the pi are primes. If P1 is irreducible in Q[x], we are done, as it is also irreducible in Z[x]. Otherwise, P1 factors in Q[x], and we can rescale both factors so that they are primitive elements of ZZ[x], so then P1 factors in Z[x]. We can continue to attempt to factor the two resulting factors of P1 . As we keep on factoring, the degrees of our polynomials decrease at every step, so the factorization process must terminate — which means that eventually, all our polynomials become irreducible. Now we’ll prove uniqueness. As in all the other cases where we proved uniqueness, it is enough to show that if an irreducible polynomial P ∈ Z[x] divides Q1 Q2 , then P divides either Q1 or Q2 . (Then similarly to in the proof that every PID is a UFD, given two factorizations P1 · · · Pn and Q1 · · · Qm , we can show that P1 must appear in the second factorization as well, cancel it out from both, and repeat with the remaining factorizations until we’ve matched up all the factors.) In order to show this result, we have two cases. First, if P is an integer prime p ∈ Z, then this follows directly from the fact that the product of two nonzero polynomials in (Z/pZ)[x] is nonzero, as Z/pZ is a field. Otherwise, P is primitive and irreducible in Q[x]. We have that if P | Q1 Q2 , then P | Q1 or P | Q2 in Q[x] (since Q is a field, so Q[x] is a PID and therefore a UFD). By Lemma 13.5, since P is primitive, then P must divide Q1 or Q2 in Z[x]. So this shows that for any irreducible P ∈ Z[x], if P | Q1 Q2 then P | Q1 or P | Q2 , as desired. As mentioned earlier, the same proof used to show that Z[x] is a UFD would work if we replaced Z with any UFD R. For example, we can even take R to be Z[x], now that we know it’s a UFD; this shows that Z[x, y] is also a UFD. 13.2 Gaussian Primes Unique factorization in Z[i] has an interesting application — it can be used to solve a problem in number theory. Guiding Question Which integers can be written as n = a2 + b2 for integers a and b? Example 13.10 We can write 5 = 22 + 12 , while 6 and 21 cannot be written as a sum of squares. On the way to proving the answer, we’ll classify irreducible elements in Z[i]. (Since Z[i] is a UFD, the irreducible elements are exactly the primes, so we will use “prime” and “irreducible” interchangeably here.) This is an example of how the abstract property of unique factorization can lead to concrete results. First, note that n = a2 + b2 can be rewritten as n = (a + bi)(a − bi). This makes it clear that if n and m can be written in the form a2 + b2 , then so can mn — if n = αα and m = ββ, then (αβ)(αβ). So the property is multiplicative, which motivates considering the special case where n is prime. Lemma 13.11 Let p ∈ Z be a prime number. Then p = a2 + b2 if and only if p is not a prime in Z[i]. We refer to primes in Z[i] as Gaussian primes. Proof. First, if p were a Gaussian prime and we could write p as a sum of squares, then we would have p = (a + bi)(a − bi), Lecture 13: More Factorization which would mean p must divide either a + bi or a − bi. In either case, p would need to divide both a and b, which is impossible. Meanwhile, if p is not a Gaussian prime, since it’s real and doesn’t factor in Z, it must factor as p = αα for some α ∈ Z[i] which is not in Z. So then α = a + bi for some integers a and b, which means p = a2 + b2 . So answering our initial question for primes is equivalent to figuring out which integer primes are also Gaussian primes. Lemma 13.12 Let p ∈ Z be a prime number. Then p is not prime in Z[i] if and only if p = 2 or p ≡ 1 (mod 4). Proof. First, 2 factors as 2 = (1 + i)(1 − i). Now suppose p > 2. Claim. p is not a prime in Z[i] if and only if there exists α ∈ Z[i] such that p ∤ α, but p | αα. Proof. By definition, p is not a prime in Z[i] if and only if there exist α and β such that p divides αβ, but not α or β. It immediately follows that if there exists an α ∈ Z[i] with the described properties, then p is not prime. On the other hand, if p is not prime, then take α and β such that neither is divisible by p but αβ is; then p | αβαβ = (αα)(ββ). Since p is an integer prime, and both αα and ββ are integers, then p must divide one of them, and either α or β has the described properties. This turns the question into one over Fp — then p is not a prime in Z[i] if and only if there exist a, b ∈ Fp , which are not both 0, such that a2 + b2 = 0. Since Fp is a field, we can divide by b2 and rewrite the equation as −1 = (ab−1 )2 , so this is true if and only if −1 is a square in Fp . Now consider the abelian group F× p (the multiplicative group of Fp ) which has order p − 1. The only element of order 2 is −1, since x2 − 1 = (x − 1)(x + 1) × 2 has no roots other than ±1, and 1 has order 1. This gives a homomorphism φ : F× p → Fp sending α → α . Then ker(φ) = {±1}, so by the homomorphism theorem, im(φ) has (p − 1)/2 elements. But −1 is a square in Fp if and only if it is in the image of φ. Since im(φ) is a subgroup of F× p , this occurs if and only if im(φ) contains an element of order 2 (since the only possible element of order 2 is −1). But im(φ) contains an element of order 2 if and only if |im(φ)| = (p − 1)/2 is divisible by 2 — one direction follows from the fact that the order of every element divides the order of the group, and the other follows from the Sylow Theorems. So −1 is a square if and only if (p − 1)/2 is even, or equivalently p ≡ 1 (mod 4). So an odd integer prime p is not a Gaussian prime if and only if p ≡ 1 (mod 4). This proof can be used to classify the Gaussian primes up to association (multiplying by units, here ±1 and ±i). Theorem 13.13 The full list of primes in Z[i], up to association, can be constructed as follows: consider all integer primes p. • If p ≡ 3 (mod 4), then p itself is a Gaussian prime. • If p ≡ 1 (mod 4), then it factors as (a − bi)(a + bi), and both factors a ± bi are Gaussian primes. • If p = 2, then it factors as (1 + i)(1 − i), and since 1 + i and 1 − i are associate, they correspond to the same Gaussian prime.