154 第七章 原 根 原根是数论的理论和应用中一个很重要的概念。本章要介绍原根以及与它有关的基本知识。 第一节 指数及其基本性质 定义 1 设 m > 1,(a, m) = 1,则使 a r 1 (mod m) (1) 成立的最小的正整数r,称为 a 对模 m 的指数,记为m(a),在不致误会的情况下,简记为(a)。 由 Eu ler 定理,当 r = (m)时式(1)成立,因此,恒有m(a) (m)。 若 a b (mod m),(a, m) = 1,则显然有m(a) = m(b)。 定义 2 若m(a) = (m),则称 a 是模 m 的原根。 例如,当 m = 7 时,因为 21 2,22 4,23 1 (mod 7), 所以7(2) = 3。又因为 31 3,32 2,33 6,34 4,35 5,36 1 (mod 7), 所以7(3) = 6 = (7),3 是模 7 的原根。 以后,在谈到 a 对模 m 的指数时,总假定 m > 1,(a, m) = 1。 定理1 记 = m(a),则 a0, a1, , a 1 对模 m 两两不同余。 证明 用反证法。若有 0 i < j 1,使得 a i a j (mod m), 则由(a, m) = 1 得到 a j i 1 (mod m), 这与 = m(a)的定义矛盾,所以定理成立。证毕。 155 定理1 说明,若g 是模m 的原根,则 g0, g1, , g(m) 1 构成模m 的简化剩余系。 定理2 设 = m(a),r 与 r是正整数,则 a r a r (mod m) (2) 的充要条件是 r r (mod )。 (3) 特别地,a r 1 (mod m)的充要条件是r。 证明 不妨设 r > r。因为(a, m) = 1,所以式(2)等价于 a r r 1 (mod m)。 (4) 若式(4)成立,记 r r = q t,qN ,0 t < ,则由定义 1,有 a t a q t = a r r 1 (mod m)。 由m(a)的定义可知 t = 0,即r r ,也即式(3)成立。必要性得证。 若式(3)成立,则存在 qN ,使得 r r = q,则由定义 1,有 a r r = a q 1 (mod m), 即式(4)成立,从而式(2)成立,充分性得证。 取 r = 0,得到定理的第二个结论。证毕。 推论 m(a)(m)。 证明 由 Euler 定理及定理2 得证。 定理3 设 k 是非负整数,则 )),(()()(kaaammkm...