一次同余式的解法探讨_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
一次同余式的解法探讨
&&《高等数学研究》杂志
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢　　表示关系的数学表达式，与等式相似。将等式中的等号“=”换成同余符号“≡”，必要时在式尾缀以(mod m) 注明模m（即除数），就是同余式。
　　含有的同余式叫做，通常要求整数解。同余式的定义　　如果两个正整数 a和 b之差能被 n整除，那么我们就说 a和 b对模n同余，记作：
　　a ≡b (mod n) 同余式的运算　　同余式运算类似于等式的运算，在等号两边可进行加减乘除的算术运算。如 a≡b (mod n) ，则有：
　　a + c ≡b + c (mod n)
　　a - c ≡b - c (mod n)
　　a ·c ≡b ·c (mod n)
　　但在应用除法运算时应特别注意，仅在除数与模互质时，才能去除同余式的两边，如：
　　a /c ≡b / c (mod n) ，必须c 与 n要互质，就c 与 n须没有公因数。
&|&相关影像
互动百科的词条（含所附图片）系由网友上传，如果涉嫌侵权，请与客服联系，我们将按照法律之相关规定及时进行处理。未经许可，禁止商业网站等复制、抓取本站内容；合理使用者，请注明来源于。
登录后使用互动百科的服务，将会得到个性化的提示和帮助，还有机会和专业认证智愿者沟通。
此词条还可添加&
编辑次数：3次
参与编辑人数：3位
最近更新时间： 22:32:00
申请可获得以下专属权利：
贡献光荣榜& 登录/注册
您可以从小木虫客户端获取VIP通行码，无需登录继续浏览
STEP1扫描左侧二维码，下载新版客户端
（已安装客户端用户请无视）
STEP2登录页面下方获取VIP通行码
VIP通行码:
小木虫,学术科研互动社区,为中国学术科研免费提供动力
违规贴举报删除请联系客服电话： 邮箱：（全天候） 或者 QQ:
广告投放与宣传请联系 李想 QQ：
QQ：&&邮箱：
Copyright & 2001-, All Rights Reserved. 小木虫 版权所有
浏览器进程
打开微信扫一扫
随时随地聊科研导读：一次同余式与一次同余式组的解的讨论，并在Euler定理及孙子定理的基础上,详细地讨论了一次同余式、一次同余式组的是否，则给出了求解方法.一次同余式和一次同余式组的相关知识是学习数论过程中必须要掌握的，关键词:一次同余式;一次同余式组;孙子定理;Euler定理，《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，秦九韶在他的《数书九章》不仅给出了一次同余式的解，而且用“大衍求一术”数学方一次同余式与一次同余式组的解的讨论
这篇文章先给出有关同余式、同余式的解的概念，并在Euler定理及孙子定理的基础上,详细地讨论了一次同余式、一次同余式组的是否有解的条件，若有解，则给出了求解方法. 一次同余式和一次同余式组的相关知识是学习数论过程中必须要掌握的知识，它在数学领域内有着及其广泛的应用。 关键词: 一次同余式; 一次同余式组;孙子定理;Euler定理
1引言 南北朝时期的数学著作《孙子算经》中“物不知数”是这样的“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”解法和答案用算式表示为：70?2?21?3?15?2?105?2?23，即得到适合题意的最小正整数是23。 《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但真正从完整的计算程序和理论上解决这个问题的是南宋时期的数学家秦九韶。秦九韶在他的《数书九章》不仅给出了一次同余式的解，而且用“大衍求一术”数学方法给出了一次同余式组的最小正整数解。 2基本定义和定理 定义2.1
设f(x)?anxn?an?1xn?1???a1x?a0是整系数多项式，m是一正整数，称 f(x)?0(modm)
(1) 是模m的同余式，若an??0(modm)，则n叫做同余式(1)的次数。 定义2.2
若a是整数，且使得f(a)?0(modm)成立，则x?a(modm)叫做同余式(1)的一个解。即把适合(1)式且对模m相互同余的一切数叫做同余式(1)的一个解。 定义2.3
欧拉函数?(a)是定义在正整数上的函数，它在正整数a上的值等于序列0,1,2,?,a?1中与a互质的数的个数。 定理2.1(Euler)
设m?1，(a,m)?1，则a?(m)?1(modm)。 证明
设r1,r2,?,r?(m)是模数m的一组简化剩余系，则由定理（若(a,m)?1,x通过m的简化剩余系，则ax通过模m的简化剩余系.） 可知ar1,ar2,?,ar?(m)也是模m的一组简化剩余系，故
(ar1)(ar2)?(ar?(m))?r1r2?r?(m)(modm) 即
a?(m)r1r2?r?(m)?r1r2?r?(m)(modm)
?ri,m??1,i?1,2,?,?(m). )?1故
(r1r2??rm(,)m
根据性质（若a?a1d,b?b1d,(d,m)?1,则a1?b1(modm).） 以及 (~)和(~~)得
a?(m)?1(modm). 定理2.2（孙子定理）
设m1,m2,?,mk是k个两两互素的正整数, m?m1m2?mk,m?miMi(i?1,2,?,k), 则同余式组 x?b1(modm1),x?b2(modm2),?,x?bk(modmk)
(2) 有唯一关于模m的解 ?M2b2???Mk?Mkbk(modm),
(3) x?M1?M1b1?M2其中Mi?Mi?1(modmi)(i?1,2,?,k). 证明
由于(mi,mj)?1,i?j，即得(Mi,mi)?1.由定理3.1知对每一Mi，有一Mi?存在，使Mi?Mi?1(modmi).由m?miMi，知mj|Mi,i?j. 故
?M?Mbjjkj?Mi?Mibi?bi(modmi),i?1,2,?,k. 即(3)为(2)的解。 j?1若x1,x2是适合(2)式的任意两个整数，则 x1?x2(modmi)(i?1,2,?,k). 又由于(mi,mj)?1,i?j，于是x1?x2(modm)，故(2)仅有解(3)。 3一次同余式 定理3.1
若?a,m??d?1,d|b,则ax?b(modm)无解。 证明
若有解，即可得ax?b?modm?.而d|a,于是有0?b(modd).而这与d|b,相矛盾，所以同余式无解。 定理3.2
设(a,m)?1,m?0，则同余式 ax?b(modm)
(4) ?(m?)1(modm ).有唯一解
由于1,2,?,m组成一组模数m的完全剩余系，(a,m)?1，故a,2a,?,ma组成模数m的一组完全剩余系，故其中恰有一个数设为aj，适合 aj?b(modm),x?j(modm) 也就是(4)的唯一解。 方法一 由定理2.1知 a?(m)x?ba?(m)?1?modm?.。 从而x?ba?(m)?1?modm?为所求的解。 即原命题成立。 方法二
因为?a,m??1.由定理(若?a,b??d由最大公因数性质可知必有二数s,t使as?bt?1.)
知必有二数s，t使as?mt?1即as?1?modm?. ，故由asx?bs?modm?知同余式(4)的解为 x?bs?modm?.
设(a,m)?d,m?0，同余式(4)有解的充分必要条件是d|b，且恰有d个解。 ?am?证明
若(4)有解，则由d|a,d|m 推出d|b。如果d|b，则?,??1， ?dd?故同余式 ab?m?x??mod? dd?d?
① 有一组解，即同余式(4)有一组解。 若整数c适合(4)，c也适合同余式①；反之，若c适合同余式①，c也适合同m余式(4)。设t适合①，则①有唯一解
x?t(mod，) dm即全体整数t?k?,k?0,?1,?2,?, d对模数m来说，恰可选出d个互不同余的整数 mmmt,t?,t?2?,?,t?(d?1).
② dddm这是因为对于t?k，设k?qd?r,0?r?d代入得 dmmmmt?k??t?(qd?r)?t?r?qm?t?r(modm). ddddmm又若 0?e?d,0?f?d,t?e?t?f?modm?，则推出f?e.这就证明了(4)的dd任一解恰与②中的某一数模数m同余，而②中的d个数，又模数m两两互不同余，即知(4)恰有d个解。 一般地，我们有 定理3.4
设k?1，同余式
a1x1???akxk?b?0(modm)
(5) 有解的充分必要条件是
(6) ?|bk,m若条件(6)满足，则(5)的解数为mk?1?a1,?,ak,m?。 证明
现用归纳法来证明。由定理3.2知当k?1时结论显然成立。 设?a1,?,ak,m??d,?a1,?,ak?1,m??d1，则?d1,a1??d。 由定理 3.3知
akxk?b?0?mod1?
（） 有d个解 xk?t?modd1?，xk?t?d1d ?,xk?t?1?modd?1??modd1?，?modd1?，dd从而对模数m来说有d?m个解： d1 2 xk?t(modm),xk?t?d1(modm),?,xk?t?d1(m?1)(modm),d1???????????d1(d?1)(modm),?,ddmxk?t?1(d?1)?d1(?1)(modm)dd1xk?t? 对（）的一个解xk，设由归纳法假定， anxk?b?b1， d1a1x1???ak?1xk?1?b1d1?0(modm) 的解数为
mk?2(a1,?,ak?1,m)?mk?2d1， 故(5)的解数为mk?2d1?d?例1 m?mk?1d. d1解同余式 111x?75?mod321?. 解
因为?111,321??3,3|75,故同余式有解，且化为37x?25?mod107?. 故
x?.???8?9?9?mod1?0371114于是原同余式有三个解：x?99,206,313?mod321?. 例2 解同余式286x?121?mod341?. 解
因为?286,341??11,11|121,故同余式有解，且化为26x?11?mod31?. 11?20 .??4?mod?3126?5于是原同余式有三个解： 故
x?x?4,35,66,97,128,159,190,221,252,283,314?mod341?. 4一次同余式组
设m1,m2是两个正整数，同余式组 ??x?b1?modm1?
(7) ?x?bmodm?2?2??① 若?m1,m2?|b1?b2，则同余式组(7)无解。 ② 若?m1,m2?|b1?b2，则同余式组(7)有以?m1,m2?为模的一类剩余解。
①满足同余式x?b1?modm1?的数为
x?b1?m,t?t Z
⑴ 并且满足同余式 x?b2?modm2?， 则有 b1?m1t?b2?modm2? 即
m1t?b2?b?1modm?2
⑵ 由于?m1,m2?|b2?b1,所以同余式x?b2?modm2?无解，即同余式组无解。 ③ 若?m1,m2?|b1?b2，则可设 m1?m1?d,m2?m2?d,b2?b1?bd,?m1?,m2???1. 由⑵得
m1?t?bmodm2??
⑶ 因为??m1，m?2???m?d1，m?2??d?，故d?m1?，m2???1，所以⑶式有一个解。t?bmodm2? 从而⑵有d个解 t?b,b?m2?,?,b??d?1?m2??modm2? 将t?b??m2?,??Z代入⑴有 x?b1?m1?b??m2???b1?bm1??m1m2?. 又?mm1m21m2??d??m1,m2?
?x?b1?bm1?mod?m1,?m?2 由于b1,m1是给定的，而且b是唯一确定的，从而同余式组有唯一的解。
显然，若?m1,m2??1,则同余式组(7)恒有解。 例3 解同余式组???x?7?mod15???x?2?mod6?. 解
因为?6,15??3,3|7?2,故此同余式组无解。 例4 解同余式组???x?7?mod15???x?4?mod6?. 解
因为?15,6??3,3|7?4,故同余式组有解。 由第一个同余式得
x?7?15y ,代入第二式
7?15y??4mo?d 6,得
3y??3?mod?6 ,即
y?1?mod?2 ,将y?1?2z代入x?7?15y中，得 x?7?15?1?2z??22?30z. 即同余式组得解为x?22?mod30?. 下面把定理6推广到含任意个同余式的情形。先给出 命题1
设m1,m2,?,mk,(k?3)是任意k个正整数，则 ??m1,m2,?,ms?,ms?1?????ms?1,m1?,?ms?1,m2?,?,?ms?1,ms???,s?2,3,?,k?1.证明
对k应用数学归纳法。 当k?3时，即证：
4 设 包含总结汇报、考试资料、外语学习、人文社科、旅游景点、经管营销、专业文献、出国留学、资格考试、行业论文、IT计算机以及一次同余式与一次同余式组的解的讨论等内容。本文共2页
相关内容搜索}