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

<p>And what is the time complexity of it?</p>

CC BY-SA 3.0
2011-08-03T15:25:53.410Z
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.
Kaveh
CC BY-SA 3.0
2011-08-03T22:56:29.247Z
What does “ax+b≡(n)” mean?  Is it the same as “ax+b≡0 (mod n)”?
Tsuyoshi Ito
<ds.algorithms><time-complexity><nt.number-theory>
Time complexity for solving linear congruences?
Johannes
# Time complexity for solving linear congruences?

(Asked by: username_0 on 2011-08-03)

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?

**Tags:** ds.algorithms, time-complexity, nt.number-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: What does “ax+b≡(n)” mean?  Is it the same as “ax+b≡0 (mod n)”?  

---

## 0 answers

