5.解:(1)=10,1)=0(10)=114:4,故1.有4个原根 2分 令q1=2,q2=5,经过验算得11的一个最小原根为2, 2分 3,7,9与10互素, 13的全部原根为2=2,2≡6,27=11,2≡7(md13)5分 6.解:从上表可知ind313=4,由于(12,16)=4是4的约数, 1分 所以同余式有解,解数为4 原同余式与12 ind.x≡id313=4(mod16)同解 2分 解得mnd3x=3,7,115(mod16) 3分 反查指标表,得解x=3,4,12,14(mod17) 5分 四.1.证明:(此题有多重解法) 2≡-1(mod3) 2+1=(-1)+1=(-1)2+1=0(mod3) 分 6分 2.证明:(数学归纳法)设a=2m+ (1)n=1时,a2=(2m+1)2=4m(m+1)+1=1(mod8),结论成立 (2)设n=k时结论成立,即有 (2m+1)2-1=0(mod2*),故有(2m+1)2-1=22t(t∈Z 从而 =(2*+21)2+2.24+2,t t2.2 n=k+1时,成立 由(1)(2)得,a2≡1(mod2n+2)(n≥1) 3.证明 第5页共6页第 5 页 共 6 页 5．解： (11) 10 = ， 1 4 ( (11)) (10) 10 4 2 5   = =   = ，故 11 有 4 个原根 2 分 令 1 2 q q = = 2, 5 ，经过验算得 11 的一个最小原根为 2， 2 分 又∵ 1，3，7，9 与 10 互素， ∴ 13 的全部原根为 1 5 7 11 2 2, 2 6, 2 11, 2 7 (mod 13)     5 分 6．解：从上表可知 3 ind 13 4 = ，由于（12，16）＝4 是 4 的约数， 1 分 所以同余式有解，解数为 4 原同余式与 12 13 4 (mod 16) 3 3 ind x ind  = 同解 2 分 解得 3 ind x  3,7,11,15 (mod 16) ， 3 分 反查指标表，得解 x  3,4,12,14 (mod 17) 5 分 四．1．证明：(此题有多重解法) ∵ 2 1 (mod 3)  − 1 分 ∴ 2 1 2 1 ( 1) 1 ( 1) 1 0 (mod 3) n n k+ +  − +  − +  4 分 ∴ 3 2 1 n + 6 分 2．证明：（数学归纳法）设 a m = + 2 1 （1） n =1 时， 2 2 a m m m = + = + +  (2 1) 4 ( 1) 1 1 (mod 8 ) ，结论成立． （2） 设 n k = 时结论成立，即有 2 1 (2 1) 1 0 (mod 2 ) k k m + + −  ，故有 2 2 (2 1) 1 2 ( ) k k m t t Z + + − =  从而 1 2 2 2 2 2 1 ( 1)( 1) ( 1)( 1 2) k k k k k a a a a a + − = − + = − − + 2 2 2 (2 ) 2 2 k k t t + + = +   2 2 4 3 2 2 k k t t + + =  +  3 1 3 2 ( 2 1) 0 (mod 2 ) k k k t t + + + =   +  故 n k = +1 时，成立。 由（1）（2）得， 2 2 1 (mod 2 ) ( 1) n n a n +   3．证明：