Intersecting two graphs of modulo functions with fractional coefficients

Question

I'm currently working on something for audio programming and in order to avoid a long post i will boil the problem down to a mathematical one. I have one function of the form:

(x + c) mod m, where -m < c < m, c element of Z, m element of N

And another function of the form:

(ax + d) mod m, where d element of Z, a element of Q

So we are talking about the modulo of linear functions of x. As most of you know, when you plot these kind of functions you will see repeating ramps. And i don't have a proof, but i assume that as long these functions are not parallel there always will be an intersection at some point. And i am trying to find the first intersection with x > 0.

Ive tried to solve it like this.

x + c ≡ (ax + d) mod m
x + c = k*m + ax + d, with k an integer
x - ax = k*m + d - c
x(1 - a) = k*m + d - c
x = k*m + d - c / (1 - a)

Now i just have to select the k that leads to the first positive x.

I've read this on wikipedia:

p(a) ≡ p(b) (mod n), for any polynomial p(x) with integer coefficients (compatibility with polynomial evaluation)

And thats why I'm a little bit apprehensive. Because im using non integer coefficients. Ive checked the extended euclids algorithm, but that leads to for example 28/11 mod 10 = 8, but that is not what i want. I want 28/10 mod 10 = 2.5454545454545, which is 28/10. And when i use wolfram alpha i get conflicting results. But what i thought maybe my method works for what i want. Because all i want is to find the intersection of the graphs and not necessarily follow the definitions of modulo arithmetic.

Since im not the best at math and i keep getting confused, i have to ask some of you guys this. So my most important question is firstly, is this correct? Secondly are there some things i need to watch out for?

Im not asking you to do the work for me, but if there is an obvious solution that some of you find easy to find, i'd like to ask this next question. Is there some way to calculate k in such a way that it always leads to the first x > 0, without checking the values of any of the values?

I apologize for not using the formatting, i just entered the forum and i didn't have time today to figure it out.

Answer 1

• if $a < 1$, x = (d - c - m*Int((d - c)/m))/(1 - a)
• if $a > 1$, x = (c - d - m*Int((c - d)/m))/(a - 1)

Here I am assuming that Int(x) is always the greatest integer $\le x$. If the function you have rounds towards $0$ instead, some changes will be needed.