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

How to 'undo' mod, or solve equation with a mod.?

  1. Jan 29, 2010 #1
    if we are given something of the form

    where we are given a and b ...how can x be solved for ?

    what if we are given a range for which x has to fall within?
    something like 0 <= lowerbound <= x <= upperbound


    I have thought about this a little while i came up with that
    with k a positive integer.. would generate all the possible solutions

    is this correct?
    can anyone guide me in right direction to solving this?
  2. jcsd
  3. Jan 29, 2010 #2
    What about negative numbers? Or 0? For k.

    You're definitely in the right direction.
  4. Jan 29, 2010 #3
    Why must x be greater than a?
  5. Jan 29, 2010 #4
    no no, i mean some other defined lowerbound and upperbound.

    for example, 0 to 1000000.. otherwise i assume there would be endless solutions.

    I guess in my case i want to exclude negatives from k (since my boundary is positive), and include 0.

    I read some more and I found this :
    So i guess I can say go from a=x(mod b) -> x = a(mod b)

    Is this correct?
    Last edited by a moderator: May 4, 2017
  6. Jan 30, 2010 #5
    1. a could be greater than b, so even if you want your x to be positive, k > 0 is too strict a condition.

    2. Sure, x = a (mod b ) iff a = x (mod b). Remember that by definition, x = a (mod b) <=> b | x-a.
  7. Jan 30, 2010 #6
    x = kb + a where kb + a > -1 is your general solution based upon your condition that x is not negative. Of course k could be any integer including even zero or a negative number for these conditions to be met.
    Last edited: Jan 30, 2010
  8. Jan 30, 2010 #7
    the actual problem I am trying to solve is a bit different .. but similar problem i think (?)
    okay, so with these problem settings below

    (U being some integer to represent x's maximum value)

    I can try to solve for x by setting up

    and the solutions are when both x and k are integers.

    ah i understand, since b wasn't specified to fall into any certain range :) , hm since we say now that it is always greater than x,

    (I think I can) assume that k >= 0.

    so is it right to think that there are 1 + FLOOR(b/U) solutions for x?
    Last edited: Jan 30, 2010
  9. Jan 31, 2010 #8
    Bear in mind that there could be no solutions at all. For example,
    [tex]x^2 \equiv 2 \pmod 4[/tex]
    has no solutions, since all squares modulo 4 are either 0 or 1.

    You can check this wikipedia entry,
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook