Solving Equations With Modulos

  • Context: Undergrad 
  • Thread starter Thread starter madness
  • Start date Start date
  • Tags Tags
    Solving equations
Click For Summary

Discussion Overview

The discussion revolves around solving equations of the form a + bx = mod(c + dx, m), focusing on the methods and implications of modular arithmetic. Participants explore the nature of solutions, the treatment of variables, and the application of modular operations in both theoretical and practical contexts.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant asks about general methods for solving equations involving modular arithmetic, specifically the form a + bx = mod(c + dx, m).
  • Another participant suggests that every solution can be expressed as 0 = mod(c - a + (d - b)x, m), indicating a transformation to a simpler modular equation.
  • A participant expresses confusion over the notation switch and questions the validity of moving terms across the equation, while also introducing a method for expressing the modulo operation in terms of real numbers.
  • There is a discussion about the validity of manipulating the equation and whether addition in modular arithmetic follows specific rules, with some participants asserting that it does.
  • One participant proposes a general solution format x = f/g + k*m/g, while also noting a constraint that 0 <= a + bx < m.

Areas of Agreement / Disagreement

Participants exhibit disagreement regarding the manipulation of terms in modular equations and the treatment of variables as real numbers versus integers. The discussion remains unresolved as participants have differing views on the methods and implications of their approaches.

Contextual Notes

Participants express uncertainty about the applicability of certain mathematical operations in the context of modular arithmetic, particularly when considering non-integer values. There are also unresolved questions about the general methods for finding solutions to the proposed equations.

madness
Messages
813
Reaction score
69
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.
 
Mathematics news on Phys.org
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.
 
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.
 
Last edited:
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.
 
mfb said:
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.
 
madness said:
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.
 
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.
 
Last edited:
Looks correct.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 16 ·
Replies
16
Views
5K
  • · Replies 11 ·
Replies
11
Views
3K
  • · Replies 13 ·
Replies
13
Views
3K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 7 ·
Replies
7
Views
4K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 6 ·
Replies
6
Views
3K