【剩余定理】怎么证明的?即辗转相除法
1个回答

某数除以A余M,除以B余N,除以C余P,(ABC组为除数,MNP组为余数,XYZ组为凑数所得.接触过奥数的朋友应该感到很亲切吧,余数就喜欢用这个…)则

1.求

B*C的X倍除以A余1 (对应除以A余M)

A*C的Y倍除以C余1 (对应除以B余N)

A*B的Z倍除以B余1 (对应除以C余P)

费时的地方在于XYZ要凑数得到

2.

B*C*X*M+A*C*Y*N+A*B*Z*P=符合条件的数

然后该数减去A、B、C的最小公倍数次直至得到的差小于最小公倍数,那么这个差就是符合条件的最小数

在公式2中注意与1中的对应关系可以使你更容易理解