What is the best known algorithm to solve linear congruences of the form below? $$a x + b \equiv 0 \space (n)$$

And what is the time complexity of it?

  • 3
    $\begingroup$ I think it is the same as the complexity of computing GCD. You can use the euclidean algorithm, but IIRC it is open if there is a better algorithm. $\endgroup$ – Kaveh Aug 3 '11 at 15:25
  • 5
    $\begingroup$ What does “ax+b≡(n)” mean? Is it the same as “ax+b≡0 (mod n)”? $\endgroup$ – Tsuyoshi Ito Aug 3 '11 at 22:56

Your Answer

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

Browse other questions tagged or ask your own question.