主題
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)

另請參閱

同餘, 同餘方程, 線性同餘方程

使用 探索

參考文獻

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. “中國剩餘定理。” 來自 Web 資源。 https://mathworld.tw/ChineseRemainderTheorem.html

主題分類