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]$?

This statement is part of the proposition 2.5 in this article.

  • $\begingroup$ Your bulleted items don’t mention $f$ nor $g$. Could you please edit? $\endgroup$ – Lubin Mar 26 '14 at 21:23
  • $\begingroup$ @Lubin thanks, fixed, I don't know what I was doing when writing this up. $\endgroup$ – BoZenKhaa Mar 26 '14 at 21:42
  • $\begingroup$ You can just write $h \, | \, f \pmod p$ for short. Your notation is very heavy to read. $\endgroup$ – Patrick Da Silva Mar 26 '14 at 21:49
  • $\begingroup$ @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. $\endgroup$ – BoZenKhaa Mar 26 '14 at 21:56
  • $\begingroup$ 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. $\endgroup$ – 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).

| cite | improve this answer | |
  • $\begingroup$ 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 ..." $\endgroup$ – BoZenKhaa Mar 26 '14 at 23:33
  • $\begingroup$ @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. $\endgroup$ – blue Mar 26 '14 at 23:34
  • $\begingroup$ 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. $\endgroup$ – BoZenKhaa Mar 26 '14 at 23:39
  • $\begingroup$ @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. $\endgroup$ – blue Mar 26 '14 at 23:42
  • $\begingroup$ 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$ $\endgroup$ – BoZenKhaa Mar 26 '14 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.