File Exchange

image thumbnail

Chinese reminder theorem

version 1.1.0.0 (107 KB) by Su Dongcai
just for fun

1 Download

Updated 02 Dec 2011

View License

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.

Cite As

Su Dongcai (2020). Chinese reminder theorem (https://www.mathworks.com/matlabcentral/fileexchange/34013-chinese-reminder-theorem), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (2)

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.

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.

Updates

1.1.0.0

supply the "program_guild.pdf" document to explain the motivation and key ideas of the program.

MATLAB Release Compatibility
Created with R14
Compatible with any release
Platform Compatibility
Windows macOS Linux
Tags Add Tags