作业

作业

第一章 作业答案 1.7 习题

1 证( 方法一 ) 由2|n，则 n= 2 m，又5|n，则5|2m,由 5| 5m ,则5|(5m – 2·2m)=m ，设m=5k(k为整数),则n = 10k.又由7|n, 则有7|10k , 由7|7k, 则有7|(3·7k - 2·10k) = k ,设k = 7p(p是整数)，则有n=70p, 从而有70|n.

(方法二)因为 2|n , 5|n , 7|n , 且[2 ，5，7]=70 ，根据1.4定理7可得70|n.

(方法三) 因为2|n, 5|n , 7|n , 所以 70|35n , 70|14n , 70 | 10n, 从而有70|(35 – 14 – 2·10)n = n.

4证：三个连续的整数可以写成，(a-1) , a , (a+1), 其中任意两个连续整数中必定有一个是偶数，所以2可以整除它们的乘积，即 2|(a - 1)a(a+1) .又任意整数a可以写成a = 3n+b(b∈Z,1≤b≤3) 当b = 1时，a – 1 =3n ,所以3|(a-1) , 当b=2时，a + 1 = 3n+3 ,所以3|(a+1), 当b=3时，a= 3n,所以3|a .

所以不论b是多少，均有3|(a-1)a(a+1) , 又(2, 3) = 1 ,故6|(a-1)a(a+1).

6 证 (运用1.1定义2或1.1 定理7)

4，设p是正整数n的最小素因数，证明：若 p＞n

13，则n/p是素

数。证明：假设n/p不是素数，则n/p为合数，设其一个素因数为x。 由p是正整数n的最小因数，可知 p＜n，而p＞n可得 p2＞n/p＞p 由x为n/p的一个素因数， 则 n/p＞x 而 p＞n/p 即有p＞x

说明存在一个比p还小的素因数 与p是正整数n的最小素因数 矛盾 则 假设不成立 即 n/p是素数

12 证明形如3k-1形式的正整数必有同样形式的素因数.

证(解析：任意整数可表示为3k-1 或3k 或3k+1 ,其中为素因数形式只能为3k – 1 或 3k+1 的形式)假设形如3k -1 的正整数只有3m +1 形式的素因数，那么3k-1 = (3m1 +1 )(3m2 +1)…(3ms +1)=3m+1 其中mi ∈Z ,i=1,2,…,s .m是mi 的整系数多项式，故m是一个整数，可推出3k – 1 = 3m + 1,这是矛盾的. 14 证明形如6k+5的素数有无穷多个.

证明：∵形如6k-1的正整数的素因数必是形如6k-1的形式的，否则，它的所有素因数都是形如6k+1，即有形如6k+1的素数的乘积

p1p2p3p413

……pn=6x+1 ，与6k-1矛盾。

∴形如6k-1的正整数的素因数必是形如6k-1的形式的 假设形如6k+5的素数只有有限个p1 ,…,ps ，令

a = 6p1 …ps + 5 因为n>pi ,i=1,…,s，所以a一定是合数，(注：否则a是大于pi的素数)，根据1.1定理6 ，a的大于5的最小正因数p是素数，因此，p是p1 ,…,ps 中的某一个,即存在j，1≤j≤s， 使得p=pj ,根据1.1定理3，我们有p|a-6p1 …ps =5,这与p>5是矛

盾的，故存在有形如6k+5的素数有无穷多个.

方法二 反证法.假设形如6k+5的素数只有有限个，可设为p1 ，p2 ，…， ps ，令 a = 6p1 … ps + 5 ，则 pi a ， i=1，…，s. 所以有 ，a 是异于p1 ，p2 ，…， ps 的

形如6k+5 的素因数. 这与形于6k+5的素数只有p1 ，p2 ，…， ps 有限个矛盾. 故形如6k+5的素数有无限多个. 17 答案：(111100011110101)2 =(78F5)16 , (10111101001110)2 =(2F4E)16

18 答案：(ABCDEFA)16 = (1010101111001101111011111010)2 (DEFACEDA)16 = (11011110111110101100111011011010)2 (9A0AB)16 =(10011010000010101011)2 29 答案 ：(2t – 1 ,2t + 1)=1 ; (2n ,2(n+1))=2. 32 答案：( 1613 ,3589) = 1 , 551×3589 – 1226×1613=1 (2947 , 3772)= 1 , 951 ×2947 – 743×3772 = 1 33答案：(70 , 98 , 105) = 7 整系数线性组合不唯一 7= 24×70 – 16×98 – 105 =105 +14×98 – 21×70 =0×70 + 105 – 98 = … 34 证明：

不妨设 m≥n ,由带余数除法得 m = qn + r 0≤r

则有

a?1?a?1?a?a?a(a?1)?a?1

qnnq(n?1)由于a?1?(a?1)(a???1)

nan由此及a?1|a?1得

mnnr(a?1,a?1)?(a?1,a?1)

mqn?rrrrqnr又(m ,n) = (n , r).若r = 0,则(m , n) = n 结论成立. 若r > 0则继续对

(a?1,a-1)作同样的讨论.

nr由辗转相除法知，结论成立. 51 略

62求9x + 24y -5z = 1000 的一切整数解. 解：(说明：这里只需要求出一组解即可)

因为(9 , 24 ,5)=1 ,则1 = 24 – 2·9 -5 所以存在 x = -2000 , y = 1000 , z = 1000使得9x + 24y -5z = 1000 或者 1 = 6·9 -2·24 -5 所以存在

X= 6000 ,y = -2000 ,z = 1000使得9x + 24y -5z = 1000 可以有多解.

第二章作业

1.（1）写出摸9的一个完全剩余系，它的每个数是奇数。 （2）写出模9的一个完全剩余系，它的每个数是偶数。 解：Ca?{a?9k,k?Z} a=0，1，2，3，4，5，6，7，8

∴模9的一个全部都为奇数的完全剩余系为：9，19，11，21，13，

23，15，25，17

模9的一个全部都为偶数的完全剩余系为：0，10，2，12，4，14，6，16，8

2.证明：当m>2时02,12,...,(m?1)2一定不是模m的完全剩余系。 证明：∵(m?1)2?m2?2m?1?m(m?2)?1 ∴(m?1)2?1(modm)

也就是说(m?1)2和1在同一个剩余类中 ∴02,12,...,(m?1)2一定不是模m的完全剩余系

6.2003年5月9日是星期五，问第220080509天是星期几？ 解：∵23mod7?1

又 220080509mod7?(23)6693503mod7?1 ∴第220080509天是星期六

16.计算：232(mod 47)，247(mod 47)，2200(mod 47) 解：（1）232(mod 47)

(32)D?(100000)B i=0，1，2，3，4，5

a0?2,b0?20(mod47)?1

a1?22(mod47)?4,b1?1?a10(mod47)?1

0a2?42(mod47)?16,b2?1?a2(mod47)?1 0a3?162(mod47)?21,b3?1?a3(mod47)?1

由模重复平方法，令n=23，b=312，令a=1，将13写成二进制 13=1+22+23

（1）n0=1 ，a0=a*b≡13，b1≡b2≡8（mod23） （2）n1=0 ，a1= a0≡13， b2≡b12≡18（mod23） （3）n2=1 ，a2=a1*b2≡4，b3≡b22≡2（mod23） （4）n3=1 ，a3= a2*b3≡8（mod23） 类似的，我们有

b2≡31213≡4（mod29） 再令m1=23，m2=29，m=m1*m2=667 M1=m2=29，M2=m1=23 分别求解同余式

29M1'≡1（mod23） 23M2'≡1（mod29） 得到M1'=4 M2'=-5

X≡4*29*8-5*23*4≡468（mod667）

14.计算21000000（mod1309） 解：1309=7*11*17

2?(7)≡26≡1（mod7）b1≡21000000≡(26)166666*24≡2（mod7） 2?(11)≡210≡1（mod11）b2≡21000000≡(210)100000≡1（mod11） 2?(17)≡216≡1（mod17）b3≡21000000≡(216)62500≡1（mod17）

令m1=7，m2=11，m3=17，m=m1*m2*m3=1309

M1=m2*m3=187 M2=m1*m3=119 M3=m1*m2=77

187M1'≡1(mod7) 119M2'≡1(mod11) 77M3'≡1(mod17) 得M1'=3 M2'=5 M3'=2

X≡3*187*2+5*119*1+2*77*1≡1122+595+154≡562（mod1309）

Q ` 88888888888888，47

的二次剩余和二次非剩余。

解：37的二次剩余是1，3，4，7，9，10，11，12，16，25，26，27，28，30，33，34，35，36

二次非剩余是2，5，6，8，13，14，15，17，18，19，20，21，22，23，24，29，31，32

47的二次剩余是1，2，3，4，6，7，8，9，12，14，16，17，18，21，24，25，27，28，32，34，36，37，42

二次非剩余是5，10，11，13，15，19，20，22，23，26，29，30，31，35，38，39，40，41 。

1， 求满足方程E：y 2=x3+5x+1（mod 7）的所有点。 解：对x=0，1，2，3，4，5，6，分别求出y x=0时，y 2=1（mod 7），y=1，6（mod 7）， x=1时，y 2=0（mod 7），y=0（mod 7）， x=2时，y 2=5（mod 7）， 无解，

x=3时，y 2=1（mod 7），y=1，6（mod 7），

x=4时，y 2=1（mod 7），y=1，6（mod 7）， x=5时，y 2=4（mod 7），y=2，5（mod 7）， x=6时，y 2=3（mod 7）， 无解。 2， 计算下列勒让德符号：

(1）.（17/37）=(-1) (17-1)(37-1)/(2*2)*(37/17)=-1

（2）. （151/373）=(-1)(151-1)(373-1)/(2*2)*(373/151)=(2*151+71/151) =(71/151)=(-1) (71-1)(151-1)/(2*2)*(151/71) =(-1)*(9/71)= (-1)* (-1) (9-1)(71-1)/(2*2)*(71/9) =(-1)*(-1/9)= (-1)* (-1) (9-1)/2=-1

(3)（191/397）=(-1）(191-1)(397-1)/(2*2) *(397/191)=(2*191+15/191) =15/191=(-1)(191-1)(15-1)/(2*2) *(191/15) =(-1)*(12*15+11/15)=(-1)*(-1/15)*(2/15)2 =(-1)*(-1) (15-1)/2*(-1) 2*(15-1)/8=1 4,判断下列同余方程是否有解。

（1）.因为（7/227）=(-1) (227-1)(7-1)/(2*2)*(227/7)=（-1）*（ 7*32+3/7） =(-1)*(3/7)=(-1)*(-1) (3-1)(7-1)/(2*2)(7/3) =(3*2+1/3)=(1/3)=1 所以,7是227的二次剩余 所以,x2≡7(mod227)有解

(2) x 2≡11(mod 511)

解：11/511=(-1) (511-1)(11-1)/(2*2)*(511/11)=(-1)*(46*11+5/11)

=(-1)* (5/11)= (-1)* (-1) (11-1)(5-1)/(2*2)*(11/5) =(-1)*(2*5+1/5)=(-1)*(1/5)=-1 所以，11不是511的二次剩余 所以，x 2≡11(mod 511)无解。

4.求所有素数p使得5为模p的二次剩余。

解：由题意，（5/p）=1

(5/p）=(-1) (5-1)(p-1)/(2*2) *(p/5)= (p/5) 而(p/5)=1，p≡?1（mod 5） (p/5)=-1，p≡?2（mod 5）

因此，使(p/5)=1的全体素数为p≡?1（mod 5）。

5.利用定理2判断：

（1）-8是不是模53的二次剩余

解：（-8/53）=(-1/53)*(2/53)* (2/53)* (2/53) =(-1) (53-1)/2*(-1) 3*(53*53-1)/8=-1 所以。-8不是53的二次剩余。 （2）8是不是67的二次剩余

解：8/67=(2/67)*(2/67)*(2/67)=(-1)3*(67*67-1)/8=-1 所以，8不是模67的二次剩余。 第五章作业 1、2，5，10（mod 13）的指数 解：（1）2（mod 13）

12的正因数为1，2，3，4，6，12 所以

（2）5（mod 13）

12的正因数为1，

所以

（3）10（mod 13）

12的正因数为1，

所以

2、3，7，10（mod 19） 解：（1）3（mod 19）

12的正因数为1， 所以

（2）7（mod 19）

12的正因数为1，

2，3，4，2，3，4，2，3，6，2，3，6，6，12 6，12 9，18 9，18

所以

（3）10（mod 19）

12的正因数为1，2，3，6，9，18 所以

3、81的所有原根 解： 因为 所以

即2为81 的一个原根 所以81有 即所有

个原根 为81的原根,k

K=1，5，7，11，13，17，19，23，25，29，31，35，37，41，43，47，49，53

81 的原根为2，32，47，23，11，14，56，5，20，77，65，68，29，59，74，50，38，41 4、证明：因为同的形式

=40=，不与2，4，,(p为奇素数)有相

所以55没有原根 5、解：47的原根个数为 因为 所以

即5为47的一个原根 即所有

为47的原根,k

K=1，3，5，7，9，11，13，15，17，19，21，25，27，29，31，33，35，37，39，41，43，45

47的原根为5，31，23，11，40，13，43，41，38，10，15，22，33，26，39，35，29，20，30，45，44，19

6、解：59的原根个数为 因为 所以

即2为59的一个原根 即所有

为59的原根,k

K=1，3，5，7，9，1，13，15，17，19，21，23，25，27，

31，33，35，37，39，41，43，45，47，49，51，53，55，57

59的原根为2，8，32，10，40，42，50，23，33，14，56，

47，11，44，55，43，54，39，38，34，18，13，52，31，6，24，37，30

16、解：因为（n，）=（22，40）=2

又由查表得ind 5=22 2|22所以原同余式有解

由已知得22ind x≡ind 5（mod 40） 即22ind x≡22（mod 40） 11ind x≡11（mod 20） ind x≡1（mod 20） 所以ind x=1，21 即x= 6，35

17、解：因为（n，

）=（22，40）=2

又由查表得ind 29=7

2不能整除7所以原同余式没有解

附加题：求98的原根

解：因为98=2*因此有原根

因为2是7的原根，而且2+7是49的原根 又因为9为奇数，所以9为98的原根 所以98有 98的原根为 即，，

=12个原根 k{k|（k，

，

，

，

，

，

，

）=1} ，

，

，

本文来源：https://www.bwwdw.com/article/jaba.html