# 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$?

• You need modular inverse of k mod b which is O(log k log b) computation. – Shashwat Kumar Oct 11 '17 at 8:41

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| < 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

• Thanks for the response. Do you mean O(log(m)^2) for the running time ? – Pankaj Bhambhani Oct 12 '17 at 2:41
• Yes, thanks. I have fixed that in my answer. – klaus Oct 12 '17 at 22:16