Back مبرهنة الباقي الصينية Arabic Teorema xinès del residu Catalan Čínská věta o zbytcích Czech Chinesischer Restsatz German Κινεζικό Θεώρημα Υπολοίπων Greek Chinese remainder theorem English Ĉina restteoremo Esperanto Teorema chino del resto Spanish Hondarraren txinatar teorema Basque قضیه باقیمانده چینی Persian
The chinese remainder theorem is a theorem from number theory. It is about congruence. The original form was:
- How many soldiers are there in Han Xin's army? – If you let them parade in rows of 3 soldiers, two soldiers will be left. If you let them parade in rows of 5, 3 will be left, and in rows of 7, 2 will be left.
The theorem says that there will be a solution to this question if there's no common factor between the row sizes. Using the original example, that is that no number divides both 3 and 7, both 3 and 5, nor both 5 and 7 (except, of course, 1). They're all coprime.
The Chinese remainder theorem is used in cryptography. For example, for the RSA algorithm.