08.中国剩余定理

title: 08. 中国剩余定理 tags: zk basic chinese remainder theorem WTF zk教程第8讲：中国剩余定理 这一讲，我们将介绍剩余类和著名的中国剩余定理，它可以用来解同余方程组。 物不知数问题 中国南北朝（公元420年—589年）的《孙子算经》上记载着这样一道题，被称为“物不知数”问题，解出这道题的勇士可以得到孙子所持有的BTC（余额：0）。 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 翻译一下古文：有个未知数 $x$，除3余2，除5余3，除7余2，求 $x$。 其实这是一个求一元线性同余方程组的问题，即找到满足下列方程组的 $x$。 $$ x \equiv 2 \pmod{3} $$ $$ x \equiv 3 \pmod{5} $$ $$ x \equiv 2 \pmod{7} $$ 下面我们要介绍的中国剩余定理就是用来解决这一问题的。 剩余类 在第5讲中，我们简单了解了剩余类（residual class）/同余类的概念，现在我们需要更系统的介绍它。 剩余类是一种等价关系，用于将整数划分为同余的集合，定义如下...