# finding lowest number which solves modulo arithmetic equation

I'm having a some trouble trying to find the best solution.

Given $i,b,m \in \mathbb N$ how do I find the smallest nonnegative integer $n$ that satisfies the equation $$i + bn \equiv 0 \mod m$$

Any help would be appreciated.

• Are you aware of the chinese remainder theorem, or the euclidean algorithm? – flawr Jan 15 '16 at 23:48
• You want $b\times n\equiv i\bmod m$. I think the most efficient solution would be to find solutions modulo each prime power $p^{\alpha}$ with $p^{\alpha}|| m$ and then find all possible solutions via the chinese remainder theorem. – Jorge Fernández-Hidalgo Jan 15 '16 at 23:50

You can solve for $n$ if and only if $gcd(b,m)=1$. In that case you can find $r,s$ such that $1 = rb+sm$ via euclidean algorithm. Then
$$1 \equiv rb \mod m$$ which implies $$b^{-1} \equiv r \mod m$$
Then you can just pick the least positive $n$ satisfying $$n \equiv b^{-1}(-i) \equiv -ri \mod m$$