腾宁科技做网站399元全包,网站域名攻击,福建建设执业注册中心网站,定州网站建设兼职mod运算#xff0c;即求余运算#xff0c;是在整数运算中求一个整数 x 除以另一个整数y的余数的运算#xff0c;且不考虑运算的商。在计算机程序设计中都有MOD运算#xff0c;其格式为#xff1a; mod(nExp1,nExp2)#xff0c;即是两个数值表达式作除法运算后的余数。中文…mod运算即求余运算是在整数运算中求一个整数 x 除以另一个整数y的余数的运算且不考虑运算的商。在计算机程序设计中都有MOD运算其格式为 mod(nExp1,nExp2)即是两个数值表达式作除法运算后的余数。中文名求余运算外文名MOD科 目数学应 用计算机编程函 数mod(nExp1,nExp2)功 能取模运算MOD运算模p运算编辑语音给定一个正整数p任意一个整数n一定存在等式n kp r其中k、r是整数且 0 ≤ r p称呼k为n除以p的商r为n除以p的余数。[1]对于正整数p和整数a,b定义如下运算取模运算a mod p 表示a除以p的余数。模p加法(a b) mod p 其结果是ab算术和除以p的余数也就是说(ab) kp r则 (ab) mod p r。模p减法(a-b) mod p 其结果是a-b算术差除以p的余数。模p乘法(a × b) mod p其结果是 a × b算术乘法除以p的余数。可以发现,模p运算和普通的四则运算有很多类似的规律如[1]结合律((ab) mod p c)mod p (a (bc) mod p) mod p((a*b) mod p * c)mod p (a * (b*c) mod p) mod p交换律(a b) mod p (ba) mod p(a × b) mod p (b × a) mod p分配律((a b)mod p × c) mod p ((a × c) mod p (b × c) mod p) mod p(a×b) mod c(a mod c * b mod c) mod c(ab) mod c(a mod c b mod c) mod c(a-b) mod c(a mod c- b mod c) mod c简单的证明其中第一个公式((ab) mod p c) mod p (a (bc) mod p) mod p假设a k1*p r1b k2*p r2c k3*p r3ab (k1 k2) p (r1 r2)如果(r1 r2) p 则(ab) mod p (r1 r2) -p否则(ab) mod p (r1 r2)再和c进行模p和运算得到结果为 r1 r2 r3 的算术和除以p的余数。对右侧进行计算可以得到同样的结果得证。MOD运算模p相等编辑语音如果两个数a、b满足a mod p b mod p则称他们模p相等记做a ≡ b (mod p)可以证明此时a、b满足 a kp b其中k是某个整数。[2]对于模p相等和模p乘法来说有一个和四则运算中迥然不同的规则。在四则运算中如果c是一个非0整数则ac bc 可以得出 a b但是在模p运算中这种关系不存在例如(3 x 3) mod 9 0(6 x 3) mod 9 0但是3 mod 9 36 mod 9 6定理(消去律)如果gcd(c,p) 1 则 ac ≡ bc mod p 可以推出 a ≡ (b mod p)证明因为ac ≡ bc (mod p)所以ac bc kp也就是c(a-b) kp因为c和p没有除1以外的公因子因此上式要成立必须满足下面两个条件中的一个1) c能整除k2) a b如果2不成立则c|kp因为c和p没有公因子因此显然c|k所以k ck因此c(a-b)kp可以表示为c(a-b) ckp因此a-b kp得出a ≡ b (mod p)如果a b则a ≡ b mod p 显然成立得证MOD运算欧拉函数编辑语音欧拉函数是数论中很重要的一个函数欧拉函数是指对于一个正整数n小于n且和n互质的正整数的个数记做φ(n)其中φ(1)被定义为1但是并没有任何实质的意义。定义小于n且和n互质的数构成的集合为Zn称呼这个集合为n的完全余数集合。显然对于素数pφ(p) p -1.对于两个素数p、q他们的乘积n pq 满足φ(n) (p-1)(q-1)证明对于质数p,q满足φ(n) (p-1)(q-1)考虑n的完全余数集Zn { 1,2,....,pq -1}而不和n互质的集合由下面三个集合的并构成1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个2) 能够被q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个3)很显然1、2集合中没有共同的元素因此Zn中元素个数 pq - (p-1 q- 1 1) (p-1)(q-1)MOD运算欧拉定理编辑语音对于互质的整数a和n有a^φ(n) mod n 1[3]证明首先证明下面这个命题对于集合Zn{x^1,x^2,...,x^φ(n)}考虑集合S {ax^1 mod n,ax^2mod n,...,ax^φ(n) mod n}则S Zn1) 由于a,n互质x^i 也与n互质则ax^i 也一定于n互质因此任意x^i, ax^i mod n 必然是Zn的一个元素2) 对于Zn中两个元素x^i 和x^j如果x^i ≠ x^j则ax^i mod n ≠ ax^j mod n这个由a、n互质和消去律可以得出。所以很明显SZn既然这样那么(ax^1 × ax^2×...×ax^φ(n))mod n (ax^1 mod n × ax^2 mod n × ... × ax^φ(n) mod n)mod n (x^1 × x^2 × ... × x^φ(n)mod n考虑上面等式左边和右边左边等于( (a^φ(n) × (x^1 × x^2 × ... × x^φ(n)))mod n右边等于(x^1 × x^2 × ... × x^φ(n))mod n而(x^1 × x^2 × ... × x^φ(n))mod n和p互质根据消去律可以从等式两边约去就得到a^φ(n) mod n 1推论对于互质的数a、n满足a^(φ(n)1) mod n aMOD运算费马定理编辑语音a是不能被质数p整除的正整数则有ap-1≡ 1 mod p证明这个定理非常简单由于φ(p) p-1代入欧拉定理即可证明。同样有推论对于不能被质数p整除的正整数a有ap≡ a mod p[3]MOD运算进一步应用编辑语音有关mod的一道证明题不用算数基本定理证明[a,b](a,b)|ab|证明在数论中证明等式有一种常用的方式就是证明两边互为整除此题也不例外只是要先移项。|ab|/(a,b)|a|(|b|/(a,b))a|(|ab|/(a,b))同理有b|(|ab|/(a,b))于是|ab|/(a,b)是a,b的公倍数即[a,b]|(|ab|/(a,b))∵|a||[a,b]∴(|a|/(a,b))|([a,b]/(a,b))同理(|b|/(a,b))|([a,b]/(a,b))又∵(|a|/(a,b))与(|b|/(a,b))互质∴(|ab|/(a,b)²)|([a,b]/(a,b))∴(|ab|/(a,b))|[a,b]综上所述[a,b](a,b)|ab|.设m,m′都是正整数d(m,mˆ)b≡bˆ(mod d).证明系统x≡b(mod m) ①x≡bˆ(mod mˆ) ②的任意两个解都是模ρ同余其中ρlcm{mmˆ}。证明设y是满足题设的另外一个解则有y≡b(mod m) ③y≡bˆ(mod mˆ) ④∵x≡b(mod m)∴x≡b(mod m/d), y≡b(mod m/d)两式相减则有x-y≡b-b≡0≡(mod m/d)∴x≡y(mod m/d)同理x≡y(mod mˆ/d)∵(m/d,mˆ/d)1∴x≡y(mod mmˆ/d²)设yxkmmˆ/d²分别代入③④中并结合①②则有xkmmˆ/d²≡b≡x(mod m) kmmˆ/d²≡0(mod m)xkmmˆ/d²≡bˆ≡x(mod mˆ) kmmˆ/d²≡0(mod mˆ)即m|kmmˆ/d²kmˆ/d²为整数(mˆ/d)(k/d)为整数mˆ|kmmˆ/d²km/d²为整数(m/d)(k/d)为整数显然(mˆ/d,d)1与(m/d,d)1至少有一个成立否则(m,mˆ)d²,矛盾.∴kld,yxlmmˆ/d,而mmˆ/d|mmˆ|/(m,mˆ)[m,mˆ]ρlcm{mmˆ}∴yxlρy≡x(mod ρ)参考资料1.罗守山信息安全的数学基础国防工业出版社2011.472.阿普斯托解析数论导引哈尔滨工业大学出版社2016.7953.维诺格拉多夫数论基础与维诺格拉多夫哈尔滨工业大学出版社2014.132
