0
$\begingroup$

Given integers a, b, and c all <=n, is there an efficient algorithm to find an integer y such that a | c + b*y? One brute force approach will be to check for all y = 0 to n
and if there is a solution, there must be a solution within this range.
That will be O(n)

$\endgroup$
1
  • 2
    $\begingroup$ Note that this is a linear congruence. You have to solve $by\equiv -c (\text{mod } a)$. $\endgroup$
    – Nathaniel
    Oct 29 at 20:46
1
$\begingroup$

Yes. You are asking how to solve a linear congruence $by \equiv -c \pmod a$. The solution is to compute the modular inverse of $b$ modulo $a$ using the extended Euclidean algorithm, multiply both sides of the equation by that modular inverse, and then read off the solution. This can be done in $O(\log^2 n)$ time.

$\endgroup$

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.