一个数论定理和一个应用

中国剩余定理 | Chinese Remainder Theorem

• 设为两两互素的正整数， 为任意正整数，称为一次同余方程组。
• 记，对任意，记，为对模的逆。
• 同余方程组小于m的非负整数解唯一，为。

求逆 | 扩展欧几里得算法

欧几里得算法原理熟知，即。
扩展欧几里得算法可以求的，设为一组解。
代换：，设为代换后的一组解，则有，有。据此在求最大公约数的过程中，我们进行完毕后，可以逆推求出。
通解为。

应用