Have you tried writing as p(x) = q(x)g(x) + r(x)?

Edit: Actually I'm not sure if the above is helpful, but maybe an approach that will work is an extension of the Chinese remainder theorem.

Edit 2 (written LONG after the original post and first edit): Since my answer wasn't very elucidating, I'm posting links to two other threads, here and here, which give better answers than what I gave.