Solving polynomial congruences modulo a prime power


by randommacuser
Tags: congruences, modulo, polynomial, power, prime, solving
randommacuser
randommacuser is offline
#1
Apr29-06, 11:35 PM
P: 25
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?
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered

Register to reply

Related Discussions
Solving quadratic congruences Calculus & Beyond Homework 1
Group isomorphism and Polynomial ring modulo ideal Linear & Abstract Algebra 4
Quadratic congruences with prime modulus Linear & Abstract Algebra 9
binomial coefficient modulo a prime Linear & Abstract Algebra 1
Solving linear congruences General Math 1