原根與指數(shù)ppt課件(參考版)
2025-05-09 18:02本頁面
【正文】 ? 指數(shù)為 4的元素有 φ(4)=2個 ,是 610?32, 630?9(mod 41)。 練習 ? 求模 41的原根情況 ? 所以 :指數(shù)為 1的元素有 φ(1)=1個 ,是 1。 ? 630?9, 631?13, 632?37,633?17,634?20, 635?38(mod 41)。 ? 618?33, 619?34, 620?40,621?35,622?5, 623?30 (mod 41)。 ? 66?39, 67?29, 68?10, 69?19,610?32, 611?28(mod 41)。 ? 68?10, 620?1(mod 41)。 ? 48?20, 420?1(mod 41)。 a s? 1 (mod m) , a s? 1 (mod n) = a s? 1 (mod mn) = t|s 練習 ord28(3)=？ φ(28)= φ(4) φ(7)=2*6=12 本來需要計算冪為 6 但是因為 ord7(3)=6， ord4(3)=2 所以 6| ord28(3) 現(xiàn)在只需直接計算 36?1(mod 28)， 所以 ord28(3)= 6 上面利用的是 ⑧ ，利用⑨直接 因為 (4， 7)=1，所以 ord28(3)=[6,2]=6 ? 計算 3模 28的指數(shù) 練習 ord49(3)=？ φ(49)= 497=42 ord7(3)=6， 所以 6| ord49(3) 因為 36?81*9?17*9?2*3 ?6(mod 49) 所以 ord49(3)= 42 作業(yè) (3)： 84頁， 2（ 1)(3） ? 計算 3模 49的指數(shù) 指數(shù)與原根 ? 性質 41 指數(shù)的基本性質 ⑦ (ab, m) =1， (ordm(a),ordm(b))=1則ordm(ab)=ordm(a)ordm(b) 分析：設 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) 價值：簡化求原根 練習 φ(23)= 22，指數(shù)可能為 1 22 直接計算 :22?4, 211?1(mod 23)， 所以 ord23(2)=11 用以前的方法再計算 3的冪，如不行再計算 5的 …… 此時考慮只需找到一個 ord23(a)=2， 則 ord23(2a)=22 而 ord23(1)=2 所以 ord23(2)=22， 2是原根，所以原根有 φ(22)=10個 (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 ? 計算模 23的原根 原根的存在條件 ? 對于什么樣的正整數(shù) m， 模 m的原根是存在 ? ? 下面的定理不用證明，只需應用 ? 定理 若 p奇素，則原根存在 ? 定理 若 p奇素， g是模 p的一個原根，則 g或g+p是模 p2的原根，若 g是模 p2的原根，則 g是模 p?的原根， ? 定理 42 模 m有原根的必要條件是 m = 2， 4， p?或 2p?， 其中 p是奇素數(shù) ， ? ? 1 模素數(shù)原根的計算技巧 ? 定理 43 ? 設奇素數(shù) p， p1= ， pi素，若對（ a,p） =1滿足 i=1,2,…,s 則 a為 p的原根 思路：設 ordp(a)=n， 則 n|p1， 若 np1則存在某個素數(shù) pi|(p1)/n 即： (p1)/n= pi u即 與條件矛盾，所以 n=p1 ieisip1??)( m o d11pa ipp??)( m o d11paa nuppi ???練習 ? 求模 47的一個原根 ? 首先分解 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的一個原根 指標 ? 定義 42 設 m1的整， g是其一個原根，(a,m)=1， 則存在唯一整數(shù) r使 gr ? a (mod m) 則 r叫做以 g為底的
教學課件相關推薦
鄂ICP備17016276號-1