原根與指數(shù)ppt課件(編輯修改稿)
2025-06-02 18:02 本頁面
【文章內(nèi)容簡(jiǎn)介】 = [ordm(a),ordn(a)] 分析：設(shè) s=[ordm(a),ordn(a)],t= ordmn(a),由 ⑧ ordn(a)|t, ordm(a)|t =s|t。 a s? 1 (mod m) , a s? 1 (mod n) = a s? 1 (mod mn) = t|s 練習(xí) ord28(3)=？ φ(28)= φ(4) φ(7)=2*6=12 本來需要計(jì)算冪為 6 但是因?yàn)?ord7(3)=6， ord4(3)=2 所以 6| ord28(3) 現(xiàn)在只需直接計(jì)算 36?1(mod 28)， 所以 ord28(3)= 6 上面利用的是 ⑧ ，利用⑨直接 因?yàn)?(4， 7)=1，所以 ord28(3)=[6,2]=6 ? 計(jì)算 3模 28的指數(shù) 練習(xí) ord49(3)=？ φ(49)= 497=42 ord7(3)=6， 所以 6| ord49(3) 因?yàn)?36?81*9?17*9?2*3 ?6(mod 49) 所以 ord49(3)= 42 作業(yè) (3)： 84頁， 2（ 1)(3） ? 計(jì)算 3模 49的指數(shù) 指數(shù)與原根 ? 性質(zhì) 41 指數(shù)的基本性質(zhì) ⑦ (ab, m) =1， (ordm(a),ordm(b))=1則ordm(ab)=ordm(a)ordm(b) 分析：設(shè) a ordm (b) ordm (ab) ? a ordm (b) ordm (ab) b ordm (b) ordm (ab) ? (a b) ordm (b) ordm (ab) ? 1 (mod m) = ordm(a)|ordm(b)ordm(ab),同理，ordm(b)|ordm(a)ordm(ab) 所以， ordm(a)ordm(b)|ordm(ab) 另一方面 (a b) ordm (b) ordm (a) ? 1 (mod m) ,所以ordm(ab)|ordm(a)ordm(b) 價(jià)值：簡(jiǎn)化求原根 練習(xí) φ(23)= 22，指數(shù)可能為 1 22 直接計(jì)算 :22?4, 211?1(mod 23)， 所以 ord23(2)=11 用以前的方法再計(jì)算 3的冪，如不行再計(jì)算 5的 …… 此時(shí)考慮只需找到一個(gè) ord23(a)=2， 則 ord23(2a)=22 而 ord23(1)=2 所以 ord23(2)=22， 2是原根，所以原根有 φ(22)=10個(gè) (2)3?15,(2)5?14,(2)7?10,(2)9?17,(2)13?19(mod 23) (2)15?7,(2)17?5,(2)19?20,(2)21?11 (mod 23) 所以模 23的原根有： 5,7,10,11,14,15,17,19,20,21 ? 計(jì)算模 23的原根 原根的存在條件 ? 對(duì)于什么樣的正整數(shù) m， 模 m的原根是存在 ? ? 下面的定理不用證明，只需應(yīng)用 ? 定理 若 p奇素，則原根存在 ? 定理 若 p奇素， g是模 p的一個(gè)原根，則 g或g+p是模 p2的原根，若 g是模 p2的原根，則 g是模 p?的原根， ? 定理 42 模 m有原根的必要條件是 m = 2， 4， p?或 2p?， 其中 p是奇素?cái)?shù) ， ? ? 1 模素?cái)?shù)原根的計(jì)算技巧 ? 定理 43 ? 設(shè)奇素?cái)?shù) p， p1= ， pi素，若對(duì)（ a,p） =1滿足 i=1,2,…,s 則 a為 p的原根 思路：設(shè) ordp(a)=n， 則 n|p1， 若 np1則存在某個(gè)素?cái)?shù) pi|(p1)/n 即： (p1)/n= pi u即 與條件矛盾，所以 n=p1 ieisip1??)( m o d11pa ipp??)( m o d11paa nuppi ???練習(xí) ? 求模 47的一個(gè)原根 ? 首先分解 471=2*23 ? (a,47)=1,取 a=2, 223? 1 (mod 47)， 失敗 ? 取 a=3, 323? 1 (mod 47)， 失敗 ? 取 a=5, 523? 1 (mod 47)， 52? 25(mod 47)， ? 所以 5是模 47的一個(gè)原根 指標(biāo) ? 定義 42 設(shè) m1的整， g是其一個(gè)原根，(a,m)=1， 則存在唯一整數(shù) r使 gr ? a (mod m) 則 r叫做以 g為底的 a對(duì)模 m的一個(gè)指標(biāo)，記為 r=indga ? 注： ? 類似于對(duì)數(shù)，所以這個(gè)解方程問題叫做離散對(duì)數(shù)問題 指數(shù) ? 7的指數(shù)表 ? 填表規(guī)則 a那行作乘法 ， ind a 那行作加法 ind a為 1時(shí)，對(duì)應(yīng)的 a為起始的那個(gè)原根 a 1 2 3 4 5 6 ind3a 0 2 1 4 5 3 a a2 a3 a4 a5 a6 6 3 2 6 4 5 1 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1