初等数论第七章原根

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，qN ，0  t < ，则由定义 1，有 a t  a q  t = a r  r   1 (mod m)。 由m(a)的定义可知 t = 0，即r  r ，也即式(3)成立。必要性得证。 若式(3)成立，则存在 qN ，使得 r  r  = q，则由定义 1，有 a r  r  = a q  1 (mod m)， 即式(4)成立，从而式(2)成立，充分性得证。 取 r  = 0，得到定理的第二个结论。证毕。 推论 m(a)(m)。 证明 由 Euler 定理及定理2 得证。 定理3 设 k 是非负整数，则 )),(()()(kaaammkm...