Chinese Remainder Theorem
Calculator for the Chinese Remainder Theorem
In number theory, the Chinese remainder theorem states: if you know the remainders and divisors of dividing a whole number by several whole numbers, the divide of these whole numbers can be determined unambiguously. The condition is that the divisors are coprime in pairs.
Coprime means that there is no natural number other than one that divides both numbers.
To calculate, enter a series of divisors and remainders. The number of values in both lists must be the same. Then click the 'Calculate' button.
The data can be entered as a series of numbers, separated by semicolons or spaces, or as a list (one value per line).
|
Examples:
1st example
Input: Divisor = {3, 4, 5}, remainder = {2, 3, 1}
Result: 11
11 is the smallest possible dividend, because:
(1) 11 / \( 3 \) = 3 remainder \( 2 \).
(2) 11 / \( 4 \) = 2 remainder \( 3 \).
(3) 11 / \( 5 \) = 2 remainder \( 1 \).
2nd example
Input: Divisor = {5, 7}, remainder = {1, 3}
Result: 31
31 is the smallest possible dividend, because:
(1) 31 / \( 5 \) = 6 remainder \( 1 \).
(2) 31 / \( 7 \) = 4 remainder \( 3 \).
3rd Example
Input: Divisor = {13, 11, 7}, remainder = {12, 10, 6}
Result: 1000
1000 is the smallest possible dividend, because:
(1) 1000 / \( 13 \) = 76 remainder \( 12 \).
(2) 1000 / \( 11 \) = 90 remainder \( 10 \).
(3) 1000 / \(\ 7 \) = 142 remainder \( 6 \).
|
|