Register to reply

Solving polynomial congruences modulo a prime power

by randommacuser
Tags: congruences, modulo, polynomial, power, prime, solving
Share this thread:
randommacuser
#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
Security CTO to detail Android Fake ID flaw at Black Hat
Huge waves measured for first time in Arctic Ocean
Mysterious molecules in space

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