Từ cách chứng minh định lý về công thức nghiệm phương trình đồng dư tuyến tính một ẩn trên, ta có thuật toán tìm nghiệm như sau:

• Tìm \(d = UCLN(|a|, m)\) theo thuật toán Euclid mở rộng, ta có: \(d = |a|.s + m.t\). Nếu \(a < 0\) thì ta thay \(s\) bằng \(–s\). Vì vậy ta có: \(d = a.s + m.t\).
• Nếu \(d\) không là ước của \(b\) thì phương trình vô nghiệm.
• Nếu \(d\) là ước của \(b\) thì phương trình có đúng \(d\) nghiệm không đồng dư theo \(modun\ m\) là: \(x=s.b/d+m/d.k\) với \(k = 0, 1, …, d-1\).

Chú ý rằng công thức nghiệm nguyên không âm nhỏ nhất là: \(x=((s.b/d+m/d.k)\%m+m)\%m\), với \(k = 0, 1, …, d-1\).