Solving polynomial congruences modulo a prime power

In summary: Simplifying, we get f'(a0)a1 + f(a0)/p = 0 (mod p), which is the equation we wanted to prove.In summary, to prove that every solution of f(x) = 0 (mod p^2) is given in the form x = a0 + a1p, 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), we used the fact that p^2 divides f(x) and its derivative f'(x), and then manipulated the equations
  • #1
randommacuser
24
0
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?
 
Physics news on Phys.org
  • #2


Hi there,

There are a few steps you can take to solve this problem. Firstly, let's rewrite the original statement as f(x) = 0 (mod p^2). This means that f(x) is congruent to 0 modulo p^2, or in other words, p^2 divides f(x). We can also write this as f(x) = p^2q(x), where q(x) is some polynomial.

Now let's consider the derivative of f(x), denoted as f'(x). Using the product rule, we can write f'(x) = 2p*q(x) + p^2q'(x). Since p is a prime number, we can divide both sides by p to get f'(x)/p = 2q(x) + pq'(x).

Next, let's look at the original equation again, f(x) = 0 (mod p^2). This means that p^2 divides f(x), so we can write f(x) = p^2q(x) = 0 (mod p). This also means that p divides q(x), so we can write q(x) = pr(x) for some polynomial r(x). Substituting this into our previous equation for f'(x)/p, we get f'(x)/p = 2pr(x) + p^2r'(x).

Now, let's consider the equation you are trying to prove: x = a0 + a1p, 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). We can rewrite this as a0 = x - a1p and f(a0)/p = -f'(a0)a1 (mod p).

Substituting x = a0 + a1p into our original equation f(x) = p^2q(x), we get f(a0 + a1p) = p^2q(a0 + a1p). Expanding this, we get f(a0) + f'(a0)a1p = p^2(q(a0) + q'(a0)a1).

Now, using our previous equations for f'(x)/p and f(a0)/p, we can rewrite this as -f'(a0)a1 + f(a0)/
 

What is a polynomial congruence modulo a prime power?

A polynomial congruence modulo a prime power is an equation of the form P(x) ≡ 0 (mod pn), where P(x) is a polynomial, n is a positive integer, and p is a prime number.

What is the difference between solving a polynomial congruence modulo a prime and modulo a prime power?

The difference lies in the range of possible solutions. When solving modulo a prime, there are only p possible solutions, while solving modulo a prime power allows for pn solutions.

What methods can be used to solve polynomial congruences modulo a prime power?

There are several methods that can be used, including Hensel's lemma, lifting the root, and the Chinese remainder theorem.

How do I know if a solution to a polynomial congruence modulo a prime power is unique?

If the polynomial P(x) is irreducible modulo p, then the solution is unique. Otherwise, there may be multiple solutions.

Are there any real-life applications of solving polynomial congruences modulo a prime power?

Yes, this concept is used in cryptography, specifically in the RSA algorithm for secure communication.

Similar threads

  • Calculus and Beyond Homework Help
Replies
12
Views
948
  • Calculus and Beyond Homework Help
2
Replies
61
Views
3K
  • Calculus and Beyond Homework Help
Replies
30
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
271
  • Calculus and Beyond Homework Help
Replies
1
Views
670
  • Calculus and Beyond Homework Help
Replies
4
Views
928
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
979
Back
Top