主题
Search

中国剩余定理

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

设 r 和 s 是 正整数，它们是互质的，且设 a 和 b 是任意两个整数。则存在一个整数 N 使得

N=a (mod r)
(1)

且

N=b (mod s).
(2)

此外，N 模 rs 是唯一确定的。一个等价的表述是，如果 (r,s)=1，则模 r 和 s 的每一对剩余类对应于模 rs 的一个简单剩余类。

中国剩余定理在 Wolfram 语言 中实现为ChineseRemainder[{a1, a2, ...}{m1, m2, ...}]。中国剩余定理也可以使用以下方式间接实现Reduce在带有域规范Integers.

该定理也可以推广如下。给定一组联立同余式

x=a_i (mod m_i)
(3)

对于 i=1, ..., r 且其中 m_i 是两两互质的，这组同余式的解是

x=a_1b_1M/(m_1)+...+a_rb_rM/(m_r) (mod M),
(4)

其中

M=m_1m_2...m_r
(5)

且 b_i 由以下公式确定

b_iM/(m_i)=1 (mod m_i).
(6)

另请参阅

同余, 同余方程, 线性同余方程

使用 Wolfram|Alpha 探索

参考文献

Flannery, S. 和 Flannery, D. In Code: A Mathematical Journey. London: Profile Books, 页 123-125, 2000.Ireland, K. 和 Rosen, M. "The Chinese Remainder Theorem." §3.4 in A Classical Introduction to Modern Number Theory, 2nd ed. New York: Springer-Verlag, 页 34-38, 1990.Séroul, R. "The Chinese Remainder Theorem." §2.6 in Programming for Mathematicians. Berlin: Springer-Verlag, 页 12-14, 2000.Uspensky, J. V. 和 Heaslet, M. A. Elementary Number Theory. New York: McGraw-Hill, 页 189-191, 1939.Wagon, S. "The Chinese Remainder Theorem." §8.4 in Mathematica in Action. New York: W. H. Freeman, 页 260-263, 1991.

请引用为

Weisstein, Eric W. “中国剩余定理。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ChineseRemainderTheorem.html

主题分类