Newton method and f(x)=0mod(p)

1. Mar 27, 2007

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:

2. Mar 28, 2007

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}