Chinese Remainder Theorem (CRT)

Pada abad pertama, seorang matematikawan Tiongkok yang bernama Sun Tzu mengajukan pertanyaan sebagai berikut:

“Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7”.

Teorema Chinese Remainder berikut akan digunakan untuk menemukan solusi sistem kongruen linier seperti di atas:

Misalkan m₁, m₂, …, m_n adalah bilangan bulat positif sedemikian sehingga GCD(m_i, m_j) = 1 untuk i ¹ j. Maka sistem kongruen linier:

x = a_k (mod m_k)

mempunyai sebuah solusi unik dalam modulo m = m₁ . m₂ . … . m_n.