Thanks to all for your comments and suggestions. The original motivation for this question was a connection between polynomials with non-negative coefficients and commutative semirings. After some search we found some papers asking for determining the least degree of a polynomial with non-negative coefficients that is divisible by a given (general) polynomial. Suprisingly similar questions were investigated repeatedly and independetly but without any deeper motivation. We deceided hence to make an overview, improvements of some results and suggested a few conjectures. The result (in the present form) can be found here http://arxiv.org/abs/1210.6868. (Suggestions and comments are welcome.)