Editorial for Phương trình đồng dư tuyến tính một ẩn
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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\).
Comments