离散数学(数论基础) |
您所在的位置:网站首页 › A和B互为质数A与B的最大公因数是 › 离散数学(数论基础) |
整除性 辗转相除
整除及其性质
定义5.1.1 :设a和b是任意整数,若存在整数c,使得a=bc,则称a是b的倍数,b是a的因数。或者称a被b整除,而b整除a。记为b|a。 注意: (1)任意整数整除0 ,特别0|0; 0=b·0;(c=0) 0=0·c(c可以是任意整数),但0不能整除任意非零整数。a=0·c(a≠0) (2)1和(-1)整除任意整数。 a=1·a;a=(-1)·(-a) 推论:b|a,(b\(\ne\) 0) 当且仅当a被b除(或者a除以b,或者b除a)的余数为0。 整除的基本性质 性质1 若a|b,b|c,则a|c (传递性) 性质2 若a|b,则a|bc (b|bc用传递性证明) 性质3 若a|b,a|c,则a|b\(\pm\)c。 性质4 若a整除b1,…,bn, 则a| \(\mathrm{\lambda}_1\mathrm{b}_1\)+…+ \(\mathrm{\lambda}_n\mathrm{b}_n\),其中\(\mathrm{\lambda}_{\mathrm{i}}\)为任意整数。 性质5 若在一等式中,除某项外,其余各项都是a的倍数,则此项也是a的倍数 性质6 若a|b,b|a,则b=\(\pm\)a 性质7 设a=qb+c,则a,b的公因数与b,c的公因数是完全相同的 定义5.1.2 若d是a的因数也是b的因数,则称d为a,b的公因数。 若d是a,b的公因数,而a,b的任意公因数整除d,则称d为a,b的最高公因数。a,b的最高公因数通常记为d=(a,b)。 例:8,12有公因数:±1, ±2, ±4, 其中, ±1|4, ±2|4, ±4|4,(注意正负)则4是8和12的最高公因数,记为4=(8, 12)。-4也是 问题:0和0的最高公因数是多少? 【答】:0 5.1.2 辗转相除定理5.1.2 :任意二整数a,b有最高公因数。 定理5.1.3:任意二整数a,b的最高公因数d可以表示为a,b的倍数和,即表为下面的形式:d=sa+tb 其中 s,t都是整数。 辗转相除法求最高公因式: 使用辗转相除法求两个数a,b的最高公因数并表示为它们的倍数和,需要使用的主要公式如下: \[\mathrm{S}_0=0,\mathrm{S}_1=1,\mathrm{T}_0=1,\mathrm{T}_1=\mathrm{q}_1 \\ \mathrm{S}_{\mathrm{k}}=\mathrm{q}_{\mathrm{k}}\mathrm{S}_{\mathrm{k}-1}+\mathrm{S}_{\mathrm{k}-2} \\ \mathrm{T}_{\mathrm{k}}=\mathrm{q}_{\mathrm{k}}\mathrm{T}_{\mathrm{k}-1}+\mathrm{T}_{\mathrm{k}-2} \\ \mathrm{d}=\left( -1 \right) ^{\mathrm{n}-1}\mathrm{S}_{\mathrm{n}}\mathrm{a}+\left( -1 \right) ^{\mathrm{n}}\mathrm{T}_{\mathrm{n}}\mathrm{b} \]![]() ![]() 定义5.2.1 : 若a,b除±1外无其它公因数,则称a和b互质。 结论: 1、a和b互质,必要而且只要a、b的最高公因数为1(通常只考虑+1)。 2、±1和任意整数(包括0)互质。 定理5.2.1 :a和b互质,当且仅当1可表示为a和b的倍数和形式,即存在整数s和t使1=sa+tb。 定理5.2.2:若a和b互质,而a|bc,则a|c。 定理5.2.3:若b和a1,a2,…,an都互质,则b和a1a2…an互质。 定理5.2.4:若m1,m2,…,mk两两互质而都整除a,则m1m2…mk|a。 ![]() 常用结论:\(2^{\mathrm{p}}\)-1和\(2^{\mathrm{q}}\)-1互质的充要条件是p和q互质。 ![]() 定义5.2.2:一个正整数,如果不等于1而且除了自己和1没有其它正因数,则称其为一个质数(也称为素数);否则称其为合数。 这样,正整数分为{1, 质数,合数} 结论: 1、质数p和a互质,必要而且只要p \(\nmid\) a 2、任意两个不同的质数互质 定理5.2.5 :设p为质数,若p整除a1a2…an,则p整除a1,a2,…,an之一。 定理5.2.6 (算术基本定理):任意正整数n(n\(\ne\) 1)恰有一法写成质数的乘积(不计因数乘积的顺序)。 推论1: 任意整数(\(\ne\) 0,\(\ne\) ±1)恰好有一法写成下面的形式:±\(\mathrm{p}_1\)…\(\mathrm{p}_k\),其中\(\mathrm{p}_1\),…,\(\mathrm{p}_k\)都是质数。 推论2: 任意整数(\(\ne\) 0,\(\ne\) ±1)恰好有一法写成下面的形式:±\({\mathrm{p}_1}^{\mathrm{r}_1}\)…\({\mathrm{p}_n}^{\mathrm{r}_n}\),其中\(\mathrm{p}_1\),…,\(\mathrm{p}_n\)是不同的质数,\(\mathrm{r}_1\),…,\(\mathrm{r}_n\)是正整数。 ![]() 定理5.2.7:质数无穷多。 合同 一次同余式 合同及其性质定义. 设a,b为二整数,m是任意非0整数。若 m|a-b,则称a合同于b 模m。记为:a\(\equiv\)b(mod m) 注意: (1)合同为整除的另一种表示法,故整除的性质在此可用。特别地,若b=0,则a$\equiv$0(mod m)表示的就是m|a。 (2)若m|a,则- m|a。所以,若未指定m而一般地讨论模m合同时,总假定m是正整数。 (3)a\(\equiv\)b(mod m) iff 以m除a和b所得的余数相同 合同的基本性质: 性质1: a\(\equiv\)a。 性质2: 若a\(\equiv\)b,则b\(\equiv\)a。 性质3: 若a\(\equiv\)b,b\(\equiv\)c,则a\(\equiv\)c。 故合同是一种等价关系。 每一个等价类称为模m的一个剩余类。 性质4: 若a\(\equiv\)b(mod m),c\(\equiv\)d(mod m),则a\(\pm\)c\(\equiv\)b\(\pm\)d(mod m),ac\(\equiv\)bd(mod m) 性质5: 若a\(\equiv\)b(mod m),则a\(\pm\)k\(\equiv\)b\(\pm\)k (mod m)。其中k为整数。 性质6: 若a+b\(\equiv\)c(mod m),则a\(\equiv\)c-b(mod m)。 性质7: 若a\(\equiv\)b(mod m),则ac\(\equiv\)bc(mod m)。 性质8: 若a\(\equiv\)b(mod m),则\(\\\mathrm{a}^{\mathrm{n}}\equiv \mathrm{b}^{\mathrm{n}}\)(mod m), n$\geqslant $0 性质9: 若c\(\ne\) 0而ac\(\equiv\) bc(mod mc),则a\(\equiv\) b(mod m)。 性质10: 若c和m互质,则由ac\(\equiv\)bc(mod m)可以推出a\(\equiv\)b(mod m)。 性质11: 若ac\(\equiv\)bc(mod m),且(c, m)=d, 则a\(\equiv\)b(mod m/d) 其实性质9和10是都性质11的特例,因为性质9里(c,m)=d=c,性质10里(c,m)=d=1 结论:若(c,m)=d,则(c/d , m/d)=1 对于质数模p(即模p为质数,如mod 3),则有与相等完全类似的消去律。 性质12: 若p为质数,c\(\not \equiv\) 0(mod p),(c,p互质),而ac\(\equiv\) bc(mod p),则a\(\equiv\) b(mod p)。 性质13: 设p(x)是整系数多项式,x和y是整数变量,则由x\(\equiv\)y(mod m)可得p(x) \(\equiv\)p(y) (mod m)。 ![]() ![]() ![]() 等价类、剩余类:模m合同既然是一种等价关系,就可以把所有整数按照模 m合同的关系分为等价类,每一个等价类称为模m的一个剩余类。 例如,整数集合Z,模3,得到: 余数为0: {…, -6, -3, 0, 3, 6, …} 余数为1: {…, -5, -2, 1, 4, 7, …} 余数为2: {…, -4, -1, 2, 5, 8, …} 1、同一个剩余类中的数互相合同,不同的剩余类中的数不互相合同。 2、因为以m去除任意整数,可能得到的余数恰有0,1,…,m-1,这m个数,所以模m共有m个剩余类。 3、从模m每个剩余类中任意取出一个数作为代表,得到m个数,比方r1, r2, …,rm,称这m个数作成一个完全剩余系。 例1: 0,1,…,m-1便是这样一个完全剩余系,称为模m 的非负最小完全剩余系。 任意整数模m恰好合同于此完全剩余系中的一个数。 例2: 模3,三个数0,1,2作成一个完全剩余系,-1,0,1也作成一个完全剩余系。 例3: 模2,两个数0,1作成一个完全剩余系,0代表所有偶数,1代表所有奇数. 同余式:含有整数变量的合同式,称为合同方程或同余式 。 ax\(\equiv\)b(mod m)这种形式的合同式称为一次同余式;类似地,\(\mathrm{a}_2\mathrm{x}^2+\mathrm{a}_1\mathrm{x}\equiv \mathrm{b}\left( \mathrm{mod} \mathrm{m} \right)\)称为二次同余式。 一次同余式解的个数: 1、若a和m互质,b任意,则模m恰有一个数x使ax\(\equiv\) b(mod m) 。 推论:设p为质数。若a\(\not \equiv\) 0 (mod p),b任意,则模p恰有一个数x使ax\(\equiv\) b(mod p)。 2、若(a, m)=d>1 ,且d|b,则同余式ax\(\equiv\) b(mod m)有d个解 ![]() 求解一次合同方程的方法 : 方法一:先使用辗转相除方法将互质的a与m的最大公因数1表示为a和m的倍数和的形式:1=as+mt,然后取x=sb,即可。 注意:\(\mathrm{s}=(-1)^k\mathrm{T}_{\mathrm{k}}\) ![]() ![]() ![]() 方法二 :就是利用合同的性质,使x的系数变成1,即得到解。 ![]() ![]() 定理5.3.2:若(a, m)=d>1,且d\(\nmid\)b,则同余式ax\(\equiv\) b (mod m)无解。 本定理可以作为同余式无解的判定定理. 定理5.3.3:若(a, m)=d>1 ,且d|b,则同余式ax\(\equiv\)b(mod m)有d个解,分别为 \(\mathrm{\alpha}\), \(\mathrm{\alpha}\)+m/d, \(\mathrm{\alpha}\)+2m/d, …, \(\mathrm{\alpha}\)+(d-1)m/d …… 其中\(\mathrm{\alpha}\)是同余式(a/d)x\(\equiv\)b/d (mod m/d)的解。 ![]() 定理5.4.1 设[m1,m2]为m1,m2的最低公倍数。则同余式组 x\(\equiv\)a1 (mod m1) x\(\equiv\)a2 (mod m2) ……………..(1) 在mod[m1,m2]下有唯一解的充要条件为 (m1,m2)|(a1-a2) ……………………….(2) Note:当此定理中的(m1,m2)=1这种特殊情况时,则(1)有关于模m1m2唯一解。推广此特殊情形即得到中国剩余定理,也称为孙子定理。后经过秦九韶整理和解法的推广,我们这里称之为秦九韶定理。 秦九韶定理 :设m1, m2 , …, mk两两互质。a1, a2, …, ak为k个整数,则下列同余式组有解,且在模m1 m2 …mk下解唯一: \[\left. \begin{array}{r} \mathrm{x}\equiv \mathrm{a}_1\left( \mathrm{mod} \quad\mathrm{m}_1 \right) ,\\ \mathrm{x}\equiv \mathrm{a}_2\left( \mathrm{mod} \quad\mathrm{m}_2 \right) ,\\ \mathrm{……} \mathrm{……} \mathrm{……},\\ \mathrm{x}\equiv \mathrm{a}_{\mathrm{k}}\left( \mathrm{mod} \quad\mathrm{m}_{\mathrm{k}} \right)\\ \end{array} \right\} \left( 1 \right) \]![]() ![]() ![]() ![]() 习题: ![]() ![]() ![]() ![]() 结论:设n是任意正整数, A 为mod n的任意剩余类,a\(\in\)A。若a和n互质,则A中任意数和n互质。 若A中有一个数和n互质,则其中所有的数都和n互质。故A 中的数或者都和n互质,或者都和n不互质。 **例. ** mod 6 2,8,16 ,…,与6都不互质。 5,11,17,…,与6都互质。 定义:设A 为mod n的一个剩余类,若对a\(\in\)A,a与n互质,则称剩余类A与n互质。 Euler函数 : 定义: 和n互质的剩余类的个数称为Euler(欧拉)函数,记为\(\mathrm{\varphi}\)(n)。 定义 :从和n互质的每一个剩余类中取出一个数,这样得到的\(\mathrm{\varphi}\)(n)个数称之为作成mod n的一个简化剩余系。 显然,从mod n的一个非负最小完全剩余系中取出与n互质的那些数,就得到mod n的一个简化剩余系,因而\(\mathrm{\varphi}\)(n)等于\(\leqslant\)n的正数中和n互质的数的个数。 例 n=10,则mod n的一个完全剩余系为0,1,…,9,一个简化剩余系为1,3,7,9,\(\mathrm{\varphi}\)(10)=4。 例 n=12,则mod n的一个完全剩余系为0,1,…,11,一个简化剩余系为1,5,7,11,\(\mathrm{\varphi}\)(12)=4。 定理5.4.5 :设m=m1…mk,而m1, …, mk两两互质。则\(\mathrm{\varphi}\)(m)= \(\mathrm{\varphi}\)(m1)\(\mathrm{\varphi}\)(m2) …\(\mathrm{\varphi}\)(mk) 例. \(\mathrm{\varphi}\)(2646)= \(\mathrm{\varphi}\)(2×27×49) = \(\mathrm{\varphi}\)(2) ×\(\mathrm{\varphi}\)(27)×\(\mathrm{\varphi}\)(49) 定理5.4.6 :\( \text{设n}={\mathrm{p}_1}^{\mathrm{r}_1}{\mathrm{…p}_{\mathrm{k}}}^{\mathrm{r}_{\mathrm{k}}}\text{是n的质因数分解式,p}_1\mathrm{…p}_{\mathrm{k}}\text{都不相同,于是} \\ \mathrm{\varphi}\left( \mathrm{n} \right) =\mathrm{n}\left( 1-\frac{1}{\mathrm{p}_1} \right) \mathrm{…}\left( 1-\frac{1}{\mathrm{p}_{\mathrm{k}}} \right)\) \(\text{例} \mathrm{\varphi (}2646)=\mathrm{\varphi (}2×3^3×7^2)=2646×(1-1/2)(1-1/3)(1-1/7)=756\) 定理5.4.7(Fermat-Euler定理,Euler1760年提出) :若a和n互质,则\(\mathrm{a}^{\mathrm{\varphi}\left( \mathrm{n} \right)}\equiv 1\)(mod n) \(\text{例}:a=3,n=10,3与10互质,\mathrm{\varphi (}10)=4,则3^4\equiv 1(mod10) \\ a=5,n=12,5与12互质,\mathrm{\varphi (}12)=4,则5^4\equiv 1(mod12)\) 推论1 (Fermat小定理Ⅰ) 若p是质数而p \(\nmid\) a,则\(\mathrm{a}^{\mathrm{p}-1}\equiv 1\)(mod p)。 推论2(Fermat小定理Ⅱ) 若p为质数,则对任意整数a,都有\(\mathrm{a}^{\mathrm{p}}\equiv a\)(mod p)。 例:p=3, a=2, \(2^{3-1}\equiv 1\left( \mathrm{mod} 3 \right)\) \(2^{3}\equiv 2\left( \mathrm{mod} 3 \right)\) 例题: ![]() 1、用辗转相除法求1046和2683的最高公因数并表示为它们的倍数和。 2683/1046=2……591 1046/591=1……455 591/455=1……136 455/136=3……47 136/47=2……42 47/42=1……5 42/5=8……2 5/2=2……1 2/1=2……0 k 0 1 2 3 4 5 6 7 8 9 \(\mathrm{r}_{\mathrm{k}}\) 591 455 136 47 42 5 2 1 0 \(\mathrm{q}_{\mathrm{k}}\) 2 1 1 3 2 1 8 2 2 \(\mathrm{S}_{\mathrm{k}}\) 0 1 1 2 7 16 23 200 423 \(\mathrm{T}_{\mathrm{k}}\) 1 2 3 5 18 41 59 513 1085最高公因数:\(1=\left( -1 \right) ^{8-1}\times 423\times 2683+\left( -1 \right) ^8\times 1085\times 1046\) (注意n是最后一个非零余项的n) 公式: \[\mathrm{S}_0=0,\mathrm{S}_1=1,\mathrm{T}_0=1,\mathrm{T}_1=\mathrm{q}_1\\\mathrm{S}_{\mathrm{k}}=\mathrm{q}_{\mathrm{k}}\mathrm{S}_{\mathrm{k}-1}+\mathrm{S}_{\mathrm{k}-2}\\\mathrm{T}_{\mathrm{k}}=\mathrm{q}_{\mathrm{k}}\mathrm{T}_{\mathrm{k}-1}+\mathrm{T}_{\mathrm{k}-2}\\\mathrm{d}=\left( -1 \right) ^{\mathrm{n}-1}\mathrm{S}_{\mathrm{n}}\mathrm{a}+\left( -1 \right) ^{\mathrm{n}}\mathrm{T}_{\mathrm{n}}\mathrm{b} \]2、判断题:0和1 是互质的。(对) 【解】±1和任意整数(包括0)互质。 3、判断题:0和100的最高公因数是±100。( 对 ) 第十次作业判定同余式206x\(\equiv\) 114(mod 422)是否有解,如果存在请给出解。 【解】(206,114)=2且2|114故有两个解 法一: 先求103\(\equiv\) 57(mod 211)的解 211=103*2+5 故206x\(\equiv\) 114(mod 211) 又因为211x\(\equiv\) 0(mod 211) 5x\(\equiv\) -114(mod 211) 5x\(\equiv\) 97(mod 211) 因为211=42*5+1 故210x\(\equiv\) 12936(mod 211) 211x\(\equiv\) 0(mod 211) x\(\equiv\) -12936(mod 211) x\(\equiv\) 146(mod 211) 故x\(\equiv\) 146(mod 422) x\(\equiv\) 357(mod 422) 法二: 先求103$\equiv$57(mod 211)的解 211=103*2+5 103=20*5+3 5=3*1+2 3=2*1+1 2=1*2+0 k 0 1 2 3 4 5 \(\mathrm{r}_{\mathrm{k}}\) 5 3 2 1 0 \(\mathrm{q}_{\mathrm{k}}\) 2 20 1 1 2 \(\mathrm{S}_{\mathrm{k}}\) 0 1 20 21 41 \(\mathrm{T}_{\mathrm{k}}\) 1 2 41 43 84最高公因式:\(1=\left( -1 \right) ^3\times 41\times 211+\left( -1 \right) ^4\times 84\times 103\) 由此知:\(\mathrm{S}=\left( -1 \right) ^4\times 84=84\) \(x=Sb=84\times57=4788=211\times 23-65\equiv -65\left( \mathrm{mod } 211 \right) \equiv 146\left( \mathrm{mod } 211 \right)\) 归正以后得x\(\equiv\) 146(mod 422) x\(\equiv\) 357(mod 422) 往期回顾离散数学(集合论) 离散数学(古典数理逻辑) 离散数学(图与网络) 离散数学(数论基础) 离散数学(格与布尔代数) 离散数学(群、环、域) |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |