CODEWITHSUNDEEP
matlabmodulochinese-remainder-theorem
Jey
Jey

Reputation: 61

Modulo and remainder (Chinese remainder theorem) in MATLAB

How do I find the least possible value in Matlab, given the modulo values and its remainder values in an array? for example:

A=[ 23 90 56 36] %# the modulo values
B=[  1  3 37 21] %# the remainder values

which leads to the answer 93; which is the least possible value.

EDIT:

Here is my code but it only seems to display the last value of the remainder array as the least value:

z = input('z=');
r = input('r=');
c = 0;
m = max(z);
[x, y] = find(z == m);
r = r(y);
f = find(z);
q = max(f);
p = z(1:q);
n = m * c + r;
if (mod(n, p) == r)
    c = c + 1;
end
fprintf('The lowest value is %0.f\n', n)

Upvotes: 5

Views: 3458

Answers (1)

Eitan T
Eitan T

Reputation: 32930

Okay, so your goal is to find the smallest x that satisfies B(i) = mod(x, A(i)) for each i.

This page contains a very simple (yet thorough) explanation of how to solve your set of equations using the Chinese Remainder Theorem. So, here's an implementation of the described method in MATLAB:

A = [23, 90];                                  %# Moduli
B = [1, 3];                                    %# Remainders

%# Find the smallest x that satisfies B(i) = mod(x, A(i)) for each i
AA = meshgrid(A);
assert(~sum(sum(gcd(AA, AA') - diag(A) > 1)))  %# Check that moduli are coprime
M = prod(AA' - diag(A - 1));
[G, U, V] = gcd(A, M);
x = mod(sum(B .* M .* V), prod(A))

x =
    93

You should note that this algorithm works only for moduli (the values of A) which are coprime!

In your example, they are not, so this will not work for your example (I've put an assert command to break the script if the moduli are not coprime). You should try to implement yourself the full solution for non-comprime moduli!

P.S
Also note that the gcd command uses Euclid's algorithm. If you are required to implement it yourself, this and this might serve you as good references.

Upvotes: 3

Related Questions