求解“余数问题”的算法研究

求解"余数问题"可归结为一次同余式组x≡ri(mod pi)或一次不定方程组x=pixi+ri的求解.当方程的个数n与模pi(i=1,2,…,n)较大时,用同余式理论和孙子定理求解的过程非常繁琐.为此,运用试算分析法和辗转相除法,给出了求解上述问题的两种通用的计算机算法和程序.通过实践证明,该算法具有计算步骤简便,求解灵活快速,通用性强等优点.

A Study on the Algorithm of Solving the Problem of Remainders

The paper gives out two kinds of algorithm to apply in the computer programming to answering the ″Problem of Remainders″.We can solve the problem by solving x≡ri(mod pi),the group of congruent formulae to first degree,or x=pixi+ri,the group of indeterminate equations to the first degree.When the amount of equations ″n″ and the value of model ″pi″(i=1,2,…,n) are larger,using the remainder formulae theory and the Chinese remainder theorem to solve the problem is very fussy and complicated.so applying the pilot calculation analytical method and successive division method,we can solve the above problem through two kinds of universal computer algorithm and program.Proved by practice,the algorithm is of simple and convenient calculating steps,flexible and swift solving,good commonality and other advantages.