# Solving polynomial congruences modulo a prime power

1. Apr 29, 2006

### randommacuser

Hey all, I have a problem regarding polynomial congruences. I need to find an iterative procedure for solving a polynomial congruence modulo a prime power. I've been working on the case p^2 and I want to ask my question regarding just this case. Hopefully once I understand the proof here I can extend it generally myself.

I have seen some proofs of this process, but have been asked to approach the problem in a different way. I need to prove that every solution of f(x)=0 mod p^2 is given in the form x=a0+a1*p, where a0 is a solution of f(x)=0 mod p and a1 is a solution of f'(a0)*a1+f(a0)/p=0 mod p.

If I call a solution x0, then I have f(x0)=0 mod p^2, and clearly f(x0)=0 mod p as well.. Also, x0=a0+a1*p, so x0=a0 mod p. I know I can factor out a root of f so that f-f(a0)=(x-a0)*g, where g is another polynomial. Now, f'=(x-a0)'*g+(x-a0)*g'=g+(x-a0)*g'.

From here, I have f'(x0)=g(x0)+(x0-a0)*g'(x0). Since x0=a0 mod p, f'(x0)=f'(a0) mod p and f'(x0)=g(x0) mod p, so f'(a0)=g(x0) mod p.

Thinking back to the original formula I want, I see how I can get part of it. From f(x0)=0 mod p^2 I have f(xo)/p=0 mod p and thus f(a0)/p=0 mod p. What I am having trouble with is the other part. I need f'(a0)*a1=0 mod p, and so it's enough to have g(x0)*a1=0 mod p. And that's where I'm stuck. Any suggestions?