Chinese reminder theorem

just for fun

Description

Example:
Counting the number of nuts as shown in the photo:
count 3 by 3, reminder: 2
count 5 by 5, reminder: 3
count 7 by 7, reminder: 2
then the requested total number of nuts X can be calculated as follow command:
x = sunzTheorem([2, 3, 2], [3, 5, 7]);
The motivation and key ideas of the program is described in "program guild.pdf",
Note:
just throw out the designing ideas in a huristic way not for vigorous proof purpose.

• MATLAB release: MATLAB 7 (R14)

[Mike Sheppard]

As an alternative, using my "System of linear congruences" submission (#32856) you can solve more general congruence problems, with Chinese Remainder Theorem being a special case:

sunzTheorem([2 3 2], [3 5 7])
ans =
23

lincon([1 1 1], [2 3 2], [3 5 7])
ans =
23 105

Meaning 23+105*k for any integer k would also be a solution.

[Su Dongcai]

Mike Sheppard:
Thanks for broaden my eye side. The 'sunzTheorem' poster here has the computational complexity of O(N1+..Nm) using your notation, which means it can only handle small magnitude numbers.