同余式 ax ≡ c(mod m) 的求解
2019-04-13 16:19发布
生成海报
【概述】
- 既然已经解决了 ax + by = c,不得不提的就是同余式 ax ≡ c(mod m) 的求解
- 先解释什么是同余式。对整数 a、b、m 来说,如果 m 整除 a-b ( 即 (a-b)%m = 0) ),那么就说 a 与 b 模 m 同余,对应的同余式为 a ≡ b(mod m),m称为同余式的模。
- 例如10与13模3同余,10也与1模3同余,它们分别记为10 ≡ 13(mod 3)、10 ≡ 1(mod 3)。
- 显然,每一个整数都各自与 [0, m)中唯一的整数同余。
- 此处要解决的就是同余式 ax ≡ c(mod m) 的求解。根据同余式的定义,有 (ax - c)%m = 0 成立,因此存在整数y,使得 ax - c = my 成立。移项并令 y = - y 后即得 ax + my = c。
【分析过程】
打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮