原书出处
Introduction to Algorithms, Fourth Edition
31 第31章 数论算法
n) (because ax′ = d (mod n)) = b (mod n), and thus x0 is a solution to ax = b (mod n). ▪
Theorem 31.24 Suppose that the equation ax = b (mod n) is solvable (that is, d | b, where d = gcd(a, n)) and that x0 is any solution to this equation. Then, this equation has exactly d distinct solutions, modulo n, given by xi = x0 + i(n/d) for i = 0, 1,
…, d – 1. Proof Because n/d > 0 and 0 ≤ i(n/d) < n for i = 0, 1, …, d – 1, the values x0,
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter031.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea