The theorem is sometimes called Sunzi's theorem.
Teorema ini juga dikenal sebagai teorema Sunzi.
Both names of the theorem refer to its earliest known statement that appeared in Sunzi Suanjing, a Chinese manuscript written during the 3rd to 5th century CE.
Kedua nama dari teorema ini merujuk kepada pernyataan yang pertama kali muncul dalam Sunzi Suanjing, sebuah manuskrip Tiongkok yang ditulis pada abad ke-3 hingga abad ke-5 Masehi.
This first statement was restricted to the following example:
Pernyataan pertama ini terbatas pada contoh berikut:
In this example, the remainder is 23.
Dalam contoh ini, sisa pembagiannya ialah 23 .
Moreover, this remainder is the only possible positive value of n that is less than 105.
Lebih lanjut, sisa pembagian ini merupakan satu-satunya nilai positif n yang kurang dari 105 .
The Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers.
Teorema sisa Tiongkok banyak digunakan untuk perhitungan bilangan bulat yang besar, sebab teorema ini memungkinkan untuk mengganti perhitungan yang diketahui batas dari ukuran hasilnya dengan beberapa perhitungan serupa pada bilangan-bilangan bulat yang kecil.
The Chinese remainder theorem (expressed in terms of congruences) is true over every principal ideal domain.
Teorema sisa Tiongkok (saat diekspresikan menggunakan kekongruenan) juga berlaku pada setiap daerah ideal utama.
The earliest known statement of the problem appears in the 5th-century book Sunzi Suanjing by the Chinese mathematician Sunzi: There are certain things whose number is unknown.
Pernyataan dari masalah ini muncul pertama kali dalam buku abad ke-5 Sunzi Suanjing karya matematikawan Tiongkok Sunzi.
Sunzi's work would not be considered a theorem by modern standards; it only gives one particular problem, without showing how to solve it, much less any proof about the general case or a general algorithm for solving it.
Berapa banyak benda tersebut? Hasil Sunzi tidak akan dianggap sebagai teorema menurut standar modern, sebab Sunzi hanya memberikan satu masalah spesifik tanpa menunjukkan cara menyelesaikannya maupun bukti dari kasus umum atau algoritma umum untuk menyelesaikan masalah tersebut.
Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century) and appear in Fibonacci's Liber Abaci (1202).
Kasus khusus dari teorema sisa Tiongkok juga diketahui oleh Brahmagupta (abad ke-7) dan muncul pada karya Fibonacci tahun 1202, Liber Abaci.
The result was later generalized with a complete solution called Da-yan-shu (大衍術) in Qin Jiushao's 1247 Mathematical Treatise in Nine Sections which was translated into English in early 19th century by British missionary Alexander Wylie.
Hasil tersebut kemudian diperumum menjadi solusi utuh yang disebut Da-yan-shu (大衍術code: zh is deprecated ) dalam karya Qin Jiushao tahun 1247, Risalah Matematika dalam Sembilan Bab yang kemudian diterjemahkan ke dalam bahasa Inggris pada awal abad ke-19 oleh misionaris asal Britania Raya, Alexander Wylie.
The notion of congruences was first introduced and used by Carl Friedrich Gauss in his Disquisitiones Arithmeticae of 1801.
Gagasan mengenai kekongruenan pertama kali diperkenalkan dan digunakan oleh Carl Friedrich Gauss dalam karya tahun 1801 miliknya, Disquisitiones Arithmeticae.
This may be much faster than the direct computation if N and the number of operations are large.
Proses ini mungkin saja jauh lebih cepat dibandingkan perhitungan langsung, jika nilai N dan banyaknya operasi cukup besar.
The existence and the uniqueness of the solution may be proven independently.
Kewujudan dan ketunggalan penyelesaian dapat dibuktikan secara terpisah.
The map x mod N ↦ ( x mod n 1 , … , x mod n k ) }\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})} maps congruence classes modulo N to sequences of congruence classes modulo ni.
Perhatikan bahwa pemetaan f ( x mod N )( x mod n 1 , x mod n 2 , x mod n 3 , … , x mod n k ) })=\left(x{\bmod {n}}_{1},\,x{\bmod {n}}_{2},\,x{\bmod {n}}_{3},\,\ldots ,\,x{\bmod {n}}_{k}\right)} memetakan kelas-kelas kekongruenan modulo N ke barisan kelas-kelas kekongruenan modulo n i } .
x ≡ a 2 ( mod n 2 ) , x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}} where n 1 } and n 2 } are coprime.
Diberikan sistem kekongruenan linier x ≡ a 1 ( mod n 1 ) x ≡ a 2 ( mod n 2 ) x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\end{aligned}}} dengan n 1 } koprima dengan n 2 } .
Consider a sequence of congruence equations: x ≡ a 1 ( mod n 1 ) ⋮ x ≡ a k ( mod n k ) , x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}} where the n i } are pairwise coprime.
x ≡ a 3 ( mod n 3 ) … x ≡ a k ( mod n k ) x&\equiv a_{1,\,2}{\pmod {n_{1}\cdot n_{2}}}\\x&\equiv a_{3}{\pmod {n_{3}}}\\&\ldots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}} Penyelesaian sistemnya akan diperoleh dengan melakukan iterasi serupa yang berulang sebanyak k − 2 kali.
However, such a direct construction involves more computation with large numbers, which makes it less efficient and less used.
Namun, konstruksi langsung semacam ini akan melibatkan perhitungan yang lebih rumit dengan bilangan besar, yang membuat metode ini kurang efisien serta jarang digunakan.
Nevertheless, Lagrange interpolation is a special case of this construction, applied to polynomials instead of integers.
Walaupun demikian, interpolasi Lagrange merupakan kasus khusus dari konstruksi ini, yang diterapkan pada polinomial alih-alih bilangan bulat.
Let N iN / n iN/n_{i}} be the product of all moduli but one.
Misalkan N iN n i{\tfrac {N}{n_{i}}}} menyatakan darab dari semua moduli selain n i } .
As the n i } are pairwise coprime, N i } and n i } are coprime.
Oleh karena setiap n i } koprima pasang demi pasang, maka N i } akan koprima dengan n i } .
In fact, as N j } is a multiple of n i } for i ≠ j , we have x ≡ a i M i N i ≡ a i ( 1 − m i n i )
Diketahui bahwa n i } koprima dengan n j } untuk setiap 1 ≤ i < j ≤ k , maka N juga merupakan faktor dari x − y , sehingga x dan y akan kongruen dalam modulo N .
Consider a system of congruences: x ≡ a 1 ( mod n 1 ) ⋮ x ≡ a k ( mod n k ) , x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\\\end{aligned}}} where the n i } are pairwise coprime, and let Nn 1 n 2 ⋯ n k .
x ≡ a 3 ( mod n 3 ) … x ≡ a k ( mod n k ) x&\equiv a_{1,\,2}{\pmod {n_{1}\cdot n_{2}}}\\x&\equiv a_{3}{\pmod {n_{3}}}\\&\ldots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}} Penyelesaian sistemnya akan diperoleh dengan melakukan iterasi serupa yang berulang sebanyak k − 2 kali.
This implies that the solution belongs to the arithmetic progression a 1 , a 1 + n 1 , a 1 + 2 n 1 , … ,a_{1}+n_{1},a_{1}+2n_{1},\ldots } By testing the values of these numbers modulo n 2 , ,} one eventually finds a solution x 2 } of the two first congruences.
Himpunan penyelesaian dari dua kekongruenan pertama ini ialah himpunan semua bilangan bulat x yang memenuhi x ≡ a 1 , 2 ( mod n 1 ⋅ n 2 ) {\pmod {n_{1}\cdot n_{2}}}} Oleh karena n 1 ⋅ n 2 \cdot n_{2}} koprima dengan setiap n i } lainnya, maka sistem kekongruenannya tereduksi menjadi k − 1 kekongruenan simultan, yaitu x ≡ a 1 , 2 ( mod n 1 ⋅ n 2 )
The system of simultaneous congruences x ≡ a 1 ( mod n 1 ) ⋮ x ≡ a k ( mod n k ) , x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}} has a solution if and only if gcd ( n i , n j ) ,n_{j})} divides a i − a j -a_{j}} whenever i ≠ j .
x ≡ a 3 ( mod n 3 ) … x ≡ a k ( mod n k ) x&\equiv a_{1,\,2}{\pmod {n_{1}\cdot n_{2}}}\\x&\equiv a_{3}{\pmod {n_{3}}}\\&\ldots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}} Penyelesaian sistemnya akan diperoleh dengan melakukan iterasi serupa yang berulang sebanyak k − 2 kali.
x ≡ b ( mod n ) , x&\equiv a{\pmod {m}}\\x&\equiv b{\pmod {n}},\end{aligned}}} If a ≡ b ( mod g ) }} , then this system has a unique solution modulo Mm n / g .
x ≡ a 3 ( mod n 3 ) … x ≡ a k ( mod n k ) x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\x&\equiv a_{3}{\pmod {n_{3}}}\\&\ldots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}} dengan FPB ⁡ ( a i , a j )
Covering system Hasse principle Residue number system Dauben, Joseph W. (2007), "Chapter 3: Chinese Mathematics", in Katz, Victor J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India and Islam : A Sourcebook, Princeton University Press, pp.
Sistem pelingkup Prinsip Hasse Sistem bilangan residu Dauben, Joseph W. (2007), Katz, Victor J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India and Islam :
187–384, ISBN 978-0-691-11485-9 Dence, Joseph B.; Dence, Thomas P. (1999), Elements of the Theory of Numbers, Academic Press, ISBN 9780122091308 Duchet, Pierre (1995), "Hypergraphs", in Graham, R. L.; Grötschel, M.; Lovász, L. (eds.), Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp.
187–384, ISBN 978-0-691-11485-9 Dence, Joseph B.; Dence, Thomas P. (1999), Elements of the Theory of Numbers [Elemen Teori Bilangan] (dalam bahasa Inggris), Academic Press, ISBN 9780122091308 Duchet, Pierre (1995).
London ; New York: Springer.
New York: Springer.
402–403, ISBN 0-387-95419-8 Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0201-57889-8 Sengupta, Ambar N. (2012), Representing Finite Groups, A Semisimple Introduction, Springer, ISBN 978-1-4614-1232-8 Bourbaki, N. (1989), Algebra I, Springer, ISBN 3-540-64243-9 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7.
[Teori Bilangan Elementer beserta Penerapannya] (dalam bahasa Inggris) (Edisi ke-3), Addison-Wesley, ISBN 978-0201-57889-8 Sengupta, Ambar N. (2012), Representing Finite Groups, A Semisimple Introduction [Merepresentasikan Grup Hingga, Pengantar Semisederhana] (dalam bahasa Inggris), Springer, ISBN 978-1-4614-1232-8 Bourbaki, N. (1989), Algebra I (dalam bahasa Inggris), Springer, ISBN 3-540-64243-9 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms [Pengantar Algoritma] (dalam bahasa Inggris)
The Chinese remainder theorem, pp.
Lihat Bagian 31.5: Teorema sisa Tiongkok, hlm.
Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography, World Scientific Publishing, pp.
Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography [Teorema Sisa Tiongkok: Penerapan pada Komputasi, Pengkodean, Kriptografi] (dalam bahasa Inggris), World Scientific Publishing, hlm.
1–213, ISBN 981-02-2827-9 Hungerford, Thomas W. (1974), Algebra, Graduate Texts in Mathematics, Vol. 73, Springer-Verlag, pp.
1–213, ISBN 981-02-2827-9 Hungerford, Thomas W. (1974), Algebra [Aljabar], Graduate Texts in Mathematics, Vol. 73 (dalam bahasa Inggris), Springer-Verlag, hlm.
Full text of the Sun-tzu Suan-ching (Chinese) – Chinese Text Project
(Inggris) Full text of the Sun-tzu Suan-ching (Chinese) – Chinese Text Project (Inggris)