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

[rsala004]

if we are given something of the form

a = x mod b

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

x = b*k + a

with k a positive integer.. would generate all the possible solutions

is this correct?
can anyone guide me in right direction to solving this?

 

[Norman.Galois]

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?

What about negative numbers? Or 0? For k.

You're definitely in the right direction.

 

[ramsey2879]

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?

Why must x be greater than a?

 

[rsala004]

Why must x be greater than a?

no no, i mean some other defined lowerbound and upperbound.

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

---

What about negative numbers? Or 0? For k.

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 :

http://homepage.smc.edu/kennedy_john/MODULARRSA.PDF][/PLAIN]
Theorem 7:
If a = b(mod n), then b=a(mod n)

So i guess I can say go from a=x(mod b) -> x = a(mod b)

Is this correct?

 

[soarer]

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.

 

[ramsey2879]

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?

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.

 

[rsala004]

the actual problem I am trying to solve is a bit different .. but similar problem i think (?)
okay, so with these problem settings below

a = (x^2) mod b, 0 <= x < U < b

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

I can try to solve for x by setting up

x^2 = b*k + a

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

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.

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?

 

[dodo]

Bear in mind that there could be no solutions at all. For example,
$$x^2 \equiv 2 \pmod 4$$
has no solutions, since all squares modulo 4 are either 0 or 1.

You can check this wikipedia entry,
http://en.wikipedia.org/wiki/Quadratic_residue