MATLAB中的模和余数(中国余数定理)

Question

考虑到数组中的模数值及其余值,如何在Matlab中找到最小值？例如:

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

这导致了答案93; 这是最不可能的价值.

---

编辑:

这是我的代码,但它似乎只显示余数数组的最后一个值作为最小值:

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) 

Answer 1

好的，所以你的目标是找到x满足B(i) = mod(x, A(i))每个 的最小的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）！

在您的示例中，它们不是，因此这不适用于您的示例assert（如果模数不互质，我已经放置了一个命令来中断脚本）。您应该尝试自己实现非素模的完整解决方案！

PS
另请注意，该gcd命令使用Euclid 算法。如果您需要自己实现，这个和这个可能会为您提供很好的参考。