数论与有限域-第四章.ppt

第四章 原根和指数 第一节 原根 一、整数的阶 二、原根的定义和性质 三、原根的存在性 四、原根的求法 一、整数的阶 由欧拉定理，若正整数n与整数a互素，则 aφ(n)≡1(mod n)。 因而同余式ax≡1(mod n)至少有一个正整数解 x=φ(n)。 进而同余式ax≡1(mod n)必定有一个最小的正整数解x。一般地： 定义4.1.1 设正整数a与n互素，则称同余式ax≡1(mod n)的最小正整数解x，为a模n的阶（或次数），记为ordna。 一、整数的阶 例4.1.1 计算2模11的阶，3模11的阶，以及5模11的阶。 解：由 21≡2(mod 11)，22≡4(mod 11)， 23≡8(mod 11)，24≡5(mod 11)， 25≡10(mod 11)，26≡9(mod 11)， 27≡7(mod 11)，28≡3(mod 11)， 29≡6(mod 11)，210≡1(mod 11)， 因而ord112=10。 一、整数的阶 例4.1.1 计算2模11的阶，3模11的阶，以及5模11的阶。 解：由 31≡3(mod 11)，32≡9(mod 11)，33≡5(mod 11)， 34≡4(mod 11)，35≡1(mod 11)， 得到ord113=5。 由 51≡5(mod 11)，52≡3(mod 11)，53≡4(mod 11)， 54≡9(mod 11)，55≡1(mod 11)， 得到ord115=5。 一、整数的阶 定理4.1.1 设p是素数且整数a模pj的阶记为fj，则 a模pj+1的阶fj+1=fj或fj+1=pfj，又若pi|| ，则 例4.1.2求11模212的阶。 解：由于111≡1(mod 2)，因而 f1=1，而 111≡3(mod 22)，112≡1(mod 22)， 所以f2=2，且 112-1=120=23·15， 因而23||120，123，故11模212的阶 f12=212-3×2=1024。 一、整数的阶 定理4.1.2 若正整数m的标准分解式为 ，则整数a模m的阶等于整数a模 ，a模 ,…,a模 的阶的最小公倍数。 例4.1.3 求3模140的阶。 解：由于140=4×5×7，而 31≡3(mod 4)，32≡1(mod 4)， 得到ord43=2。又 31≡3(mod 5)，32≡4(mod 5)， 33≡2(mod 5)，34≡1(mod 5)， 得到ord53=4。又 31≡3(mod 7)，32≡2(mod 7)，33≡6(mod 7)， 34≡4(mod 7)，35≡5(mod 7)，36≡1(mod 7)， 得到ord73=6。故3模140的阶为[2,4,6]=12。 一、整数的阶 定理4.1.3 设整数a与正整数n相对互素，则正整数x是同余式ax≡1(mod n)的解当且仅当ordna|x。 证明：给定正整数x，若ordna|x，则由于此时存在正整数k，使得x=k?ordna，因而 即此时正整数x是同余式ax≡1(mod n)的解。 反之，若已知正整数x是同余式ax≡1(mod n)的解，则由算术基本定理会存在整数q，r，使得 x=q?ordna+r，0≤rordna。 因而 ax= ≡ar (mod n)。 一、整数的阶 证明：ax= ≡ar (mod n)。 由于ax≡1(mod n)，因而 ar≡1(mod n)。 但是ordna是使得ax≡1(mod n)成立的最小正整数，现在竟然有整数r，0≤rordna，也使得同余式ax≡1(mod n)成立，因而 r=0，即x=q?ordna，故此时ordna|x。 例4.1.4确定x=137与x=120是否为同余式2x≡1(mod 11)的解。 解：由例4.1.1，有ord112=10，由于10?137且3|120，因而 x=137不是同余式2x≡1(mod 11)的解， 而x=120是同余式2x≡1(mod 11)的解。 一、整数的阶 推论4.1.1 设整数a与正整数n相对互素，则 ordna|φ(n)。 证明：由欧拉定理若(a,n)=1，则 aφ(n)≡1(mod n)， 结合定理4.1.3就得到 ordna|φ(n)。 要计算ordna，由推论4.1.1，可以先找出φ(n)的各个因子d1, d2,…, ds，随后再通过计算模n的值，找出使得成立的最小的dj，则ordna=dj。 一、整数的