Quickest way to find smallest positive integer solution to $ax\equiv b\mod m$

Question

Let $I(a,b,m)$ be the smallest postive integer solution $x$ to the modular equation $$ax\equiv b\mod m.$$ What is the quickest way to find $I(a,b,m)$ for given integers $a,b,m$?

I know how to find it with the generalized euclidean algorithm, but is that the quickest way? Also, are there any curious properties of $I(a,b,m)$ like efficient bounds or identities?

I would be surprised if there were anything more efficient than Euclid, unless you have restrictions on $a, b, m$. — Old John, Dec 31 '12 at 22:56
You might want to review, if you hadn't already, Method of least absolute remainders and also review Algorithm Efficiency Comparison. You might also want to review HAC - Section 14.4. Regards — Amzoti, Dec 31 '12 at 23:21

score 2 · Answer 1 · answered Dec 31 '12 at 22:50

2

Euclid is pretty quick, and I don't know a quicker way.

answered Dec 31 '12 at 22:50

Gerry Myerson

179,216

2

When I was a freshman I invented a search algorithm, which is a general problem solving algorithm. It works in $O(1)$ but it has a rather high failure rate. It's called Lazy Search (or in the general case, Lazy Solve). Pick a random possible value, if it's the correct one return it; otherwise go and have a beer. I think this is a quicker algorithm than Euclid's! – Asaf Karagila Dec 31 '12 at 23:06

Quickest way to find smallest positive integer solution to $ax\equiv b\mod m$

1 Answers1