【数论】中国剩余定理

初探(


早有耳闻这个定理,今天集中研究了一下……

原出处是孙子算经的一道题,翻译过来就是:

** x%3==2&&x%5==3&&x%7==2,求x**


首先先要引入取模运算的性质:

(a1+a2+…+an)%b=[(a1%b)+(a2%b)+…+(an%b)]%b

推论:

a%b=c => (a%k*b)%b=c


再来看这道题,

设x=n1+n2+n3;n1%3=2,n2%5=3,n3%7=2;

由推论,如果n2%3=0,则(n1+n2)%3=2;同理,如果n3%3=0,(n1+n2+n3)%3=2

于是原方程:

(n1+n2+n3)%3=2,n2,n3%3=0;

(n1+n2+n3)%5=3,n1,n3%5=0;

(n1+n2+n3)%7=2,n1,n2%7=0;

于是,

x=n1+n2+n3,(n1%3=2,n1%5=0,n1%7=0)

(n2%5=3,n2%1=0,n2%7=0)

(n3%7=2,n3%3=0,n1%5=0)

这样,分别求出n1,n2,n3,,它们的和就是方程的一个解了。(但不一定是最小解)要求最小只需将和mod3,5,7的最小公倍数,即可求出。