Solving Equations With Modulos


by madness
Tags: equations, modulos, solving
madness
madness is offline
#1
Dec31-12, 07:24 AM
P: 606
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.
Phys.Org News Partner Mathematics news on Phys.org
Math modeling handbook now available
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
mfb
mfb is online now
#2
Dec31-12, 10:37 AM
Mentor
P: 10,854
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
madness is offline
#3
Dec31-12, 10:59 AM
P: 606
I dont 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
mfb is online now
#4
Dec31-12, 11:33 AM
Mentor
P: 10,854

Solving Equations With Modulos


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
madness is offline
#5
Dec31-12, 12:11 PM
P: 606
Quote Quote by mfb View Post
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
mfb is online now
#6
Dec31-12, 12:14 PM
Mentor
P: 10,854
Quote Quote by madness View Post
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
madness is offline
#7
Dec31-12, 12:30 PM
P: 606
Ok I'm starting to see where you're coming from now. However, I still dont 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
mfb is online now
#8
Dec31-12, 01:26 PM
Mentor
P: 10,854
Looks correct.


Register to reply

Related Discussions
Solving for variables using 3 different equations (simultaneous equations) Precalculus Mathematics Homework 1
Modulos one Calculus 0
modulos raised to phi Introductory Physics Homework 1
palindromes and modulos Introductory Physics Homework 6
reduced residue system mod 7 Linear & Abstract Algebra 16