龙源期刊网 http://www.qikan.com.cn
另解一次同余方程
作者：杨冬明
来源：《科教导刊》2009年第05期
摘要本文主要阐述几种一次同余方程的特殊解法:逐次减小模法、逐次减小系数法、形式分数法。
关键词一次同余方程特殊解法逐次减小形式分数 中图分类号:G633.6文献标识码:A
由王进明老师主编,人民教育出版社出版的《初等数论》,介绍了几种比较传统的一次同余方程的求解方法:同余变形法,“大衍求一术”,欧拉方法,组合数法等。在这里将介绍几种其他的较为简捷的解法。 由于一次同余方程 ax b (mod m)(1)
的解的存在性及其解的个数已经得到认识,我们这里只需要讨论当(a, m) = 1时的情况就可以了。
1 逐次减小模法
定理1设(a, m) = 1,则存在整数y,使得a|b +ym,且 x(mod m) 是方程(1)的解。
解因为(a, m) = 1,则不定方程az- my=b一定有解,即存在整数y,使得a|b + ym。直接将x(mod m)代入方程(1)中验算,有 axb+ymb (mod m)。
龙源期刊网 http://www.qikan.com.cn
于是结论成立。
定理1说明,求方程(1)的解可以转化为求方程 my-b (mod a)(2)
的解,这有两个方便之处:一是将一个对于大模m的同余方程转化为一个对于小模a的同余方程,因此有可能通过对模a的完全剩余系进行逐个验证,以求出方程(2)和(1)的解;二是对于方程(2)继续使用定理1,则又可继续转化成一个更小的模的同余方程,再依次递推可得原一次同余方程的解。
例1解同余方程 19x3 (mod 53) 解先解同余方程 53y3 (mod 19), 15y16 (mod 19) 解同余方程 19z 16 (mod 15), 4z 14 (mod 15) 解同余方程 15r14 (mod 4), 3r 2 (mod 4)
得到r 2 (mod 4),因此方程4z 14 (mod 15)的解是 z = 11 (mod 15)。
方程15y 16 (mod 19)的解是 y= 15 (mod 19)。
最后得到方程19x 3 (mod 53)的解是
龙源期刊网 http://www.qikan.com.cn
x= 42 (mod 53)。
2 逐次减小系数法
定理2设a > 0, (a, m) = 1,是m对模a的最小非负剩余且(, m) = 1,则同余方程 x -b(mod m) (3) 等价于同余方程(1)。
证明设x是(1)的解,则由m =a得到 (mod m),
即x是同余方程(3)的解。但是由已知条件可知同余方程(1)与(3)都有且只有一个解。所以这两个同余方程等价。
利用定理2,可以将同余方程(1)逐次转化成未知数的系数更小一些的同余方程,从而易于求解。当然在转化过程中为了保证每次的(, m) = 1,此方法最好在模m为质数时使用。 例2解同余方程22x 23 (mod 37)。 解由定理2,依次得到
22x23 (mod 37) 15x23�?14 (mod 37) 7x 14�?9 (mod 37) 2x9�?29 (mod 37) x 29�?8 33 (mod 37)。
3 形式分数法
定义1:当(a, m) = 1时,若ab c (mod m),则记b(mod,称为形式分数。