![同余问题 同余问题例题](http://img.zhejianglong.com/240416/125K051X-0.jpg)
文章插图
大家好,小问来为大家解答以上问题 。同余问题例题,同余问题这个很多人还不知道,现在让我们一起来看看吧!
1、准备知识:引理1.剩余系定理2若a,b,c为任意3个整数,m为正整数 , 且(m,c)=1,则当ac≡bc(modm)时,有a≡b(modm)证明:ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质,c可以约去,a–b≡0(mod m)可得a≡b(mod m)引理2.剩余系定理5若m为整数且m>1,a[1],a[2],a[3],a[4],…a[m]为m个整数,若在这m个数中任取2个整数对m不同余,则这m个整数对m构成完全剩余系 。
2、证明:构造m的完全剩余系(0,1,2,…m-1),所有的整数必然这些整数中的1个对模m同余 。
3、取r[1]=0,r[2]=1,r[3]=2,r[4]=3,…r=i-1,1<=m 。
4、令(1):a[1]≡r[1](mod m),a[2]≡r[2](mod m),a≡r(mod m)(顺序可以不同),因为只有在这种情况下才能保证集合{a1,a2,a3,a4,…am}中的任意2个数不同余 , 否则必然有2个数同余 。
5、由式(1)自然得到集合{a1,a2,a3,a4,…am}对m构成完全剩余系 。
6、引理3.剩余系定理7设m是一个整数 , 且m>1,b是一个整数且(m,b)=1 。
7、如果a1,a2,a3,a4,…am是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系 。
8、证明:若存在2个整数ba和ba[j]同余即ba≡ba[j](mod m),根据引理2则有a≡a[j](mod m) 。
9、根据完全剩余系的定义和引理4(完全剩余系中任意2个数之间不同余,易证明)可知这是不可能的,因此不存在2个整数ba和ba[j]同余 。
10、由引理5可知ba[1],ba[2],ba[3],ba[4],…ba[m]构成模m的一个完全剩余系 。
11、引理4.同余定理6如果a,b,c,d是四个整数,且a≡b(mod m),c≡d(mod m),则有ac≡bd(mod m)证明:由题设得ac≡bc(mod m),bc≡bd(mod m),由模运算的传递性可得ac≡bc(mod m)证明过程:构造素数p的完全剩余系P={1,2,3,4…(p-1)} , 因为(a,p)=1,由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一个完全剩余系 。
【同余问题 同余问题例题】12、令W=1*2*3*4…*(p-1),显然W≡W(mod p) 。
13、令Y=a*2a*3a*4a*…(p-1)a,因为{a,2a,3a,4a,…(p-1)a}是p的完全剩余系,由引理2可知A中所有元素必然满足a≡1(mod p),2a≡2(modp),…(p-1)a≡p–1(mod p) 。
14、由引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(mod p)即W*a^(p-1)≡W(modp) 。
15、易知(W,p)=1,由引理1可知a^(p-1)≡1(modp) 以上就是【同余问题例题,同余问题】相关内容 。
推荐阅读
- Win10端口问题解决办法及常见端口介绍解析
- Win10端口占用查询快速排查问题!方法
- 图文攻略 Win10端口封闭解决方法-有效解决您的网络问题
- Win10竖屏翻转简单步骤解决横屏问题解析
- Win10窗口无法完全显示?解决这个问题的秘诀在这里!介绍
- 洛阳:公积金贷款信息纳入征信系统 这些问题你可能关注
- 成都职工医保门诊共济保障热点咨询问题,集中解答来啦!
- 2023最新 毕业生参加社保需要注意什么问题?
- 牛每天喂多少酒糟,应注意的问题有哪些
- 形容懒得应付和解决问题的成语大全