第六章 (12) 指数与原根
- 格式：pdf
- 大小：506.02 KB
- 文档页数：41
' '',由 此 及 ( ', '' ) = 1 推 出 ' .同 样 , 有
1 (ab) (ab) '' b '' (mod m),所 以 , '' ',由 此 及 ( ', '' ) = 1 , 推 出 ' '' .此 外 , 显 然 有( ab) ' '' 1 (mod m), 所 以 , ' ' ''.因 此 , ' ''. 必 要 性 ： 由 (ab) 1 (mod m), 得 .另 一 方 面 有 ' '', 由 此 及 ' ''就 推 出 ' '',即 ( ', '' ) = 1 .
定理2 模p 是素数,则模p 必有原根.事实上, 对 每 一 正 整 数 d p 1, 在 模 p 的 一 个 简 化 剩 余 系 中 恰 有 (d )个 数 对 模 p 的 指 数 为 d .
定 理 3 设 p 为 奇 素 数 . 那 么 , 对 任 意 的 1 , 模 p 必 有 原 根 . 事 实 上 , 存 在 g 使 得 对 所 有 的 1, g 是 模 p , 模 2 p 的公共的原根. ( i ) 若 g 是 模 p 1( 1 ) 的 原 根 , 则 g一 定 是 模 p的 原 根 . ( i i ) 若 g 是 模 p的 原 根 , 则 必 有 p 1 ( g ) ( p )或 ( p 1 ). ( i i i ) 当 p 是 奇 素 数 , 若 g 是 模 p 的 原 根 , 且 有 g p 1 1 rp p | r ,则 g 是 所 有 模 p ( 1 ) 的 原 根 . (iv) 当p 是奇素数,若g '是模p的原根且为奇数(若g '是 偶 数 , 则 以 g ' p代 g ' ) , 那 么 有 g g ' tp, t 0,1, , p 1.
性 质 5 若 ( a, m) 1,则 a 0 , a1 ,
, a m ( a )1 这 m (a ) 个 数
对模 m两两不同余.特别地,当a 是模 m的原根时， 即 m (a ) (m) 时 , 这 (m)个 数 是 模 m 的 一 组 既 约 剩余系. 例 2是 模9的 一 个 原 根 , 这 是 因 为22 4,23 8,26 1
性 质 9 (i) 若 n m ,则 n (a) m (a); (ii) 若(m1 , m2 ) 1,则 有 m1m2 (a) [ m1 ( a), m2 ( a)] . (4) 证 (i)可 由 性 质2直 接 推 出 . 由 ( i ) 即 得 * m1m2 (a) , 这 里
k
此外,在模 m的一个既约剩余系中,至少有 （ m (a)） 个 数 对 模 m 的 指 数 等 于 m (a). 证 记 m (a), ' / ( , k ), * m ( a k ).由 定 义 知 a
k *
1 (mod m), a
'
k '
* [ m (a), m (a)].另 一 方 面 , 显 然 有 a * 1 (mod m j ),
1 2
j 1,2.由 此 及 (m1 , m2 ) 1 推 出 a * 1 (mod m1m2 ).因 而 由 性 质2推 出 m1m2 (a) * . 所 以 ( 4 ) 式 成 立 .
例 1 m 7, ( 7) =6, 求模 7 的指数和原根.
a
7 a
-3
3
-2
6
-1
2
1
1
2
3
3
6
例 2 m 10 2 5, ( 1 0 ) = 4 , 求 模 1 0 的 指 数 和 原 根. 例 3 m 15 3 5, ( 1 5 ) = 8 , 求 模 1 5 的 指 数 和 原 根. 例 4 m 9 3 , ( 9 ) = 6 , 求 模 1 5 的 指 数 和 原 根.
p j为 不 同 奇 素 数 , j 1 (1 j r ).设 由 式 (m)给 出 , 容 易 验 证 , 当 m 属 于 式 ( 1 0 ) 列 出 的 任 一 情 形 时 , 必 有 (m) (m), 由此知,这时模m没有原根.
§2 原根
定 理 1 模 m 有 原 根 的 充 要 条 件 是 m 1,2,4, p ,2 p ,其 中 p 是 奇 素 数 , 1 .
1 特 别 地 , 当 m 20 p1
0 1
r pr , p j是 不 同 的 奇 素 数 , 我 们 有
r
m (a) [2c , ( p1 ), , ( pr )] ( m),
0, 0 0,1 其 中 c0 1, 0 2 2, 3 0 0 例 ： 105 ( 2) [ 7 ( 2), 15 ( 2)] [6,4] 12.
性 质 1 2 模 m 存 在 原 根 的 必 要 条 件 是 ： m 1,2,4, p ,2 p ,其 中 p 是 奇 素 数 . 证 当 m 不 属 于 上 式 列 出 的 情 形 时 , 必 有 m 2 ( 3),
1 20 p1 r 1 pr ( 2, r 1),或 20 p1 r pr ( 0, r 2),(10)其 中
由 此 及 性 质5 证 明 了 结 论.
性 质 8 m (ab) m (a) m (b)的 充 要 条 件 是 ( m (a ) , m (b)) 1. 证 设 ' m (a), '' m (b), m ( ab), [ m ( a), m (b)]. 充 分 性 : 我 们 有 1 (ab) (ab) '' a '' (mod m),所 以 ,
初等数论 第六章 指数与原根
本章内容
1 引进并讨论指数的概念和性质.指数是刻画模m的 简 化 剩 余 系 中 的 元 素 特 征 的 一 个 量 ; 指 数 等 于 (m)的 元 素 称 为 是 模 m 的 原 根. 2 讨论模m 存在原根的充要条件及求原根的算法; 当 模 m 存 在 原 根 g 时 , g 0 , g1, , g ( m )1就 给 出 了 模 m 的
性 质 6 设 a 1是 a 对 模 m 的 逆 , 即 a 1a 1 (mod m ) 我 们 有 m (a ) m (a) .
1
证 这 由 a d 1 (mod m )成 立 的 充 要 条 件 是 ( a ) 1 (mod m )立 即 推 出 .
1 d
m (a) 性 质 7 设 k 是 非 负 整 数 , 则 有 m (a ) = (3) . ( m (a) , k )
', '' 作 分 解 ： ' ' ', '' '' '', 使 得 ( ', '') 1, ' '' .由 性 质7知 m (a ' ) ', m (b '' ) ''.这 样 , 由
性 质 8 推 出 m (a 'b '' ) m (a ' ) m (b '' ) ' '' . 因此 取 c a 'b ''就 满 足 要 求 .
m m (a) [ m (a), m (a)] 推 广 为 : 若 m1, , ms两 两 即 约 ,
1 2 1 2
m m1
ms , 则 m (a ) [ m1 (a ), , ms (a)].
由此及性质3推出：
m (a) [ (m1 ), , (ms )].
mod 9 .由 性 质 知 , 2的 幂 的 前 9 6 个 构 成 模 9 的
一 个 既 约 剩 余 系 . 它 们 是 21 2 mod 9 ,22 4 mod 9 , 23 8 mod 9 ,24 7 mod 9 , 25 5 mod 9 ,26 1 mod 9 .
d
满 足 上 述 要 求 的 最 小 正 整 数.
§1 指数
定 义 1 设 m 1, (a, m) 1.使 a 1 (mod m)
d
成 立 的 最 小 正 整 数 d 称为 a 对 模 m 的 指 数 (或 阶 ), 把 它 记 作 m (a). 定 义 2 当 m (a) (m)时 , 称 a 是 模 m 的 原 根 ， 简称m的原根.
性 质 1 0 设 ( m1 , m2 ) = 1. 那 么 , 对 任 意 的 a1 , a2 , 必 有 a 使 得 m1m2 (a ) = [ m1 (a1 ), m2 (a2 )]. 证 考 虑 同 余 方 程 组 x a1 (mod m1 ), x a2 (mod m1 ), 由孙子定理知,这同余方程组有惟一解: x a (mod m1m2 ), 显 然 有 m1 (a ) = m1 (a1 ) , m2 (a ) = m2 (a2 ) . 由 此 从 性 = [ 10 (7), 10 (9)] 4.
性 质 1 1 对 任 意 的 a, b,一 定 存 在 c 使 得
