Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 27, 2007 #1


    User Avatar

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

    [tex] f(x)=0mod(p) [/tex]

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

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

    So we have 'modified' Newton method for solving Polynomial congruences. :Bigrin:
  2. jcsd
  3. Mar 28, 2007 #2


    User Avatar

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

    [tex] f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})=0mod(p) [/tex] (1)

    will work to solve the general congruence [tex] f(x)=0mod(p) [/tex] 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}
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook