# Relation between divisibility of polynomials in different rings, $h | f$ in $\mathbb{Z}[x], \mathbb{Z}/p^k\mathbb{Z}[x]$ and $\mathbb{F}_p[x]$

Let $p$ be a prime, $k$ a positive integer. Let $f,h \in \mathbb{Z}[x]$ be polynomials such that

• $h | f \mod p^k$ in $(\mathbb{Z}/p^k\mathbb{Z})[x]$
• $h \mod p$ is irreducible in $\mathbb{F}_p$

Then $f$ has an irreducible factor $h_0$ in $\mathbb{Z}[x]$ such that $h | h_0 \mod p$. Here, $\sum_i a_ix^i (\mod p)$ means $\sum_i (a_i \mod p)x^i$.

Why is this true? Are there some general results connecting divisibility in $\mathbb{Z}[x], \mathbb{Z}/p^k\mathbb{Z}[x]$ and $\mathbb{F}_p[x]$?

• Your bulleted items donâ€™t mention $f$ nor $g$. Could you please edit? – Lubin Mar 26 '14 at 21:23
• @Lubin thanks, fixed, I don't know what I was doing when writing this up. – BoZenKhaa Mar 26 '14 at 21:42
• You can just write $h \, | \, f \pmod p$ for short. Your notation is very heavy to read. – Patrick Da Silva Mar 26 '14 at 21:49
• @PatrickDaSilva change. I think that might be a part of the reason why I am having such hard time with this. That and the fact that I rarely ever had to deal with finite fields. – BoZenKhaa Mar 26 '14 at 21:56
• If $h$ divides $f$ modulo $p^k$, then $f \equiv gh \pmod {p^k}$, hence $f \equiv gh \pmod p$. If $h$ is irreducible $\pmod p$, this means $h$ divides some irreducible factor of $f$ modulo $p$. Call this factor $h_0$. Then you most probably use Hensel's lemma to lift your factor $\pmod p$ to a factor in the $p$-adics, and then argue that your factor has integer coefficients. I can't really do this argument right now, but that's my first guess. – Patrick Da Silva Mar 26 '14 at 22:00

Here is a clean way to describe the situation: factorizations refine in residues.

If $a\in A$ and $a=a_1\cdots a_n$ and $\pi:A\to B$ and $B$ is a UFD and $\pi(a)=b_1\cdots b_m$ is its factorization into irreducibles (repetitions allowed) then we can partition the factors $b_i$ in such a way that each multiset of factors is precisely the multiset of irreducible factors of one of the $\pi(a_i)$s up to units.

The proof of this is quite straightforward: use the fact that $\pi(a)=\pi(a_1)\cdots\pi(a_n)$, that each of these $\pi(a_i)$s factors into irreducibles, and that cumulative total of these must be $\{b_i\}$ since $B$ is a unique factorization domain.

In particular, this applies with $A=\Bbb Z[x]$ and $B=\Bbb F_p[x]$. Every irreducible factor of $\overline{f}(x)$, i.e. the mod $p$ residue of some $f(x)\in\Bbb Z[x]$, "comes from" an irreducible factor of the original $f(x)$, i.e. divides the mod $p$ residue of some irreducible factor in $\Bbb Z[x]$ of $f(x)$.

For this conclusion to be drawn from our hypotheses, it is enough that we work mod $p$; working modulo higher powers of $p$ is superfluous.

Notice that when going from $\Bbb Z$ to $\Bbb F_p$, factorizations are allowed to "break down" further. So given a residual factorization, in order to lift it back to $\Bbb Z$ we would have to "clump" atoms together. If we extend our scalars to the $p$-adic integers $\Bbb Z_p$, we don't necessarily have to do any clumping, and can keep the same exact shape of factorization. Given $a(x)=a_1(x)a_2(x)\cdots a_n(x)$ for polynomials in $\Bbb F_p[x]$, under some mild conditions this lifts up to $A(x)=A_1(x)A_2(x)\cdots A_n(x)$ for polynomials in $\Bbb Z_p[x]$, where $A(x)\equiv a(x)$ and $A_i(x)\equiv a_i(x)$ mod $p$ are lifts; if the original factors were in fact irreducible, then we can guarantee the lifts are too. A special case of this is in lifting linear factors, which amounts to lifting roots mod $p$, and this is done with Hensel's lemma (a non-archimedean form of Newton's method for root approximation).

• Thank you, I think this very neatly formalizes what I was crudely attempting in the comments. I have one question, what do you mean by ".... cummulative total of these must be ..." – BoZenKhaa Mar 26 '14 at 23:33
• @BoZenKhaa Each $\pi(a_i)$ has an associated multiset of irreducibles. If you collect them up as $i$ ranges from $1$ to $n$, then you have the cumulative total. – blue Mar 26 '14 at 23:34
• Well, I also have a second question. This will not work for $\mathbb{Z}/k\mathbb{Z}$ with arbitrary $k$, right? As it is not UFD, there could be a factorization of f (in mod k) that is divided by some irreducible element, h|f mod k, but this element h does not divide any of the images of the original factors of f=ab in $Z$. Is that correct? I know it is not needed in the prove, I am just checking whether I understood this right. – BoZenKhaa Mar 26 '14 at 23:39
• @BoZenKhaa Two facts: if $R$ is a PID then $R$ is a UFD, and if $R$ is a UFD then $R[x]$ is a UFD. In particular, $R=\Bbb Z/k\Bbb Z$ is a PID for any $k$ (you can use lattice correspondence + $\Bbb Z$ is a PID if you want) so $(\Bbb Z/k\Bbb Z)[x]$ is a UFD. – blue Mar 26 '14 at 23:42
• I probably do not understand the notation, I was thinking that the associated irreducibles of $\pi(a)$ are those $b_i$ such that $\pi(a)=\prod_i b_i$ – BoZenKhaa Mar 26 '14 at 23:43