中国剩余定理（CRT）

中国剩余定理概述

定理内容阐述

中国剩余定理（Chinese Remainder Theorem, CRT）是源自中国古代用于解决一次同余方程组的数学方法，属于数论领域中的核心理论之一，亦被称作孙子定理。

一般解决该定理实际问题所具备的前置知识：

快速乘法、扩展欧几里得算法以及逆元计算是数论中常见的几种运算方法，广泛应用于密码学和算法设计等领域。

使用条件分析

通常情况下，要求mi之间两两互质。然而，在某些特殊情形下，并不强制执行这一条件，本文对此类情况不予探讨。

从题目入手

• 首先通过一个简单的例题，可以帮助我们初步理解中国剩余定理的求解过程，随后将对算法的具体步骤进行详细阐述。
  • 在古代数学著作《孙子算经》中记载了一个著名的问题：“现有若干物品，不知其数量，若以3为单位计数则余2，以5为单位计数则余3，以7为单位计数则余2，问物品总数是多少？”这一问题被后人称为“孙子问题”，其普遍的解决方法在国际上被命名为“中国剩余定理”。
    1. 确定三个关键数值：从3与5的公倍数中寻找能被7整除后余1的最小正整数15；从3与7的公倍数中寻找能被5整除后余1的最小正整数21；再从5与7的公倍数中寻找能被3整除后余1的最小正整数70。
    2. 将15乘以2（其中2是最终结果除以7所得的余数），将21