合同一次同余式PPT课件

合同一次同余式PPT课件§5.3合同一次同余式本文档后面有精心整理的常用PPT编辑图标，以提高工作效率§5.3.1合同及其性质设m是任意非0整数。a被m整除时，我们就说a合同于0模m，记为：a0(modm)一般来说，若a-b被m整除，则我们说a合同于b模m：ab(modm)一个数为m整除，当且仅当此数为-m整除。所以，若未指定m而一般地讨论模m合同时，我们总假定m是正整数。§5.3.1合同及其性质设a=q1m+r1，0≤r1

§5.3合同一次同余式本文档后面有精心整理的常用 ppt 编辑图标，以提高工作效率§5.3.1合同及其性质设m是任意非0整数。a被m整除时，我们就说a合同于0模m，记为：a0(modm)一般来说，若a-b被m整除，则我们说a合同于b模m：ab(modm)一个数为m整除，当且仅当此数为-m整除。所以，若未指定m而一般地讨论模m合同时，我们总假定m是正整数。§5.3.1合同及其性质设a=q1m+r1，0≤r1 题设有r，s使a-b=rm，c-d=sm。故(ac)-(bd)=(rs)m,因而acbd(modm)。其次，ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2bd+0+0+0(modm)=bd(modm)，故acbd(modm)。合同的基本性质性质5若ab(modm)，则akbk(modm)。其中k为整数。性质6若a+bc(modm)，则ac-b(modm)。性质7若ab(modm)，则acbc(modm)。性质8若ab(modm)，则anbn(modm)，n0。合同的基本性质性质9若c0而acbc(modmc)，则ab(modm)。证明：由题设有q使ac-bc=qmc，于是a-b=qm，因而ab(modm)。性质10若c和m互质，则由acbc(modm)可以推出ab(modm)。证明：ac=bc(modm) 表示m|(a-b)c，但c和m互质，所以有m|(a-b)，于是ab(modm)。合同的基本性质性质11若acbc(modm)，且（c,m）=d，则ab(modm/d)证明：由acbc(modm)知，m|(a-b)c，而(c,m)=d，故m/d|(a-b)c/d。注意到（m/d,c/d）=1，从而得m/d|(a-b)，即ab(modm/d)。对于质数模p，则有和相等完全类似的消去律。合同的基本性质性质12若p为质数，c0(modp)，而acbc(modp)，则ab(modp)。证明：因为p是质数，c0(modp)就表示c和p互质，(c,p)=1，因而性质12不过是性质10的推论。合同的基本性质性质13设p(x)是整系数多项式，x和y是整数变量，则由xy(modm)可得p(x)p(y)(modm)。运用性质13，我们再看能被9整除数的数码特征。设N=an10n+an-110n-1+…+a110+a0为一整数，因为101(mod9)，由性质13得Nan1n+an-11n-1+…+a1+a0(mod9)即。于是9|N当且仅当9|§5.3.2剩余类一次同余式模m合同既然是一种等价关系，就可以把所有整数按照模m合同的关系分为等价类，每一个等价类称为模m的一个剩余类。同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。因为以m去除任意整数，可能得到的余数恰有0，1，…，m-1，这m个数，所以模m共有m个剩余类，§5.3.2剩余类一次同余式从每个剩余类中取出一个数作为代表，这样便可得到m个数，比方r1,r2,…,rm说是作成一个完全剩余系，任意整数模m恰好合同于此完全剩余系中的一个数。例如，0，1，…，m-1便是这样一个完全剩余系。又如，模3，三个数0，1，2作成一个完全剩余系，-1，0，1也作成一个完全剩余系。模2，两个数0，1作成一个完全剩余系，0代表所有偶数，1代表所有奇数。同余式含有整数变量的合同式，称为合同方程或同余式。axb(modm)这种形式的合同式称为一次同余式；类似地，a2x2+a1xb(modm)称为二次同余式。同余式求解一次同余式实际上是解ax-b=my这样的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？定理5.3.1若a和m互质，b任意，则模m恰有一个数x使axb(modm)。证明：存在性。因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(modm)。取x=sb，则sb所在的剩余类中的数皆是解。唯一性。所谓模m只有一个这样的x，意思是说在模m合同的意义下，解是唯一的。即若axb(modm)，ayb(modm)，则xy(modm)。因为，由axb(modm)，ayb(modm)得axay(modm)，消去和m互质的a乃得xy(modm)。定理5.3.1推论设P为质数。若a0(modp)，b任意，则模p恰有一个数x使axb(modp)。定理5.3.2若(a,m)=d1，且d|b，则同余式axb(modm)无解。证明：反证法。若上式可解，则存在，使得ab(modm)。从而存在q，使得b=a-mq。因为(a,m)=d1，故d|(a-mq)，从而d|b，矛盾。定理5.3.3若(a,m)=d1，且d|b，则同余式axb(modm)…………………(1)有d个解，分别为,+m/d,+2m/d,…,+(d-1)m/d……(2)其中是同余式(a/d)xb/d(modm/d)…………(3)的解。定理5.3.3证明：由性质11和性质9知,(1)的解是(3)的解，(3)的解也是(1)的解。因为(a,m)=d，所以(a/d,m/d)=1。由定理5.3.1知，(3)在模m/d下有唯一解，设为，不妨设0m/d。因为+km/d恰是所在的模m/d剩余类的全部元素，k=0,1,2,…，故(3)的解作为数都可以表示成+km/d的形式。于是(1)的解都是+km/d形式的数，k=0,1,2,…。定理5.3.3下面证明(2)式是(1)的d个不同解。因为0m/d，故0(2)中每一个式子m，且互不相同，所以它们之间关于模m互不同余，即(2)为(1)的d个不同解。再考虑(1)只有(2)这d个不同解。即若数+lm/d是(1)的解，则关于模m，+lm/d必同余(2)中d个数之一。因为0，1，…，d-1为关于模d的完全剩余系，故存在i，0id-1，使得li(modd)。由m/d0和性质9，两边和模同乘m/d得，(l/d)m(i/d)m(modm)，故+lm/d+im/d(modm)。证毕。求解一次合同方程的方法我们以解合同式103x57(mod211)为例.方法一:定理5.3.1告诉我们若a和m互质，b任意，则模m恰有一个数x使axb(modm)。该定理证明存在性的过程即告诉了我们一种求解方法：因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(modm)。取x=sb，则sb所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的a与m的最大公因数1表示为a和m的倍数和的形式：1=as+mt，然后取x=sb，即可。求解一次合同方程的方法解：由于103与211互质，我们先将103与211的最大公因数1表示为它们的倍数和的形式。使用辗转相除方法逐次得商及余数并计算Sk，Tk如下表所示： k012345rk53210qk220113Sk01202141Tk12414384求解一次合同方程的方法因此，1=（-1）3×41×211+（-1）4×84×103。由此知，S=（-1）4×84，所以x=sb=84×57=4788=21×23-65-65(mod211)。求解一次合同方程的方法方法二:就是利用合同的性质，使x的系数变成1，即得到解。对于上例解合同式103x57(mod211)。由于211=103×2+5，由合同的性质7有2×103x2×57(mod211)。因为211x0(mod211)，所以由合同的性质5知，211x-2×103x0-2×57(mod211)。即5x-114(mod211)97(mod211)。求解一次合同方程的方法由于211=42×5+1由合同的性质7有42×5x42×97211×19+6565(mod211)。由合同的性质5知，211x-42×5x0-65(mod211)。即x-65(mod211)。对于一些例子，使用这种方法是比较快的。比如，解合同式4x1(mod15)。因为116(mod15)，所以4x1164×4(mod15)，因为4与15互质，由合同的性质10知，合同式两边可以消去4，得到x4(mod15)。求解一次合同方程的方法方法三:利用Fermat-Euler定理（教材中定理5.4.7），见下例。例5.2.18解合同式7x5(mod10)。解：因为7和10互质，由Fermat-Euler定理有7(10)1(mod10)，因(10)=4，所以741(mod10)。由合同的性质7，在7x5(mod10)两边乘以73，有73×7x73×5(mod10)，而73×7x=74xx(mod10)，73×5=72×7×5（-1）×7×55(mod10)，所以所给合同式的解为x5(mod10)。后面附件PPT常用图标，方便大家提高工作效率生活图标元素生活图标元素医疗图标元素

                    本文档为【合同 一次同余式PPT课件】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：￥18.0 已有0 人下载

立即下载

合同 一次同余式PPT课件

你可能还喜欢

合同一次同余式PPT课件