扩展欧几里得算法与中国剩余定理

在《孙子算经》中有这样一个问题:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

这个问题说的是,有一件物品,我们不知道它的数量。但是,如果三个三个数,最后会剩下两个;如果五个五个数,最后会剩下三个;如果七个七个数,最后会剩下两个。问这个东西的数量是多少?

实际上,这个问题在现在我们可以将其转化为一个同余方程组:

 \left\{ \begin{aligned} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{aligned} \right.

中国剩余定理告诉了我们像这样的同余方程组的解。这个定理又称为孙子定理,通常被简写成CRT(Chinese Remainder Theorem)。

这篇文章将会从欧几里得算法开始讲起,之后过渡到扩展欧几里得算法解线性方程,最后介绍中国生于定理。

(more…)

Read More