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

Solving Congruences

  1. Oct 11, 2008 #1
    if we knew how to solve [tex] f(x)= 0 mod (p^{l-1}) [/tex] (1)

    could we solve then [tex] f(x)= 0 mod (p^{l}) [/tex] for integer 'l'

    the idea is, if it were easy to solve [tex] f(x)= 0 mod (p) [/tex] then we could easily find a solution to (1) but i do not know how to do it.
     
  2. jcsd
  3. Oct 13, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    It's not even clear that
    [tex]f(x)\equiv0\pmod{p^l}[/tex]
    has solutions, let alone that we can easily find them.
     
  4. Oct 13, 2008 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    http://en.wikipedia.org/wiki/Hensel_Lifting

    But don't just immediately click on that link! Think about the problem first. Suppose you knew that f(x) had exactly one root modulo p. (Let's say a is that root) Then isn't there a very narrow range of possibilities for a root of f(x) modulo p^2?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?