初探(
早有耳闻这个定理,今天集中研究了一下……
原出处是孙子算经的一道题,翻译过来就是:
** 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的最小公倍数,即可求出。