07原根(编辑修改稿)

07原根(编辑修改稿)内容摘要：

的简化剩余系中，恰有 (d)个指数为 d 的整数，并由此推出模 m的简化剩余系中恰有 ((m))个原根。 4. 设 m  3， g是模 m的原根， x1, x2,  , x(m)是模 m的简化剩余系，证明： (ⅰ ) 2)(mg  1 (mod m)； (ⅱ ) x1x2 x(m)  1 (mod m)。 5. 设 p = 2n  1是一个奇素数，证明：模 p的全部二次非剩余就是模 p的 全部原根。 6. 证明： (ⅰ ) 设 p奇素数，则 Mp = 2p  1的素因数必为 2pk  1型； (ⅱ ) 设 n  0，则 Fn = n2  1的素因数必为 2n + 1k  1型。 第二节 原 根 对于什么样的正整数 m， 模 m的原根是存在的。 这是本节要研究的问题。 为了叙述方便 ， 对于正整数 n，设它的标准分解式是 n = kkppp  21 212 ， 其中 pi（ 1  i  k）是奇素数 ， 记 (n) = [ )(,),(),(),2( 21 21 kkppp   ]。 定理 1 模 m有原根的必要条件是 m = 1， 2， 4， p或 2p， 其中p是奇素数 ，   1。 证明 若 m不具备定理中所述形式 ， 则必是 m = 2（   3） ， (1) m = kkppp  21 212 （   2， k  1）， (2) 或 m = kkppp  21 212 （   0， k  2）， (3) 159 其中 pi（ 1  i  k）是奇素数，  i（ 1  i  k）是正整数。 如果 m是形如式 (2)的数 ， 那么对于任意的 a， (a, m) = 1， 有 ，，，kipaakipaaiiiiimmip1)(m od1)2(m od11)(m od1)2(m od1)()()()2( a(m)  1 (mod m)。 (4) 容易验证 (m) (m)。 因此，由式 (4)可知，任何与 m互素的数 a不是模 m的原根。 同样方法可以证明，若 m 是形如式 (1)或式 (3)中的数，模 m 也没有原根。 证毕。 下面我们要证明，定理 1 中的条件也是充分条件。 为此，先要证明几个引理。 引理 1 设 m 是正整数。 对任意的整数 a， b，一定存在整数 c，使得 m(c) = [m(a), m(b)]。 证明 由第一章第六节习题 6，存在正整数 1， 2， 1， 2，使得 m(a) = 12， m(b) = 12， (2, 2) = 1， [m(a), m (b)] = 22。 (5) 由第一节定理 3，有 22 )()( 11    ba mm ， ， 因此，由第一节定理 4得到 )()()( 1111   baba mmm  = 22 = [m(a), m(b)]。 取 c = 11 ba 即可得证。 证毕。 引理 2 若 p是奇素数 ， 则模 p有原根。 证明 由引理 1及归 纳法容易证明，存在整数 g， (g, p) = 1，使得  = p(g) = [p(1), p(2),  , p(p  1)]。 显然 p  1， p(j)， 1  j  p  1。 (6) 另一方面 ， 由 式 （ 6。