《初等数论》2004~2005学年第二学期考试（查）试题A答案

2004~2005学年第二学期 科目:初等数论 考试(查)试题A答案 命题教师:李伟勋 使用班级:02数本1,2,3班 2.1473.(b,10)=14.0.95840 6.393 9.q(m)=510.(a,b) 二,11.A12.D13 1.解:由于(9,21)=3,而3144,所以原方程有解 1分 原方程等价于3x+7y=48,又因为3×(-2)+7×1=1,故有 3×(-2×48)+7×1×48=48,特解为(-96,48) 3分 所有解为 x=-96+7t t=0,±1, 5分 48+3t 解:∵7=7,9=32,15=3×5, [7,915]=315 1分 ∴原同余式组等价于{x=5(mod9),由孙子定理,得2分 x≡1l=1(mod5) M1=45,M2=35,M3=63 今、5°=5(mM2=5=1(m09Mb32md 5分 3.解:3为平方非剩余,由互反律, p/=(2/3 ()+(+( 1分 或 P≡1(mod3) 3分 P≡-1(mod4) 由孙子定理,得P≡5或-5(mod12),即P=12k±5 5分 4.解:504=23·32·7,且25≡1(mod8), 3 分 故原同余式有解,解数为2+2=24=16 分 第1页共6页

第 1 页 共 6 页 2004 ～2005 学年第 二 学期 科目: 初等数论 考试（查）试题 A 答案 命题教师：李伟勋 使用班级：02 数本 1，2，3 班 一．1．28 2．147 3． ( ,10) 1 b = 4．0.95840… 5．72 6．393 7．－1 8． ( , )    9． 1 ( ) 5 2  m = 10．( , ) | a b c 二．11．A 12．D 13．D 14．C 15．D 16．A 17．D 18．B 19．D 20．C 三．1．解：由于 (9,21) 3 = ，而 3|144 ，所以原方程有解 1 分 原方程等价于 3 7 48 x y + = ，又因为 3 ( 2) 7 1 1  − +  = ，故有 3 ( 2 48) 7 1 48 48  −  +   = ，特解为 ( 96,48) − 3 分 所有解为 96 7 0, 1, 48 3 x t t y t  = − +  =   = + 5 分 2．解： 2 7 7, 9 3 , 15 3 5, [7,9,15] 315 = = =   = = m 1 分 ∴ 原同余式组等价于 2 (mod 7) 5 (mod 9) 11 1 (mod 5) x x x          ，由孙子定理，得 2 分 M M M 1 2 3 = = = 45, 35, 63 ' ' ' 1 2 3 1 1 1 1 1 5 (mod 7) 1 (mod 9) 2 (mod 5) 45 3 35 63 3 M M M      −    所以 x  86 (mod 315) 5 分 3．解：3 为平方非剩余，由互反律，得 1 1 2 3 3 ( 1) ( 1) 3 P P P P P −       − −       = − = −       ， 1 分 1 (mod 3) 1 (mod 3) 1 (mod 4) 1 (mod 4) P P P P           −  − 或 3 分 由孙子定理，得 P  5 5 (mod 12) 或－ ，即 P k =  12 5 5 分 4．解： 3 2 504 2 3 7 =   ，且 25 1 (mod 8)  ， 25 25 4 1, 1 3 7 7             = = =       3 分 故原同余式有解，解数为 2 4 2 2 16 k+ = = 5 分

5.解:013)=12,0(013)=012)=12×1×2=4,故13有4个原根2 令q=2,q2=3,经过验算得13的一个最小原根为2, 分 5,7,11与12互素, 13的全部原根为2=2,2≡6,27=11,2=7(md13)5分 6.解:由于4是16的约数,从上表可知ind13=4, 1分 所以同余式有解,解数为4 原同余式与nd2x≡ind313=4(modl6)同解 2分 解得ind3x≡1,5,9,13(mod16) 分 反查指标表,得解x=10,5,14,12(mod17 5分 四.1.证明:令2表示不超过a的最高次幂,即2a≤a≤2a+, 分 则1++…+的分母必为2“k,k为奇数 2分 2k2-k2%,k % 分 2ak2ak2“k 此时除 k 外均为偶数,故分子和为奇数,而分母和为偶数,故非整数。6分 2.证明:设a1=qm+b,q,b∈Z,i=1,2,…,(m,0≤b≤m-1(b,m)=1 分 Im 4分 ∵(b,m)=1,∴(b,m-b)=1 5分 取S=b+b2+…bm)=(m-b)+(m-b)+…+(m-bam) 6分 整理,得到∑b=m0m),因此s=(m) 8分 第2页共6页

第 2 页 共 6 页 5．解： (13) 12 = ， 1 2 ( (13)) (12) 12 4 2 3   = =   = ，故 13 有 4 个原根 2 分 令 1 2 q q = = 2, 3 ，经过验算得 13 的一个最小原根为 2， 2 分 又∵ 1，5，7，11 与 12 互素， ∴ 13 的全部原根为 1 5 7 11 2 2, 2 6, 2 11, 2 7 (mod 13)     5 分 6．解：由于 4 是 16 的约数，从上表可知 3 ind 13 4 = ， 1 分 所以同余式有解，解数为 4 原同余式与 4 13 4 (mod 16) 3 3 ind x ind  = 同解 2 分 解得 3 ind x 1,5,9,13 (mod 16) ， 3 分 反查指标表，得解 x 10,5,14,12 (mod 17) 5 分 四．1．证明：令 2  表示不超过 a 的最高次幂，即 1 2 2 a  +   ， 1 分 则 1 1 1 2 a + + + 的分母必为 2 k  ， k 为奇数 2 分 1 1 2 2 2 2 3 2 2 2 2 2 k k k k k a k k k k k          − − + + + + 3 分 此时除 2 k k  外均为偶数，故分子和为奇数，而分母和为偶数，故非整数。6 分 2．证明：设 a q m b q b Z i m b m b m i i i i i i i = +  =   − = , , , 1,2, , ( ),0 1,( , ) 1  2 分 ∴ ( ) ( ) ( ) 1 1 1 1 m m m i i i i i i i q m b b s b m m m    = = =     + = = =            4 分 ∵ ( , ) 1 i b m = ，∴ ( , ) 1 i i b m b − = 5 分 取 0 1 2 ( ) 0 1 ( ) ( ) ( ) ( ) m m s b b b m b m b m b = + + = − + − + + −   6 分 整理，得到 ( ) 1 1 ( ) 2 m i i b m m   =  = ，因此 ( ) 2 m s  = 8 分 3．证明：

[1·((P-1)][2·((P-2)…[(-(P--) 8分 ≡(-1)212…(P-1)≡(-1)2(P-1)≡-1 5.证明:(x)f(x)是可乘函数,由可乘定理即得 2分 ∑(d)f(d) 分 +p)八(P )+…+(p)(p)+…+(p2)/2) 因为()-=1(p2)=0p)=1(=12-,故得8分 ∑u(d)fd)=∏(-f(P) 第3页共6页

第 3 页 共 6 页 2 2 2 2 1 1 2 2 1 2 2 1 ( 1) (( )!) 1 2 ( ) 2 2 1 1 [1 ( ( 1))] [2 ( ( 2))] [ ( ( ))] 2 2 ( 1) 1 2 ( 1) ( 1) ( 1)! 1 (mod ) 1 (( )!) ( 1) (mod ) 2 P P p P P P P P P P P P P P P − − + − − =    − −   − −   − −    − −  −    −  − −  − −   − 8 分 5．证明：  ( x f x ) ( ) 是可乘函数，由可乘定理即得 2 分 ( ) ( ) ( ( ) ( ) ( ) ( ) ( ) ( )) 2 2 1 1 i i k i i i i i i i d a a a f f f d f d    p p p p p p  = = + + + + +  5 分 因为 ( ) ( ) ( ) 2 0, 1, 1,2, , i i i i a     p p p i   = = = = − =     ，故得 8 分 | 1 ( ) ( ) (1 ( )) k i d a i  d f d f p =  = − 

2004~2005学年第二学期 科目:初等数论 考试(查)试题B答案 命题教师:李伟勋 使用班级:02数本1,2,3班 1.72.1473. 4.P为素数(P-1)+1=0(modP)5.96 6.3937.18.g与g+p中的单数9.(11)=1010.(a,b,c)|d 二,11.D12.A13.A14.C15.B16.A17.C18.B19.D20 1.解:由于(6,17)=1,而118,所以原方程有解 分 又因为6×3-17×1=1,故有 6×(3×18)-17×(1×18)=18,特解为(54,-18) 所有解为 =54-17t y=-18-g,t=0,±1 分 2.解:∵7=7,9=32,15=3×5,∴m=[7,9,15]=315 1分 ∴原同余式组等价于{x=5(mod9),由孙子定理,得2分 x≡7=2(mod5) M1=45,M2=35,M3=63 M===5(mod7)M2==-1(mod9)M3B=2(mds) 所以x=122(mod315) 分 3.解:3为平方非剩余,由互反律,得2=(-1) 1分 或 ∫P=-1(mod3) P≡1(mod4) IP=-1(mod 4) 3分 由孙子定理,得P=域或-1(mod12),即P=12k±1 5分 4.解:72=2332,且25≡1(mod8), 分 3 故原同余式有解,解数为2+2=23=8 5分 第4页共6页

第 4 页 共 6 页 2004 ～2005 学年第 二 学期 科目: 初等数论 考试（查）试题 B 答案 命题教师：李伟勋 使用班级：02 数本 1，2，3 班 一．1．7 2．147 3． [ ] a b 4．P 为素数  − +  ( 1)! 1 0 (mod ) P P 5．96 6．393 7．1 8．g 与 g p  + 中的单数 9．(11) 10 = 10．( , , ) | a b c d 二．11．D 12.A 13．A 14．C 15．B 16．A 17．C 18．B 19．D 20．A 三．1．解：由于 (6,17) 1 = ，而 1|18 ，所以原方程有解 1 分 又因为 6 3 17 1 1  −  = ，故有 6 (3 18) 17 (1 18) 18   −   = ，特解为 (54, 18) − 3 分 所有解为 54 17 0, 1, 18 6 x t t y t  = −  =   = − − 5 分 2．解： 2 7 7, 9 3 , 15 3 5, [7,9,15] 315 = = =   = = m 1 分 ∴ 原同余式组等价于 3 (mod 7) 5 (mod 9) 7 2 (mod 5) x x x          ，由孙子定理，得 2 分 M M M 1 2 3 = = = 45, 35, 63 ' ' ' 1 2 3 1 1 1 1 1 5 (mod 7) 1 (mod 9) 2 (mod 5) 45 3 35 63 3 M M M      −    所以 x 122 (mod 315) 5 分 3．解：3 为平方非剩余，由互反律，得 1 2 3 3 ( 1) P P P −         = −     ， 1 分 1 (mod 3) 1 (mod 3) 1 (mod 4) 1 (mod 4) P P P P     −        − 或 3 分 由孙子定理，得 P 1 1 (mod 12) 或－ ，即 P k =  12 1 5 分 4．解： 3 2 72 2 3 =  ，且 25 1 (mod 8)  ， 25 1 3     =   3 分 故原同余式有解，解数为 2 3 2 2 8 k+ = = 5 分

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．证明：

1232…(p-2)=[1((P-1)[3·(-(P-3)…(P-2)(-(P-2) P-1 (-1)21.2…(P-1)≡(-1)2(P-1)-1(modP) 所以1232…(p-2)2=(-1) (mod P) 5.证明:(1)(1)=1,故(x)≠0 (2)设若x1,x2分别通过模m1,m2简化剩余系,则m2x1+mx2通过模mm2简化剩余 系,即m2x1+mx2通过9(m1m2)个整数。另一方面由于x1通过(m1)个整数,因此 m2x+m1x2通过φ(m1)9(m2)个整数。故9(m1m2)=9(m1)9(m2)。证完 第6页共6页

第 6 页 共 6 页 2 2 2 1 1 2 2 1 3 ( 2) [1 ( ( 1))] [3 ( ( 3)] ( 2) ( ( 2)) ( 1) 1 2 ( 1) ( 1) ( 1)! 1 (mod ) P P p P P P P P P P − −    −   − −   − −   −  − −  −    −  − −  −  7 分 所以 1 2 2 2 2 1 3 ( 2) ( 1) (mod ) p p P +    −  − 5．证明：（1） (1) 1= ，故 ( ) 0 x  （2）设若 x1，x2 分别通过模ｍ1，ｍ2 简化剩余系，则ｍ2x1+ｍ1x2 通过模ｍ1ｍ2 简化剩余 系，即ｍ2x1+ｍ1x2 通过  （ｍ1ｍ2）个整数。另一方面由于 x1 通过（ｍ1）个整数，因此 ｍ2x1+ｍ1x2 通过  （ｍ1）  （ｍ2）个整数。故  （ｍ1ｍ2）=  （ｍ1）  （ｍ2）。证完