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) = akxk + ... + a0, and g(x) = bkxk + ... + b0, then f = g (mod m) means that ai = bi (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 pn).
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) ) + p2 v(x)2r(x)s(x) = h(x) + terms divisible by p2. That does not quite work. Upping the power of p does not help, because we need p1 to get h(x). However, it does move us from (mod p) to (mod p2), which suggests that induction could complete the proof.
So suppose r(x)f(x) + s(x)g(x) = 1 + pm u(x) and f(x)g(x) = h(x) + pm v(x). Then put F(x) = f(x) - pm v(x) s(x), G(x) = g(x) - pm v(x) r(x). That gives: F(x)G(x) = h(x) (mod p2m), which is sufficient to give the induction.
© John Scholes
jscholes@kalva.demon.co.uk
3 Oct 1999