Solving Equations With Modulos

[madness]

Are there general methods for solving equations of the form

a+bx = mod(c+dx, m),

where, in the notation I have made up here, mod is the modulo function which resets the argument to zero when it reaches m. I hope it's clear what I mean here.

 

[mfb]

Every solution of that equation will also satisfy 0 = mod(c-a+(d-b)x, m), or, in a more conventional notation, f=g x mod m where f=a-c and g=d-b. This is a simple modular equation, and general methods to find all solutions exist.
All solutions which satisfy 0<=a+bx<m are solutions to your initial equation.

 

[madness]

I don't quite follow. When you switch from my made up notation to the real notation (sorry about that), it looks like a completely new equation. Unless you moved terms to the other side, which I didn't think was allowed. I could get a better idea of the solution by considering:

mod(x,n) = x- n*floor(x/n)

so that for my equations:

a+bx = c+dx - m*floor((c+dx)/m)

But what are the general methods for finding the solutions here? I should be clear here that I'm considering x as a real number and not necessarily and integer here.

 

[mfb]

Unless you moved terms to the other side, which I didn't think was allowed.

It is.

0 = mod(c-a+(d-b)x, m)
switch notation
0 = c-a+(d-b)x mod m
add a-c (for mathematical details: you can do this as addition is a group in Z/nZ, and it works for non-integer values as well)
a-c = (d-b)x mod m

Note that "mod m" refers to the whole equation in mathematics. It is used differently in programming languages.

I should be clear here that I'm considering x as a real number and not necessarily and integer here.

No, this is not clear, and really unexpected in modular expressions. It is not a problem, however: it might change the general methods to solve f=gx mod m, but it does not change the other parts.

 

[madness]

It is.

0 = mod(c-a+(d-b)x, m)
switch notation
0 = c-a+(d-b)x mod m
add a-c (for mathematical details: you can do this as addition is a group in Z/nZ, and it works for non-integer values as well)
a-c = (d-b)x mod m

Addition is a group, but the addition operation follows the rule

add(x,y) = x+y-m*floor((x+y)/m),

which you didn't follow. Is this not the case?

No, this is not clear, and really unexpected in modular expressions. It is not a problem, however: it might change the general methods to solve f=gx mod m, but it does not change the other parts.

Well it should be pretty clear now that I've stated it explicitly. I'm working on a specific scientific problem and don't have the luxury of choosing all of the details of the problem.

 

[mfb]

Addition is a group, but the addition operation follows the rule

add(x,y) = x+y-m*floor((x+y)/m),

which you didn't follow. Is this not the case?

My steps follow the calculation mod m, the expression via division and floor is not useful here.

 

[madness]

Ok I'm starting to see where you're coming from now. However, I still don't know what these general methods you talk about are. Could you point me towards an explanation of the methods involved?

Edit: So x = f/g + k*m/g is the general solution for some integer k? Plus the constraint that 0<=a+bx<m.

 

[mfb]

Looks correct.