中国剩余定理

Chinese Remainder Theorem(CRT)

导入

1
物不知数」问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

出自孙子算经，问题大意为求一个整数，除以3余2，除以5余3，除以7余2.

定义

中国剩余定理，用来解决一元线性同余方程组(n为互质的正整数，为整数)

img

计算过程

  1. 先求所有模数的积n
  2. 再求m_i =