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

Modular math problem

  1. Jun 19, 2004 #1

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Given, A>0 and odd B>0, find C = f(A,B), satisfying :

    1 + BC == 0 (mod 2^A)
     
  2. jcsd
  3. Jun 19, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Euclid's Algorithm on B and 2**A will do it. sorry, my six key is buggered so i can't do powers in pseudotex.
     
  4. Jun 19, 2004 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    matt,

    I'm not sure I follow. You are talking about the GCD algorithm, right ?

    I don't see how this works. Can you show me how, on an example, say 2^A = 64, B = 15 ?
     
  5. Jun 19, 2004 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Recall that the extended Euclidean algorithm will give you two numbers, u and v, such that u * m + v * n = gcd(m, n)...
     
  6. Jun 19, 2004 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, I've used it to solve linear diophantine eqns...but don't see how it can be used here.
     
  7. Jun 20, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    B is odd, 2**A is a power of two, they are coprime.
     
  8. Jun 20, 2004 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Maybe it would help if I rewrite it as

    (-u) * m + gcd(m, n) = v * n

    ?
     
  9. Jun 20, 2004 #8

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Thanks,

    I never cease to amaze myself !
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Modular math problem
  1. Modular math problem (Replies: 7)

  2. New math problem book (Replies: 2)

Loading...