中国剩余定理学习笔记

发布于 2019-06-30  29 次阅读


前置知识

  • 逆元相关知识

  • 费马小定理

img

模线性同余方程组

考虑方程组

img

满足img两两互质。求𝑥

中国鸭子定理

如果一个东西长得像鸭子,叫得像鸭子,走路也像鸭子,那它就是鸭子。——阮行止

img (废话)

构造

img

这个问题看起来搅和在一起。那么我们尝试分开构造。

img

那么如何构造一个img,使得

img img

这就是著名的中国剩余定理(CRT)

img img


Cause this is the life. Living is do or die.