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

Remodularization? help?

  1. Dec 16, 2004 #1
    i'm not sure if i understand this concept at all.
    for finding all the solutions (mod 45) of

    4x=7 (mod 45), we know that solutions exist, b/c the gcd (4, 45)=1 which divides 7.
    4x= [52,97,112,157] (mod 45*4)
    4x= 52 (mod 180) and 4x=112(mod 180).
    these reduce to x=13 (mod 45) and x=28 (mod 45) respectively.
    then x=13, 28 (mod 45)?

    i feel like i'm missing some important step or piece of the concept.
  2. jcsd
  3. Dec 16, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    There is certainly something you've not quite grasped. In particular you may not say that since

    a=b mod p


    a=b+rp mod ap

    this just is not going to help even if it were true, which it isn't guaranteed to be, though by some *fluke* it may give an answer.

    What you need to do is find the multiplicatice inverse of 4 modulo 45.

    since 4*11=-1 mod 45

    you should be able to solve it from there.
  4. Dec 16, 2004 #3
    i tried it your way, finding the multiplicative inverse, and got x=13.

    Then I tried my method with 4x= 0 (mod 45) to get x=0, which works with your method as well. i don't know where i got the formula. but thank you. i'd rather do the problem right than do it by fluke.
  5. Dec 17, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You've just introduced new answers - a little like squaring. I've not chekced to see if your method must produce the correct answer, but it vertainly must produce incorrect ones, and it isn't nec. clear whioh of them is or insn't going to be correct without substituting back.

    To find multiplicative inverses one only needs to use eulcid's algorithm.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook