Smallest multiple of a number that gives a specific remainder modulo another number Given three positive integers $a, b$ and $c$, my task to find the smallest positive integer $k$ such that $(k * a) \mod b = c$.
I can obviously try values of $k$ from $1$ and higher, until I find the right value. My question is, can this computation be done in $O(1)$ time? That is, is there a direct way to calculate the smallest integer value of $k$ such that $k*a - c$ is a multiple of $b$?
Using Congruent Modulo Notation, one can rewrite the problem as:

$$a*k \equiv c\pmod{b}$$
This is a simple linear congruence, that can be solved using the Extended Euclidean Algorithm

There are other algorithms, but this one is the simplest.

According to Wikipedia:


  In big O notation, this algorithm runs in time $O(\log(m)^2)$, assuming
  $|a| &lt; m$, and is considered to be very fast and generally more
  efficient than its alternative, exponentiation.


Where $m$ is the letter $b$ in your example