Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following little problem : let $a,b,u,v$ be four given integers with $\gcd(a,b)=1$. Now I would like to find the minimum of the linear congruence subsequence $\{ax \pmod b : u \le x \le v\}$. Of course, we have $0<u<v<b$ otherwise it is trivial.

I have some sort of algorithm but wonder if there have already been some work on such a problem ? some references ?

Thanks in advance, Eric

share|improve this question
Welcome to MSE! Please note the LaTeX formatting I did to your question, LaTeX being the language of choice to write mathematics here. –  Andreas Caranti Mar 2 '13 at 13:37
I wonder whether you can make it better than $O(v - u)$. –  Andreas Caranti Mar 2 '13 at 14:07
I have an algorithm which is log(b) worst case. It is a funny little thing but was wondering if some mathematical work out there that has different approaches or may be even better. And thanks for the LaTeX editing. Just discovered the site. Wasn't aware of the LaTeX possibility. –  Eric Andres Mar 2 '13 at 14:49
That'a interesting. I'm not aware of any work in this direction, but then I'm no expert at all. As to the editing, you're welcome, it's a community here. –  Andreas Caranti Mar 2 '13 at 15:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.