1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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}
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Newton method and f(x)=0mod(p)
  1. X² + y² = 1 (mod p) (Replies: 7)

  2. Calculate f(x)modg(x) (Replies: 1)