1. 首頁 > 生活百科 > >

同余問題 同余問題例題

知識經驗


同余問題 同余問題例題

文章插圖
大家好,小問來為大家解答以上問題 。同余問題例題，同余問題這個很多人還不知道,現在讓我們一起來看看吧！
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) 以上就是【同余問題例題，同余問題】相關內容 。

    推薦閱讀