How Can Newton's Method Be Modified for Polynomial Congruences?

[tpm]

Let be the congruence equation with f(x) a Polynomial of grade k then:

f(x)=0mod(p)

then if we have as a first approximation f(x_{n+1})=0mod(p)

then using a linear interpolation: f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})=0mod(p) or x_{n+1}=(x_{n}+\frac{f(x_{n}}{f'(x_{n})})0mod(p/f'(x_{n})

So we have 'modified' Newton method for solving Polynomial congruences. :Bigrin:

 

[tpm]

I think in this case the mai question is if the linear interpolation solution

f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})=0mod(p) (1)

will work to solve the general congruence f(x)=0mod(p) for f(x) a POlynomial solving it by iterations using Newton method, where from (1) form an initial ansatz x_n we can get the next approximate value x_{n+1}