3
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.