Let $a_{i,j}$ denote the coefficients of the polynomials so that $f_i(x)=\sum_{j=0}a_{i,j}x^j$. Let $p_1,p_2\ldots,p_n,p_{n+1}$ be distinct primes such that $p_{n+1}$ is not a root of $f_i(x)$ and $p_i\nmid f_i(p_{n+1})$ for all $i=1,2,\ldots,n$. Let $d=\max\limits_{1\leq i\leq n}\deg f_i$. For $0\leq j\leq d$ let $b_j$ be an integer such that $b_j \equiv -a_{i,j}+p_i \bmod p^2_i$ for all $i=1,2,\ldots,n$ and $b_j\equiv 0 \bmod p_{n+1}^{d+1}$. The existence of such $b_j$ integers is guaranteed by the Chinese remainder theorem. Let $b_{d+1}=-\frac{1}{p_{n+1}^{d+1}}\sum_{j=0}^{d}b_jp_{n+1}^j$. We show that $g(x) = \sum_{j=0}^{d+1}b_{j}x^j$ satisfies the required conditions. On one hand $g(x)$ can be factored, because $\sum_{j=0}^{d+1}b_{j}p_{n+1}^j=0$ so $p_{n+1}$ is a root of $g(x)$. On the other hand, $p_i\mid b_j+a_{i,j}$ for all $i=1,\ldots,n$ and $j=0,1,\ldots,d$, $p_i^2\nmid b_0+a_{i,0}$ for all $i=1,2,\ldots,n$ and $p_i\nmid b_{d+1}\iff p_i\nmid b_{d+1}p_{n+1}^{d+1} = -\sum_{j=0}^d (b_j+a_{i,j})p_{n+1}^j + \sum_{j=0}^d a_{i,j}p_{n+1}^j$ for all $i=1,2,\ldots,n$, therefore $f_i(x)+g(x)$ is irreducible as its coefficients satisfy Eisenstein's criterion.

Well, I don't get it. You build a polynomial $g$ with $g(1)=0$, thus $g$ reducible. What if there is an index $i$ with $f_i(x)=1$ also? Then $f_i+g$ is reducible ...

mavropnevma wrote: Well, I don't get it. You build a polynomial $g$ with $g(1)=0$, thus $g$ reducible. What if there is an index $i$ with $f_i(x)=1$ also? Then $f_i+g$ is reducible ... You are right, it was a stupid thing to do. Let me correct it in a minute.