欢迎来到天天文库
浏览记录
ID：47490093
大小：165.00 KB
页数：13页
时间：2020-01-12
《初等数论 第四章 同余式》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章同余式第四章同余式§1基本概念及一次同余式同余式的解法1、代入法（适用于模较小时）-13-第四章同余式2、公式法（适用于模较小时）3、变换系数法4、换模法-13-第四章同余式5、辗转相除法-13-第四章同余式§2孙子定理本节讨论同余式组的求解问题。-13-第四章同余式定理1之所以称为“孙子定理”，因为在我国古代的数学著作《孙子算经》（纪元前后）中已经提出了这种形式的问题，并且很好地解决了它。孙子定理在国外文献和教科书中均称为“中国剩余定理”，并且在代数学中被推广成非常一般的形式。《孙子算经》中
2、所提出的问题之一如下：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。用现在的记号，上述问题相当于求解同余式组。《孙子算经》中所用的方法可以列表如下：除数余数最小公倍数衍数乘率各总答数最小答数323×5×7=1055×7235×2×2140+63+30=233233-105×2=23537×3121×1×3723×5115×1×2程大位在《算法统宗》（1593）中将这一问题的算法总结成如下歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆半个月，除百零五便得知。推广为一
3、般的列表算法：-13-第四章同余式除数余数最小公倍数衍数乘率各总答数m1b1m=m1m2…mkM1M1’M1M1’b1m2b2M2M2’M2M2’b2……………mkbkMkMk’MkMk’bk-13-第四章同余式-13-第四章同余式§3质数模的同余式-13-第四章同余式质数模同余式的具体解法：1、简化同余式，一般考虑以下简化方法：(1)若f(x)的系数中有大于p的数，则可将其化到小于p；(2)若，则可用去除f(x)，则可得到一个次数较低的与原同余式等价的同余式；(3)若f(x)关于模p有一个或几个因
4、式，则也可将原同余式的次数降低；(4)若f(x)已知有一解或几解，则可析出因式将次数降低。2、将模的完全剩余系中的数逐一代入同余式，检验即可得解。-13-第四章同余式-13-第四章同余式§4高次同余式的解法-13-第四章同余式-13-第四章同余式-13-
此文档下载收益归作者所有
