1. Limited time only! Sign up for a free 30min personal 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!

Solving equations with mod

  1. Jan 17, 2013 #1
    Solving equations with "mod"

    1. The problem statement, all variables and given/known data
    I have a homework problem. I'm in computer science, however one of my programs requires me to solve this equation. I'm afraid it's beyond my expertise.

    (a * x) mod b = 1

    This needs to be rearranged in the form of x = ...
    Due to the existence of "mod", I get confused.

    Please don't solve it for me. I'm just looking for a little nudge to help me get over this hump.


    2. Relevant equations
    See above.


    3. The attempt at a solution
    My main goal solving this was to try and get rid of that "mod". Thinking about it logically, if x mod y = 0, that means that x / y = Z, where Z is some integer. I also believe it means there exist values of x and y such that all integer values of Z would exist.

    Base equation
    (a * x) mod b = 1

    Subtracting 1 from both sides
    ((a * x) - 1) mod b = 0

    Converting to division
    ((a * x) - 1) / b = Z

    Solve like normal
    x = (Z*b + 1) / a

    Now the problem is, the Z is throwing me off. Do I just choose a value? It would make sense for remainders that there are multiple values of x that keep the equation in balance. Due to this being programming, x can be my only unknown. Am I on the right track?
     
  2. jcsd
  3. Jan 17, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Re: Solving equations with "mod"

    There are many websites covering basic operations of modular arithmetic.

    Something you can consider first: if x0 is a solution, what about x0+b?

    You would have to choose a value such that x is an integer. No, that does not work (unless you want to guess - possible, but inefficient), but there are methods to solve the original equation for x, for example a simplified version of the extended euclidean algorithm.
     
  4. Jan 18, 2013 #3
    Re: Solving equations with "mod"

    I've looked up plenty of sites, but all of the things are far, far above my comprehension. I guess what I'm (potentially stupidly) expecting is something like:

    "a mod b = 1" --> "(a + 1) / b = 0", or:
    "x / y" --> "x * (1/y)"

    Something I can use to isolate x such that I may continue my coding. I need to emphasize, even though math is related to my field, I'm not a math person. I don't understand all of the complicated things I see on Wikipedia and other sites like this:

    http://upload.wikimedia.org/math/3/0/8/308f894eed1a6fe2f4921fbc747db4e8.png

    I've done plenty of research, but I'm not finding anything simple like above. Perhaps it's not as simple as I think? Perhaps there's just not that much coverage. In the end, I'm not sure.

    ~

    Edit: I'm starting to see what you were saying by x, versus x+b. That would reinforce my logic that there must be multiple solutions, which doesn't make sense in my scenario. Perhaps the assignment is broken... I will look into this further.
     
    Last edited: Jan 18, 2013
  5. Jan 18, 2013 #4

    rcgldr

    User Avatar
    Homework Helper

    Re: Solving equations with "mod"

    You have the correct answer. Z can be any integer (negative, zero, positive). x is the only unknown, but it has multiple values.

    If this was finite field math modulo b, then a, x, and Z would be limited to the range {0, ..., b-1}, and there would be only one solution for x (and Z) for given a and b. There are algorithms to solve this, but I'm not sure if there is a formula.
     
    Last edited: Jan 18, 2013
  6. Jan 18, 2013 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Solving equations with "mod"

    There are fundamentally two ways to solve a such an equation.

    1) If in the equation ax= 1 (mod b) b is relatively small, you can just do "trial and error": to solve 3x= 1 (mod 5), note that if
    a) x= 0, 3(0)= 0, not 1
    b) x= 1, 3(1)= 3, not 1
    c) x= 2, 3(2)= 6= 5+ 1 and so is 1 (mod 5). x= 2 is the answer. Of course, if you are not just considering the "base values" between 0 and 5, x= 2+ 5n for any integer n is the general answer.

    2) If b is rather large, you can use the "Euclidean division algorithm". To solve 7x= 1 (mod 32), Write it as 7x= 1+ 32n or 7x- 32n= 1. Now
    7 divides into 32 four times with remainder 4: 32- 4(7)= 4.
    4 divides into 7 once with remainder 3: 7- 4= 3.
    3 divides into 4 once with remainder 1: 4- 3= 1.

    Replace the "3" in 4- 3= 1 with 7- 4 from the previous equation: 4- (7- 4)= 2(4)- 7= 1.
    Replace the "4" in 2(4)- 7= 1 with 32- 4(7) from the previous equation: 2(32- 4(7))- 7= 2(32)- 9(7)= 1. We can also write this as (-9)(7)- (-2)(32)= 1 and comparing that with the original equation, 7x- 32n= 1 we see that x= -9 and n= -2 is a solution. But it is easy to see that x=-9+ 32k, n= -2+ 7k is also a solution for any integer k:
    7(-9+ 32k)- 32(-2+ 7k)= -63+ 7(32)k+ 64+ (32)(7)k= -63+ 64= 1 because the 7(32)k terms cancel.

    So x= -9+ 32k is the general solution or, taking k= 1, x= -9+ 32= 23 is the solution between 0 and 32.

    Check: 7(23)= 161= 5(32)+ 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving equations with mod
  1. Mod of Sine Equation (Replies: 2)

  2. Solving an equation (Replies: 3)

  3. Solving an equation (Replies: 4)

Loading...