Geek asks and answers

Modulo and the remainder (Chinese remainder theorem) in MATLAB

How to find the smallest possible value in Matlab, given the modulo values ​​and its residual values ​​in the array? eg:

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

which leads to an answer 93; which is the smallest possible value.

EDIT:

Here is my code, but it only seems that the last value of the residual array is the smallest 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)
+5
source share
1 answer

So, your goal is to find the smallest xone that suits B(i) = mod(x, A(i))everyone i.

( ) , , . , 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

, ( A), coprime!

, ( assert, script, ). !

P.S
, gcd . , this this .

+3

More articles:


All Articles