Register to reply

Solving Equations With Modulos

by madness
Tags: equations, modulos, solving
Share this thread:
madness
#1
Dec31-12, 07:24 AM
P: 625
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
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
mfb
#2
Dec31-12, 10:37 AM
Mentor
P: 11,925
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
#3
Dec31-12, 10:59 AM
P: 625
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
#4
Dec31-12, 11:33 AM
Mentor
P: 11,925
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
#5
Dec31-12, 12:11 PM
P: 625
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
#6
Dec31-12, 12:14 PM
Mentor
P: 11,925
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
#7
Dec31-12, 12:30 PM
P: 625
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
#8
Dec31-12, 01:26 PM
Mentor
P: 11,925
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