We use the congruence notation for polynomials (in one variable) with integer coefficients to mean that the corresponding coefficients are congruent. Thus if f(x) = a_{k}x^{k} + ... + a_{0}, and g(x) = b_{k}x^{k} + ... + b_{0}, then f = g (mod m) means that a_{i} = b_{i} (mod m) for all i. Let p be a prime and f(x), g(x), h(x), r(x), s(x) be polynomials with integer coefficients such that r(x)f(x) + s(x)g(x) = 1 (mod p) and f(x)g(x) = h(x) (mod p). Prove that for any positive integer n we can find F(x) and G(x) with integer coefficients such that F(x) = f(x) (mod p), G(x) = g(x) (mod p) and F(x)G(x) = h(x) (mod p^{n}).

**Solution**

*Fairly easy*

Suppose that r(x)f(x) + s(x)g(x) = 1 + p u(x) and f(x)g(x) = h(x) + p v(x). The obvious thing to try is F(x) = f(x) - p v(x) s(x), G(x) = g(x) - p v(x) r(x). That gives: F(x)G(x) = f(x)g(x) - p v(x) ( f(x)r(x) + g(x)s(x) ) + p^{2} v(x)^{2}r(x)s(x) = h(x) + terms divisible by p^{2}. That does not quite work. Upping the power of p does not help, because we need p^{1} to get h(x). However, it does move us from (mod p) to (mod p^{2}), which suggests that induction could complete the proof.

So suppose r(x)f(x) + s(x)g(x) = 1 + p^{m} u(x) and f(x)g(x) = h(x) + p^{m} v(x). Then put F(x) = f(x) - p^{m} v(x) s(x), G(x) = g(x) - p^{m} v(x) r(x). That gives: F(x)G(x) = h(x) (mod p^{2m}), which is sufficient to give the induction.

© John Scholes

jscholes@kalva.demon.co.uk

3 Oct 1999