原根和指数.PPT

4.2 指数 指数表 因而由指数的定义有 x≡514，52，56，510 (mod 17) 由于 52≡8 (mod17)， 56≡2 (mod17) 510≡9 (mod17)，514≡15 (mod17) 因而 x≡15，8，2，9 (mod 17) 由于上面的计算过程的每一步都是可逆的，因而 同余式13x4≡9 (mod 17)有四个模17不同余的解。 4.2 指数 指数表 指数表还可以用来解幂同余式 ax≡b (mod m)，(b,m)=1 其中m有原根r。 注： 请分辨二项同余式和幂同余式的形式区别。 4.2 指数 指数表 显然，幂同余式 ax≡b (mod m) 与同余式 x?indra≡indrb (mod φ(m)) 等价。故幂同余式 ax≡b (mod m) 有解的充要条件是 (indra, φ(m))|indrb 且若有解，恰有(indra, φ(m))个解。 4.2 指数 指数表 例4.2.6：给出同余式4x≡16 (mod 17)的所有解。 解：由例4.2.5可知5是17的原根，对上述同余式的两边取模为17基为5的指数，得到 ind5(4x)=ind516=8 即 ind5(4x)≡x?ind54≡12x≡8 (mod 16) 因而 12x≡8 (mod 16) 由于(12,16)=4，而ind516=8，因而同余式4x≡16 (mod 17)恰有4个解。 4.2 指数 指数表 由欧几里得算法得到16=12×1+4，因而 8=16×2-12×2 因而方程12x-16y=8的特解为 x0=-2，y0=-2 故同余式12x≡8(mod 16)的4个不同余的解为 x≡14，2，6，10 (mod 16) 由于上面所有的计算步骤都是可逆的，因而 4x≡16 (mod 17) 的4个不同余的解为 x≡14，2，6，10 (mod 16) 4.1 原根 原根的存在性 例4.1.15：由例4.1.14对任意的正整数k，r=7是11k的原根，因而定理4.1.17说明对任意的正整数k，r=7也是2?11k的原根，例如7是22的原根。 类似地对任意的正整数k，2是11k的原根，又2+11k是奇数，因而上述定理说明对任意的正整数k，2+11k也是2?11k的原根，例如13是22的原根。 4.1 原根 原根的存在性 综上，就证明了本节最初给出的结论即 定理4.1.18：正整数n，n1，有原根当且仅当n=2, 4, pt或者2pt，这里p是奇素数而t是正整数。 4.1 原根 原根的求法 最后我们来讨论一下原根的求解问题。 一般地，我们应先求出模素数p的原根，然后再依照前面各定理的证明方法来求pa及2pa的原根。 下面介绍另外一种求素数p的原根的方法。 4.1 原根 原根的求法 定理4.1.19：设ordpa=d，dp-1，则at，t=1,2,…,d都不是模p的原根。 证明：因为at，t=1,2,…,d，对模p的阶为 d/(d, t) 而 d/(d,t)≤dp-1 所以at，t=1,2,…,d都不是模p的原根。 4.1 原根 原根的求法 由此定理，要求模p的原根，可以先取a=2，计算2模p的阶d。若d=p-1，则2就是p的原根；若dp-1，则2t，t=1,2,…,d，都不是p的原根，因而可以在1,2,…, p-1中删去2, 22, …, 2d模p的最小正剩余，随后在剩余的数中再取一数，重复以上方法。 由于给定奇素数p，恰有 φ(φ(p))=φ(p-1) 个原根，因而若1,2,…, p-1中只剩下了φ(p-1)个数，则这φ(p-1)个数就是p的所有原根。 4.1 原根 原根的求法 例4.1.16：求p=23的原根。 解：先求a=2模23的阶，由于φ(23)=22，而22的因子只有 1，2，11，22 又 21≡2 (mod 23) 22≡4 (mod 23) 211≡(24)2×23≡(-7)2×8≡3×8≡1 (mod 23) 所以2模23的阶为11≠22，即2不是23的原根。 4.1 原根 原根的求法 因此2t，t=1,2,…,11，都不是23的原根，因而可以在1,2,…,22中除去以下各数： 21≡2 (mod23)， 22≡4 (mod23) 23≡8 (mod23)， 24≡16 (mod23) 25≡9 (mod23)， 26≡18 (mod23)