初等数论考试试卷
一、单项选择题:(1分/题×20 题=20分)
1.设 x为实数,x 为 x 的整数部分,则( A )
A.x x x 1 ;B.x x x 1;
C.x x x 1 ;D.x x x 1.
2.下列命题中不正确的是( B )
A.整数 a1, a2, ,a n 的公因数中最大的称为最大公因数;
C.整数a与它的绝对值有相同的倍数
D.整数a与它的绝对值有相同的约数
3.设二元一次不定方程 ax by c(其中 a,b, c是整数,且 a,b 不全为零)有一整数解x0,y0,d a,b ,则此方程的一切解可表为( C )
ab
A. x x0 t,y y0 t,t 0, 1, 2, ;
dd
ab
B. x x0 t,y y0 t,t 0, 1, 2, ;
dd
ba
C. x x0 t,y y0 t,t 0, 1, 2, ;
dd
ba
D. x x0 t,y y0 t,t 0, 1, 2, ;
dd
4.下列各组数中不构成勾股数的是(D)
A.5,12,13;B.7
,
24,
25;
C.3,4,5;D.8
,
16,17
5.下列推导中不正确的是
(D)
A.a1 b1 modm ,a2 b2 modm a1 a2 b1 b
2 modm ;
B.a1 b1 modm ,a2 b2 modm a1a2 b1b
2modm ;
C.a1 b1 modm a1a2 b1a
2 modm ;
D.a12b12modm a1 b1 modm .
6.模10 的一个简化剩余系是( D )
A. 0,1,2, ,9; B. 1,2,3, ,10;
C. 5, 4, 3, 2, 1,0,1,2,3,4; D. 1,3,7,9.
7. a b modm 的充分必要条件是 ( A )
A. ma b; B. a b m; C. ma b;
D. a b m.
8.设 f x x 4
2x 3
8x 9 ,同余式 f x 0 mod5 的所有解为 ( C )
A. x 1或 1; B. x 1或 4; C. x 1 或 1 mod5 ; D.无解.
9、设f(x)= a n x n
a 1x a 0其中a i 是奇数,若x x 0 modp 为f(x) 0 modp 的一个解,
则:( ? )
A . mod p 一 定为 f (x) 0 mod p , 1的一个解
B .
mod p , 1,一定为 f (x) 0 mod p 的一个解
C .当p 不整除f ( x)时, f ( x) 0 modp 一定有解 x x 0 modp ,其中x x 0 modp
D . 若x x 0 mod p 为f(x) 0 mod p 的一个解 ,则有x x 0 mod p 10.设f (x) a n x n
a 1x a 0,其中a i 为奇数,a n 0 mod p ,n p,则同余式
f (x) 0 modp 的解数 :( )
A .有时大于 p 但不大于 n;
B .不超过 p
C .等于 p
D .等于 n
11.若 2为模 p 的平方剩余,则 p 只能为下列质数中的 :( D )
2
A .同余式x 2
a modm 一定有解 ,
B .当 a,m 1时,同余式 x 2
a modp 有解 ;
A . 3 C .13 ( C )
D .23
B .11 12.若雅可比符
号
C .当m p(奇数)时,同余式x 2
a modp 有解 ;
D .当a p(奇数)时,同余式x 2
a modp 有解 .
13.若同余式 x 2
a mod2 , 3, 2,a 1有解 ,则解数等于 ( A )
A .ind 32 2
B . ind 32 3
C . ind 35 0
D . ind 310 ind 32 ind 35
17.下列函数中不是可乘函数的是: ( C ) A .茂陛鸟斯 (mobius)函数 w(a) ; B .欧拉函数 a ;
C .不超过 x 的质数的个数 x ;
D .除数函数 a ;
18.若 x 对模m 的指数是 ab , a >0, ab >0,则 a
对模 m 的指数是 ( B ) A . a
B .b
C . ab
D .无法确定
19.
f a ,
g a 均为可乘函数,则 ( A )
fa
A . f a g a 为可乘函数;
B . 为可乘函数 ga
C . f a g a 为可乘函数;
D . f a g a 为可乘函数
20.设 a 为茂陛乌斯函数,则有 ( B )不成立 A . 1 1
B .
1 1 C .
2 1 D . 9 0
二.填空题:(每小题 1 分,共 10分)
A . 43 C . 2 D . 1
14. 模 12 的所有可能的指数为: ( A )
A . 1, 2,4
B . 1,2,4, 6,12
C . 12, 3,4, 6,12
D 15.
若模 m 的原根存在, 下列数
中, m 不 可能等于: (
D )
A 2
B . 3
C . 4
D .
12
16.对于模 5,下列式子成立的是 ( B ) 无法确定
21. 3 在45!中的最高次n= ___ 21 _____;
22.多元一次不定方程: a1x1 a2x2 a n x n N ,其中 a1 ,a2 ,?,a n ,N 均为整数,
设 x x 0 modm 为一次同余式 ax b modm ,a 0 modm 的一个解, 则它的所有
确?正确请证明,不正确请举反例。
33.求模 17 的简化剩余系中平方剩余与平方非剩余。
34.设 a p 11
p 22
p k k
为a 的标准分解式, 记 S a 为a 的正因数的和, a 为 a 的正因数的
个数,则 S a =? a =? 为什么? 四.计算题。( 7 分/题 ×4 题= 28 分) 35. 求不定方程 6x+93y=75 的一切整数解。
x 1 mod5
36. 解同余方程组 y 3 mod6
z 2 mod7
37.解同余式 x 2
≡11(mod125) 38.求模 13 的所有原根。
五、证明题:( 7分/题×2题=14 分)
23. n 2 ,有整数解的充分必要条件是
24. 26.
勒让德符号 503
1013
31.
简答题:( 5分/题× 4 题=20 分) 命题“任意奇数的平方减 1 是 8 的倍数 对吗?说明理由。
32. 若 a,m 1, x 通过模 m 的简化剩余系,则 ax 也通过模 m 的简化剩余系 ”这命题是否正
a
有理数 , 0 a b , b
25
.
1
27
.
28
.
29
.
30
.
39、试
x12 2y2 z2,(x,y)=1,y 是偶数的整数解可写成:
证:
2 2 2 2
x (a2 2b2) y 2ab z a 2 2b2
这里a b 0 ,a,b 1,并且一为奇数,一为偶数
a
40、设 a 为正整数,试证:(d) ( ) a
d|a d|a d
其中表示展布在 a 的一切正因数上的和式。
d|a
六、应用题:( 8 分)
41、求30!中末尾0 的个数。
参考答案
一.单项选择:ABCDD ;DACCB ;DCAAD ;BCBAB 。
二.填空题:21.21;22.a1,a2, ,a n | N ;23.b,10 1;24.x0 t m,t 0, 1, 2, ;
a,m
25.p 1 !+1 0 modp ,p 为素数;26.1;
p1
27.a 21 modp ;28.m ;29.g与 g p 中的单数;30.16
2
三.简答题:31.答:命题正确。2m 1 1 2m 1 1 2m 1 1
2m 2m 2 4m m 1 而m m 1 必为 2 的倍数。
86页
32.正确.证明见教材 P47 。
33 .在摸 p 的简化剩余系中与 12,2 2, , p 1同余的数是数 p 的平方剩余,
1 2 2 2 2 2 2 2 2
p 17, p 1 8 ,121,224,329,4216 ,528,622,7215,8213 2
故1,2,4,8,9,13,15,16为摸17的平方剩余,而3,5,6,7,10,11,12,14为摸17 的平方非剩余。
kk
34.s a 1 p i p i2p i i
i 1 i1
2
a 1 1 2 1 k 1
k
证明:若f a 为可乘函数,则 f 1 f p i f p i i.
|a i 1
分别令f a a. f a 1,它们为可乘
p i 1
函数,即得出。
四.计算题
35.解:因为6,93 3| 75 ,故原不定方程有解。
又原方程即 2x 31y 25 ,而易见方程 2x 31y 1有解
x0 16, y0 1 。所以原方程的一个解是 x0400, y025
所以,原方程的一切整数解是:
x 400 31t t 是整数
r 25 2t
36.解:因为模5,6,7 两两互质,由孙子定理得所给同余方程组关于模5×6×7=210 有唯一解,分别解同余方程:
42x 1 mod5 ,35x 1 mod6 ,30x 1 mod7 ,得
x 3 mod5 ,x 1 m o d 6,x 4 mod7 因此所给同余方程组的解是:
x 42 3 1 35 1 3 30 4 2 mod210
即:x 261 51 mod210
37.解:从同余方程x211 mod5 得x 1 mod5 ,
2
再从 1 5t1 211 mod5 2,得10t1 10 mod52,
2
因此t1 1 mod5 ,于是1 t1 6 mod5 2,
是2 11 mod52的解,又从 6 52t22 11 mod53
3
得 300t2 25 mod5 3 ,因此12t2 1 mod5
即t2 2 mod5 ,所以x 6 522 56是所给方程的一个解,于是所解为:
x 56 m od 1 2解5毕。
38.解: 13 12 22
3, g 1 2,g 2 3 为其质因数
213
6, 313
4,故 g 为模 13的原根的主要条件是:
证明题: 39.证明:易验证所给的解为原方程的解,因 z x z x r 2 2 2
而 ,所以( z x
, z x
) =1
22
由书中引理,我们可假设
z x 2 z x 2 = a , =b
22
显然 a >b , (a , b )=1 , 于是
2 2 2 2
X= a 2 -b 2 , z=a 2+b 2
, y=2 ab
因子为奇数,所以 a ,b 一定是一为奇,一为偶,证毕
40.证明:假定 d 1 ,---, d k 为a 的所有正约数,那末
a
, --- , a
也是 a 的所有正约数,于是 d 1 d k
(d)= (a
) d a da d
再因为在 a 的完全剩余系中任一数 a 的最大公约数
64
g 1 mo d1,
3 g
1 mod13
用 g=1,2,?? 12 逐一验证,得: 2, 6, 7, 11为模 13 的原
根,
因为 12 4,故模 13 原根只有 4 个, 即为所
求。 zx
z x
| z
xz 2, 2|
2 2
但
x
z z x
,
z x
|
z xz 2, 2|
2 ,
2 x
x 五、
y 为偶数,原方程可化为:
大公约数为 d i 的数有 (m
) ,所以:
d
i
(m
)
= m d a d
六.应用题:
=15+7+3+1+0=26
10=2×5,故 30!的末尾有 7 个零。
必定是 d 1 ,
-
d k 中某一个数,而完全剩余系中与 a 的最
41.解: 5 在 30!中的最高次幂 30 30 30
2 在 30 !的最高次
幂
=6+1+0=7
证毕
初等数论练习题一 一、填空题 1、τ(2420)=27;?(2420)=_880_ 2、设a ,n 是大于1的整数,若a n -1是质数,则a=_2. 3、模9的绝对最小完全剩余系是_{-4,-3,-2,-1,0,1,2,3,4}. 4、同余方程9x+12≡0(mod 37)的解是x ≡11(mod 37)。 5、不定方程18x-23y=100的通解是x=900+23t ,y=700+18t t ∈Z 。. 6、分母是正整数m 的既约真分数的个数为_?(m )_。 7 8、??? ??10365 =-1。 9、若p 是素数,则同余方程x p - 1 ≡1(mod p )的解数为二、计算题 1、解同余方程:3x 2+11x -20≡0 (mod 105)。 解:因105 = 3?5?7, 同余方程3x 2+11x -20≡0 (mod 3)的解为x ≡1 (mod 3), 同余方程3x 2+11x -38 ≡0 (mod 5)的解为x ≡0,3 (mod 5), 同余方程3x 2+11x -20≡0 (mod 7)的解为x ≡2,6 (mod 7), 故原同余方程有4解。 作同余方程组:x ≡b 1 (mod 3),x ≡b 2 (mod 5),x ≡b 3 (mod 7), 其中b 1 = 1,b 2 = 0,3,b 3 = 2,6, 由孙子定理得原同余方程的解为x ≡13,55,58,100 (mod 105)。 2、判断同余方程x 2≡42(mod 107)是否有解? 11074217 271071107713231071107311072107 710731072107732107422110721721107213)(=∴-=-=-==-=-=-==??≡-?--?-)()()()(),()()()(),()())()(( )(解: 故同余方程x 2≡42(mod 107)有解。 3、求(127156+34)28除以111的最小非负余数。
1 浙江省2018年4月高等教育自学考试 初等数论试题 课程代码:10021 一、单项选择题(本大题共5小题,每小题2分,共10分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.20被-30除的余数是( ) A .-20 B .-10 C .10 D .20 2.176至545的正整数中,13的倍数的个数是( ) A .27 B .28 C .29 D .30 3.200!中末尾相继的0的个数是( ) A .49 B .50 C .51 D .52 4.从以下满足规定要求的整数中,能选取出模20的简化剩余系的是( ) A .2的倍数 B .3的倍数 C .4的倍数 D .5的倍数 5.设n 是正整数,下列选项为既约分数的是( ) A . 3144 21++n n B . 121 -+n n C .2 512+-n n D .1 31++n n 二、填空题(本大题共10小题,每小题3分,共30分) 请在每小题的空格中填上正确答案。错填、不填均无分。 1.d(120)=___________。 2.314162被163除的余数是___________。 3.欧拉定理是___________。 4.同余方程3x ≡5(mod13)的解是___________。 5.不定方程10x-8y=12的通解是___________。
2 6.ο ___________)1847 365 ( = 7.[-π]=___________。 8.为使n-1与3n 的最大公因数达到最大的可能值,则整数n 应满足条件___________。 9.如果一个正整数具有21个正因数,问这个正整数最小是___________。 10.同余方程x 3+x 2-x-1≡0(mod 3)的解是___________。 三、计算题(本大题共4小题,每小题10分,共40分) 1.解同余方程组 ???? ?? ?≡≡≡≡) 9(mod 4)7(mod 32)4(mod 23) 25(mod 1x x x x 2.解不定方程15x+10y+6z=19。 3.试求出所有正整数n ,使得2n -1能被7整除。 4.判断同余方程 x 2≡-1457(mod 2389) 是否有解? 四、证明题(本大题共2小题,每小题10分,共20分) 1.证明形如4n+3的素数有无穷多个。 2.证明不定方程 x 2+y 2+z 2=x 2y 2 没有正整数解。
初等数论试卷一 一、 单项选择题:(1分/题×20题=20分) 1.设x 为实数,[]x 为x 的整数部分,则( ) A.[][]1x x x ≤<+; B.[][]1x x x <≤+; C.[][]1x x x ≤≤+; D.[][]1x x x <<+. 2.下列命题中不正确的是( ) A.整数12,,,n a a a 的公因数中最大的称为最大公因数; B.整数12,, ,n a a a 的公倍数中最小的称为最小公倍数 C.整数a 与它的绝对值有相同的倍数 D.整数a 与它的绝对值有相同的约数 3.设二元一次不定方程ax by c +=(其中,,a b c 是整数,且,a b 不全为零)有一整数解 ()00,,,x y d a b =,则此方程的一切解可表为( ) A.00,,0,1,2,;a b x x t y y t t d d =- =+ =±± B.00,,0,1,2, ;a b x x t y y t t d d =+= -=±± C.00,,0,1,2, ;b a x x t y y t t d d =+= -=±± D.00,,0,1,2, ;b a x x t y y t t d d =-= -=±± 4.下列各组数中不构成勾股数的是( ) A.5,12,13; B.7,24,25; C.3,4,5; D.8,16,17 5.下列推导中不正确的是( ) A.()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ B.()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ C.()()111212mod mod ;a b m a a b a m ≡?≡ D.()()112 2 11mod mod .a b m a b m ≡?≡ 6.模10的一个简化剩余系是( ) A.0,1,2, ,9; B.1,2,3,,10;
第三章 同 余 §1 同余的概念及其基本性质 。,所有奇数;所有偶数,例如,。 不同余,记作:对模则称;若所得的余数不同,同余,记作:对模则称所得的余数相同,与去除两个整数,称之为模。若用设)2(mod 1)2(mod 0)7(mod 18)(mod ,)(mod ,≡≡≡≡/≡∈+a a m b a m b a m b a m b a b a m m Z 定义1。 故同余关系是等价关系;(传递性),则,、若;(对称性) ,则、若;(反身性) 、:关系,它具有下列性质同余是整数之间的一种)(mod )(mod )(mod 3)(mod )(mod 2)(mod 1m c a m c b m b a m a b m b a m a a ≡≡≡≡≡≡ 。 则,,,设。 ,,即同余的充分必要条件是对模整数)(|)()(mod ,0)(|,2121212211b a m q q m b a r r m b a m r r r mq b r mq a t mt b a b a m m b a -?-=-?=?≡<≤+=+=∈+=-证明定理1Z 。 ,则若; ,则,若)(mod )(mod )2()(mod )(mod )(mod )1(21212211m b c a m c b a m b b a a m b a m b a -≡≡++≡+≡≡性质1 。 ,则特别地,若; ,则,若)(mod )(mod )(mod )(mod )(mod 21212211m kb ka m b a m b b a a m b a m b a ≡≡≡≡≡性质2 。 ,则, ;特别地,若则 ,,,若)(mod ,,2,1,0)(mod )(mod ,,2,1)(mod )(mod 0110111111 111 111m b x b x b a x a x a n i m b a m y y B x x A k i m y x m B A n n n n n n n n i i k k i i k k k k k k k k +++≡+++=≡≡ =≡≡----∑∑ΛΛΛΛΛΛΛΛΛΛΛΛαααααααααααααααα定理2。,则,,,若)(mod )(mod 1),(1111m b a m b a m d d b b d a a ≡≡===性质3
《初等数论》期末练习二 一、单项选择题 1、=),0(b ( ). A b B b - C b D 0 2、如果1),(=b a ,则),(b a ab +=( ). A a B b C 1 D b a + 3、小于30的素数的个数( ). A 10 B 9 C 8 D 7 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C (mod )ac bc m ≡/ D b a ≠ 5、不定方程210231525=+y x ( ). A 有解 B 无解 C 有正数解 D 有负数解 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 7、如果a b ,b a ,则( ). A b a = B b a -= C b a ≥ D b a ±= 8、公因数是最大公因数的( ). A 因数 B 倍数 C 相等 D 不确定 9、大于20且小于40的素数有( ). A 4个 B 5个 C 2个 D 3个 10、模7的最小非负完全剩余系是( ). A -3,-2,-1,0,1,2,3 B -6,-5,-4,-3,-2,-1 C 1,2,3,4,5,6 D 0,1,2,3,4,5,6 11、因为( ),所以不定方程71512=+y x 没有解. A [12,15]不整除7 B (12,15)不整除7 C 7不整除(12,15) D 7不整除[12,15] 12、同余式)593(mod 4382≡x ( ). A 有解 B 无解 C 无法确定 D 有无限个解 二、填空题 1、有理数 b a ,0,(,)1a b a b <<=,能写成循环小数的条件是( ). 2、同余式)45(mod 01512≡+x 有解,而且解的个数为( ). 3、不大于545而为13的倍数的正整数的个数为( ). 4、设n 是一正整数,Euler 函数)(n ?表示所有( )n ,而且与n ( )的正整数的个数. 5、设b a ,整数,则),(b a ( )=ab . 6、一个整数能被3整除的充分必要条件是它的( )数码的和能被3整除. 7、+=][x x ( ). 8、同余式)321(mod 75111≡x 有解,而且解的个数( ). 9、在176与545之间有( )是17的倍数.
第五章同余方程 本章主要介绍同余方程的基础知识,并介绍几类特殊的同余方程的解法。 第一节同余方程的基本概念 本节要介绍同余方程的基本概念及一次同余方程。 在本章中,总假定m是正整数。 定义1设f(x) = a n x n a1x a0是整系数多项式,称 f(x) 0 (mod m) (1)是关于未知数x的模m的同余方程,简称为模m的同余方程。 若a n≡/0 (mod m),则称为n次同余方程。 定义2设x0是整数,当x= x0时式(1)成立,则称x0是同余方程(1)的解。凡对于模m同余的解,被视为同一个解。同余方程(1)的解数是指它的关于模m互不同余的所有解的个数,也即在模m的一个完全剩余系中的解的个数。 由定义2,同余方程(1)的解数不超过m。 定理1下面的结论成立: (ⅰ) 设b(x)是整系数多项式,则同余方程(1)与 f(x) b(x) b(x) (mod m) 等价; (ⅱ) 设b是整数,(b, m) = 1,则同余方程(1)与 bf(x) 0 (mod m) 等价; (ⅲ) 设m是素数,f(x) = g(x)h(x),g(x)与h(x)都是整系数多项式,又设x0是同余方程(1)的解,则x0必是同余方程 g(x) 0 (mod m) 或h(x) 0 (mod m)
的解。 证明 留做习题。 下面,我们来研究一次同余方程的解。 定理2 设a ,b 是整数,a ≡/0 (mod m )。则同余方程 ax b (mod m ) (2) 有解的充要条件是(a , m )b 。若有解,则恰有d = (a , m )个解。 证明 显然,同余方程(2)等价于不定方程 ax my = b , (3) 因此,第一个结论可由第四章第一节定理1得出。 若同余方程(2)有解x 0,则存在y 0,使得x 0与y 0是方程(3)的解,此时,方程(3)的全部解是 ??? ????-=+=t m a a y y t m a m x x ),(),(00,t Z 。 (4) 由式(4)所确定的x 都满足方程(2)。记d = (a , m ),以及 t = dq r ,q Z ,r = 0, 1, 2, , d 1, 则 x = x 0 qm r d m x r d m +≡0(mod m ),0 r d 1。 容易验证,当r = 0, 1, 2, , d 1时,相应的解 d m d x d m x d m x x )1(20000-+++,,,,Λ 对于模m 是两两不同余的,所以同余方程(2)恰有d 个解。证毕。 在定理的证明中,同时给出了解方程(2)的方法,但是,对于具体的方程(2),常常可采用不同的方法去解。 例1 设(a , m ) = 1,又设存在整数y ,使得a b ym ,则 x a ym b +(mod m ) 是方程(2)的解。 解 直接验算,有 ax b ym b (mod m )。
初等数论考试试卷 一、 单项选择题:(1分/题×20题=20分) 1.设x 为实数,[]x 为x 的整数部分,则( A ) A.[][]1x x x ≤<+; B.[][]1x x x <≤+; C.[][]1x x x ≤≤+; D.[][]1x x x <<+. 2.下列命题中不正确的是( B ) A.整数12,, ,n a a a 的公因数中最大的称为最大公因数; < B.整数12,,,n a a a 的公倍数中最小的称为最小公倍数 【有最小的吗】 C.整数a 与它的绝对值有相同的倍数 D.整数a 与它的绝对值有相同的约数 3.设二元一次不定方程ax by c +=(其中,,a b c 是整数,且,a b 不全为零)有一整数解 ()00,,,x y d a b =,则此方程的一切解可表为( C ) A.00,,0,1,2,;a b x x t y y t t d d =- =+=±± B.00,,0,1,2, ;a b x x t y y t t d d =+=-=±± C.00,,0,1,2, ;b a x x t y y t t d d =+=-=±± D.00,,0,1,2, ;b a x x t y y t t d d =-=-=±± ( 4.下列各组数中不构成勾股数的是( D ) A.5,12,13; B.7,24,25; C.3,4,5; D.8,16,17 5.下列推导中不正确的是( D ) A.()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ B.()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ C.()()111212mod mod ;a b m a a b a m ≡?≡
第三次作业答案: 一、选择题 1、整数5874192能被( B )整除. A 3 B 3与9 C 9 D 3或9 2、整数637693能被(C )整除. A 3 B 5 C 7 D 9 3、模5的最小非负完全剩余系是( D ). A -2,-1,0,1,2 B -5,-4,-3,-2,-1 C 1,2,3,4,5 D 0,1,2,3,4 4、如果)(mod m b a ≡,c 是任意整数,则(A ) A )(mod m bc ac ≡ B b a = C ac T )(m od m bc D b a ≠ 二、解同余式(组) (1))132(mod 2145≡x . 解 因为(45,132)=3|21,所以同余式有3个解. 将同余式化简为等价的同余方程 )44(mod 715≡x . 我们再解不定方程 74415=-y x , 得到一解(21,7). 于是定理4.1中的210=x . 因此同余式的3个解为 )132(mod 21≡x , )132(mod 65)132(mod 3 13221≡+ ≡x , )132(mod 109)132(mod 3132221≡?+≡x . (2))45(mod 01512≡+x 解 因为(12,45)=3|15,所以同余式有解,而且解的个数为3. 又同余式等价于)15(mod 054≡+x ,即y x 1554=+. 我们利用解不定方程的方法得到它的一个解是(10,3), 即定理4.1中的100=x . 因此同余式的3个解为 )45(mod 10≡x ,
)45(mod 25)45(mod 3 4510≡+≡x , )45(mod 40)45(mod 3 45210≡?+≡x . (3))321 (m od 75111≡x . 解 因为(111,321)=3|75,所以同余式有3个解. 将同余式化简为等价的同余方程 )107(mod 2537≡x . 我们再解不定方程 2510737=+y x , 得到一解(-8,3). 于是定理4.1中的80-=x . 因此同余式的3个解为 )321(mod 8-≡x , )321(mod 99)321(mod 3 3218≡+-≡x , )321(mod 206)321(mod 3 32128≡?+-≡x . (4)?? ???≡≡≡)9(mod 3)8(mod 2)7(mod 1x x x . 解 因为(7,8,9)=1,所以可以利用定理5.1.我们先解同余式 )7(mod 172≡x ,)8(mod 163≡x ,)9(mod 156≡x , 得到)9(mod 4),8(mod 1),7(mod 4321-=-==x x x .于是所求的解为 ). 494(mod 478)494(mod 510 )494(mod 3)4(562)1(631472=-=?-?+?-?+??≡x (5)???????≡≡≡≡) 9(mod 5)7(mod 3)5(mod 2)2(mod 1x x x x . (参考上题)
第一章 §1 1 证明:n a a a ,,21 都是m 的倍数。 ∴存在n 个整数n p p p ,,21使 n n n m p a m p a m p a ===,,,222111 又n q q q ,,,21 是任意n 个整数 m p q p q q p a q a q a q n n n n )(22112211+++=+++∴ 即n n a q a q a q +++ 2211是m 的整数 2 证: )12)(1()12)(1(-+++=++n n n n n n n )1()1()2)(1(+-+++=n n n n n n )1()1/(6),2)(1(/6+-++n n n n n n )1()1()2)(1(/6+-+++∴n n n n n n 从而可知 )12)(1(/6++n n n 3 证: b a , 不全为0 ∴在整数集合{}Z y x by ax S ∈+=,|中存在正整数,因而 有形如by ax +的最小整数00by ax + Z y x ∈?,,由带余除法有00000,)(by ax r r q by ax by ax +<≤++=+ 则 S b q y y a q x x r ∈-+-=)()(00,由00by ax +是S 中的最小整数知0=r by ax by ax ++∴/00 下证8P 第二题 by ax by ax ++/00 (y x ,为任意整数) b by ax a by ax /,/0000++∴ ).,/(00b a by ax +∴ 又有b b a a b a /),(,/),( 00/),(by ax b a +∴ 故),(00b a by ax =+ 4 证:作序列 ,2 3, ,2 , 0,2 ,,2 3,b b b b b b - -- 则a 必在此序列的某两项之间
《初等数论》教学大纲 课程编码:110823 课程名称:初等数论 学时/学分:54/3 先修课程:《数学分析》、《高等代数》 适用专业:信息与计算科学 开设教研室:代数与几何教研室 一、课程性质与任务 1.课程性质:初等数论是信息与计算科学专业的一门专业必修课程。该课程是研究整数性质和方程(组)整数解的一门学科,也是一个古老的数学分支。初等数论是现代密码学的一门基础课程,也是高等学校信息安全专业的一门重要的基础课。初等数论在计算技术、通信技术等技术学科中也得到了广泛的应用。 2.课程任务:初等数论是信息与计算科学专业的一门重要的专业必修课,开设的目的在于使学生熟悉和掌握数论的基础知识,基本理论和基本的解题技能技巧,培养学生的逻辑思维能力,更深入地理解初等数论与其它邻近学科的关系,为进一步学习信息安全领域的其它学科打下坚实的基础。 二、课程教学基本要求 初等数论是研究整数性质的一门学科,历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂,容易引起人的兴趣,但是解决它们却非常困难。本课程的目的是简单介绍在初等数论研究中经常用到的若干基础知识、基本概念、方法和技巧。 通过本课程的学习,使学生加深对整数的性质的了解,更深入地理解初等数论与其它邻近学科的关系。 1. 有关定义、定理、性质等概念的内容按“知道、了解和理解”三个层次要求;有关计算、解法、公式和法则等方法的内容按“会、掌握、熟练掌握”三个层次要求。 2. 本课程开设在第5学期,总学时54,其中课堂讲授54学时,课堂实践0学时。教学环节以课堂讲授为主,研制电子教案和多媒体幻灯片以及CAI课件,在教学方法和手段上采用现代教育技术。 3. 成绩考核形式:期终成绩(闭卷考试)(70%)+平时成绩(平时测验、作业、课堂提问、课堂讨论等)(30%)。成绩评定采用百分制,60分为及格。
备注:纯手写代码,注释。 数论 1、素数 (1)暴力求解法 根据素数的概念,没有1和其本身没有其他正因数的数。所以只需枚举比这个数小的数,看能整除即可; C++代码: #include
//去掉了偶数的判断,效率提高一倍 /*如果number整除以i,那么会得到两个的因数, 而较小的那个因数不会超过number的二分之一次方; 所以只需判断到number的平方根向上取整即可;*/ if(number%i); else return false; return true; } int main() { int sum; cin>>sum; if(determine(sum)) cout<<"YES!"; else cout<<"NO!"; return 0; } 时间复杂度:o(sqrt(n)/2); 空间复杂度:几乎没有; (2)一般线性筛法: 因为任何一个合数都能分解成几个素数相乘的形式; 所以可以做一个表,首先把2设为质数,然后将2的倍数设为合数,剩下的数就是新得到的质数,然后重复这个过程,直到筛到合
适的范围即可; 但是这个算法有缺陷: 1、同一个数可能被筛多次,这就产生了多余的步骤。 2、占用空间很大,如果使用bool数组的话,只能筛到1e9; 3、从1-n筛,不能从m-n开始筛; C++代码: #include
初等数论试卷和答案
初等数论考试试卷1 一、单项选择题(每题3分,共18分) 1、如果a b ,b a ,则( ). A b a = B b a -= C b a ≤ D b a ±= 2、如果n 3,n 5,则15( )n . A 整除 B 不整除 C 等于 D 不一定 3、在整数中正素数的个数( ). A 有1个 B 有限多 C 无限多 D 不一定 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C ac T )(mod m bc D b a ≠ 5、如果( ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 二、填空题(每题3分,共18分) 1、素数写成两个平方数和的方法是( ). 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为 ( ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ). 5、b a ,的公倍数是它们最小公倍数的( ).
试卷1答案 一、单项选择题(每题3分,共18分) 1、D. 2、A 3、C 4、A 5、A 6、B 二、填空题(每题3分,共18分) 1、素数写成两个平方数和的方法是(唯一的). 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是(b m a ),(). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ][b a ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( 与p 互素 ). 5、b a ,的公倍数是它们最小公倍数的( 倍数 ). 6、如果b a ,是两个正整数,则存在( 唯一 )整数r q ,,使r bq a +=,b r ≤0. 三、计算题(每题8分,共32分) 1、 求[136,221,391]=?(8分) 解 [136,221,391] =[[136,221],391] =[391,17221136?] =[1768,391] ------------(4分) = 17391 1768?
作业次数:学号姓名作业成绩 第0章序言及预备知识 第一节序言(1) 1、数论人物、资料查询:(每人物写600字左右的简介) (1)华罗庚 2、理论计算与证明: (1 是无理数。 (2)Show that there are infinitely many Ulam numbers 3、用Mathematica 数学软件实现 A Ulam number is a member of an which was devised by and published in in 1964. The standard Ulam sequence (the (1, 2-Ulam sequence starts with U 1=1 and U 2=2 being the first two Ulam numbers. Then for n > 2, U n is defined to be the smallest that is the sum of two distinct earlier terms in exactly one way 。 By the definition, 3=1+2 is an Ulam number; and 4=1+3 is an Ulam number (The sum 4=2+2 doesn't count because the previous terms must be distinct. The integer 5 is not an Ulam number because 5=1+4=2+3. The first few terms are 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77,
初等数论考试试卷1 一、单项选择题(每题3分,共18分) 1、如果a b ,b a ,则( ). A b a = B b a -= C b a ≤ D b a ±= 2、如果n 3,n 5,则15( )n . A 整除 B 不整除 C 等于 D 不一定 3、在整数中正素数的个数( ). A 有1个 B 有限多 C 无限多 D 不一定 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C ac T )(mod m bc D b a ≠ 5、如果( ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 二、填空题(每题3分,共18分) 1、素数写成两个平方数和的方法是( ). 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ). 5、b a ,的公倍数是它们最小公倍数的( ). 6、如果b a ,是两个正整数,则存在( )整数r q ,,使r bq a +=,b r π≤0. 三、计算题(每题8分,共32分) 1、求[136,221,391]=? 2、求解不定方程144219=+y x . 3、解同余式)45(mod 01512≡+x . 4、求? ?? ??563429,其中563是素数. (8分) 四、证明题(第1小题10分,第2小题11分,第3小题11分,共32分)
《初等数论》教学大纲 Elementary number theory 一、本大纲适用专业 数学与应用数学。 二、课程性质与目的 1. 课程目标 初等数论是数学与应用数学专业一门专业选修课。通过这门课的学习,使学生获得关于整数的整除、不定方程、同余、原根与指数的基本知识,掌握数论中的最基本的理论和常用的方法,加强他们的理解和解决数学问题的能力,为今后的实际工作打下良好基础。 2. 与其它课程的关系 本课程是初等数学研究、C语言程序设计A,近世代数等课程的后续课程。 3. 开设学期 按培养方案规定的学期开设。 三、教学方式及学时分配 序号主要内容主要教学方式学时 1 第一章整数的可除性面授讲课8 2 第二章不定方程面授讲课8 3 第三章同余、同余式面授讲课8 4 第四章二次剩余式与平方剩余面授讲课8 四、教学内容、重点 第一章整数的可除性 1. 教学目标 理解整数整除的概念、最大公约数的概念、最小公倍数的概念,掌握带余除法与辗转相除法;理解素数与合数的概念;理解和掌握素数的性质、整数关于素数的分解定理、素数的求法;掌握函数[x]和 {x} 的性质。 2. 教学内容 (1)整数整除、剩余定理:带余除法与辗转相除法;最大公约数的概念、性质及求最大公约数的方法;最小公倍数的概念、性质及最小公倍数的求法。(2)素数与合数:素数与合数的概念、素数的性质、整数关于素数的分解定理、素数的求法;函数[x] {x} 的性质及其应用。
3. 教学方法 讲解教学。 4. 本章重点 辗转相除法,整数的素数分解定理。 5. 本章难点 求最大公因子的方法。 第二章不定方程 1. 教学目标 理解不定方程的概念,理解和掌握元不定方程有整数解的条件,会求一次不定方程的解。 2. 教学内容 (1)一次不定方程,多元一次不定方程的形式,多元一次不定方程有解条件,求简单的多元一次不定方程的解。(2)二元一次不定方程有整数解的条件,求一次不定方程的解。 3. 教学方法 讲解教学。 4. 本章重点 多元一次不定方程有解条件,二元一次不定方程有整数解的条件。 5. 本章难点 不定方程的整数解的形式,求多元不定方程的整数解。 第三章同余、同余式 1. 教学目标 理解整数同余的概念,理解和掌握同余的基本性质、整数具有素因子的条件函数相关性质;理解剩余类与完全剩余系的概念,理解欧拉函数的定义及性质;掌握欧拉定理、费马定理、孙子定理。 2. 教学内容 (1)整数同余:整数同余的概念、同余的基本性质;整数具有素因子的条件;利用同余简单验证整数乘积运算的结果。(2)剩余类与完全剩余系:剩余类与完全剩余系的概念;判断剩余系的方法;欧拉函数的定义及性质;欧拉定理、费马定理。(3)同余式的基本概念、孙子定理。 3. 教学方法 讲解教学。 4. 本章重点 剩余系的判定,欧拉函数的定义及性质,中国剩余定理。 5. 本章难点 判断剩余系的方法,费马定理。
初等数论考试试卷 1 一、单项选择题(每题3分,共18分) 1、 如果 ba , ab ,则(). A a b Bab C a b Dab 2、 如果 3n , 5n ,则 15 ( ) n . A 整除 B 不整除 C 等于 D 不一定 3、 在整数中正素数的个数( ). A 有1个 B 有限多 C 无限多 D 不一定 4、 如果 a b (modm ) , c 是任意整数贝V 5、 如果(),则不定方程ax by c 有解. A (a, b)c B c(a,b) C ac D (a,b)a 6、 整数5874192能被()整除. A 3 B 3 与 9 C 9 D 3 或 9 二、填空题(每题3分,共18分) 1、 素数写成两个平方数和的方法是( )? 2、 同余式ax b 0(modm ) 有解的充分必要条件是(). 3、 如果 a,b 是两个正整数,则不大于a 而为b 的倍数的正整数的个数为(). 4、 如果p 是素数,a 是任意一个整数,则a 被P 整除或者(). 5、 a,b 的公倍数是它们最小公倍数的 (). 6、如果a ,b 是两个正整数,则存在()整数q ,r ,使a bq r ,0 r b . 三、计算题(每题8分,共32分) 1、 求[136,221,391]=? 2、 求解不定方程9x 21y 144 . 3、 解同余式 12x 15 0(mod45) . 429 4、 求563 ,其中563是素数.(8 分) 四、证明题(第 1小题10分,第2小题11分,第3小题11分,共32分) 2 3 n n n 1证明对于任意整数n ,数3 2 6是整数. 2、 证明相邻两个整数的立方之差不能被 5整除. A ac bc(modm) B a b C ac bc(mod m) D ab
初等数论学习总结 本课程只介绍初等数论的的基本内容。由于初等数论的基本知识和技巧与中学数学有着密切的关系, 因此初等数论对于中学的数学教师和数学系(特别是师范院校)的本科生来说,是一门有着重要意义的课程,在可能情况下学习数论的一些基础内容是有益的.一方面通过这些内容可加深对数的性质的了解,更深入地理解某些他邻近学科,另一方面,也许更重要的是可以加强他们的数学训练,这些训练在很多方面都是有益的.正因为如此,许多高等院校,特别是高等师范院校,都开设了数论课程。 最后,给大家提一点数论的学习方法,即一定不能忽略习题的作用,通过做习题来理解数论的方法和技巧,华罗庚教授曾经说过如果学习数论时只注意到它的内容而忽略习题的作用,则相当于只身来到宝库而空手返回而异。 数论有丰富的知识和悠久的历史,作为数论的学习者,应该懂得一点数论的常识,为此在辅导材料的最后给大家介绍数论中著名的“哥德巴赫猜想”和费马大定理的阅读材料。 初等数论自学安排 第一章:整数的可除性(6学时)自学18学时 整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理 [x]和{x}的性质及其在数论中的应用 习题要求3p :2,3 ; 8p :4 ;12p :1;17p :1,2,5;20p :1。 第二章:不定方程(4学时)自学12学时 二元一次不定方程c by ax =+ 多元一次不定方程c x a x a x a n n =++ 2211 勾股数 费尔马大定理。 习题要求29p :1,2,4;31p :2,3。
第三章:同余(4学时)自学12学时 同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系 欧拉定理、费尔马小定理及在循环小数中的应用 习题要求43p :2,6;46p :1;49p :2,3;53p 1,2。 第四章:同余式(方程)(4学时)自学12学时 同余方程概念 孙子定理 高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。 习题要求60p :1;64p :1,2;69p :1,2。 第五章:二次同余式和平方剩余(4学时)自学12学时 二次同余式 单素数的平方剩余与平方非剩余 勒让德符号 二次互反律 雅可比符号、 素数模同余方程的解法 习题要求78p :2; 81p :1,2,3;85p :1,2;89p :2;93p :1。 第一章:原根与指标(2学时)自学8学时 指数的定义及基本性质 原根存在的条件 指标及n 次乘余 模2 及合数模指标组、
02013自学考试初等数论模拟试题(含答案) 一、 单项选择题:(1分/题×20题=20分) 1.设x 为实数,[]x 为x 的整数部分,则( ) A.[][]1x x x ≤<+; B.[][]1x x x <≤+; C.[][]1x x x ≤≤+; D.[][]1x x x <<+. 2.下列命题中不正确的是( ) A.整数12,,,n a a a 的公因数中最大的称为最大公因数; B.整数12,, ,n a a a 的公倍数中最小的称为最小公倍数 C.整数a 与它的绝对值有相同的倍数 D.整数a 与它的绝对值有相同的约数 3.设二元一次不定方程ax by c +=(其中,,a b c 是整数,且,a b 不全为零)有一整数解()00,,,x y d a b =,则此方程的一切解可表为( ) A.00,,0,1,2,;a b x x t y y t t d d =- =+=±± B.00,,0,1,2, ;a b x x t y y t t d d =+=-=±± C.00,,0,1,2, ;b a x x t y y t t d d =+=-=±± D.00,,0,1,2, ;b a x x t y y t t d d =-=-=±± 4.下列各组数中不构成勾股数的是( ) A.5,12,13; B.7,24,25; C.3,4,5; D.8,16,17 5.下列推导中不正确的是( ) A.()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ B.()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ C.()()111212mod mod ;a b m a a b a m ≡?≡ D.()()112211mod mod .a b m a b m ≡?≡ 6.模10的一个简化剩余系是( ) A.0,1,2, ,9; B.1,2,3,,10; C.5,4,3,2,1,0,1,2,3,4;----- D.1,3,7,9.
初等数论第五章二次同余式与平 方剩余 第五章二次同余式与平方剩余第五章二次同余式与平方剩余§1二次同余式与平方剩余二次同余式的一般形式是ax2?bx?c?0(modm),a??0(modm)(1)下面讨论它的解的情况。?k?1?2令m?p1p2?pk,则(1)有解的充要条件为ax2?bx?c?0(modpi?i),i?1,2,?,k有解,而解f(x)?ax2?bx?c?0(modp?),p为质数(2)又可以归结为解f(x)?ax2?bx?c?0(modp),p为质数(3)。当p?2时,同余式(3)极易求解,因此,我们只需讨论二次同余式f(x)?ax2?bx?c?0(modp),p为奇质数(4)若p?|a,用4a乘(4)再配方得(2ax?b)2?4ac?b2?0(modp),令y?2ax?b,A?b2?4ac,得y2?A?0(modp)可以证明:同余式(4)和(5)是等价的。证明
必要性显然;反之,设(5)有一解y?y0,因为(p,2a)?1,所以2ax?b?y0(modp)有解,即(4)有解。以上讨论可知,二次同余式可以化为x2?a(modp),p为奇质数(6)(5)来求解,当p|a时,(6)仅有一个解x?0(modp),所以我们下面总假定p?|a或(p,a)?1。因此,下面主要研究形如x2?a(modp),(p,a)?1,p为奇质数同余式。 (7)的定义若同余式x2?a(modp),(a,p)?1,p为奇质数有解,则a 叫做模p的平方剩余(二次剩余),若无解,则a叫做模p的平方非剩余(二次非剩余)。定理1(欧拉判别条件)若(a,p)?1,则a是模p的平方剩余的充要条件为ap?12?1(modp);a是模p的平方非剩余的充要条件为a- 1 - p?12??1(modp)。若a是模p的平方剩余,则(7)式恰有两解。第五章二次同余式与平方剩余证明(1)设a是模p 的平方剩余,则同余式x2?a(modp),(a,p)?1有解,设为?,于是??a(modp),从而欧拉定理可知反之,若
附录1 习题参考答案 第一章习题一 1. (ⅰ) 由a b知b = aq,于是b = (a)(q),b = a(q)及b = (a)q,即a b,a b及a b。反之,由a b,a b及a b 也可得a b; (ⅱ) 由a b,b c知b = aq1,c = bq2,于是c = a(q1q2),即a c; (ⅲ) 由b a i知a i= bq i,于是a1x1a2x2a k x k = b(q1x1 q2x2q k x k),即b a1x1a2x2a k x k;(ⅳ) 由b a知a = bq,于是ac = bcq,即bc ac; (ⅴ) 由b a知a = bq,于是|a| = |b||q|,再由a 0得|q| 1,从而|a| |b|,后半结论由前半结论可得。 2. 由恒等式mq np= (mn pq) (m p)(n q)及条件m p mn pq可知m p mq np。 3. 在给定的连续39个自然数的前20个数中,存在两个自然数,它们的个位数字是0,其中必有一个的十位数字不是9,记这个数为a,它的数字和为s,则a, a 1, , a 9, a 19的数字和为s, s 1, , s 9, s 10,其中必有一个能被11整除。 4. 设不然,n1= n2n3,n2p,n3p,于是n = pn2n3p3,即p3n,矛盾。 5. 存在无穷多个正整数k,使得2k1是合数,对于这样的k,(k1)2
不能表示为a2p的形式,事实上,若(k 1)2= a2p,则(k 1 a)( k 1 a) = p,得k 1 a = 1,k 1 a = p,即p = 2k 1,此与p为素数矛盾。 第一章习题二 1. 验证当n =0,1,2,… ,11时,12|f(n)。 2.写a = 3q1r1,b = 3q2r2,r1, r2 = 0, 1或2,由3a2b2 = 3Q r12r22知r1 = r2 = 0,即3a且3b。 3.记n=10q+r, (r=0,1,…,9),则n k+4-n k被10除的余数和r k+4-r k=r k(r4-1)被10 除的余数相同。对r=0,1,…,9进行验证即可。 4. 对于任何整数n,m,等式n2 (n 1)2 = m2 2的左边被4除的余数为1,而右边被4除的余数为2或3,故它不可能成立。 5 因a4 3a2 9 = (a2 3a 3)( a2 3a 3),当a = 1,2时,a2 3a 3 = 1,a4 3a2 9 = a2 3a 3 = 7,13,a4 3a2 9是素数;当a 3时,a2 3a 3 > 1,a2 3a 3 > 1,a4 3a2 9是合数。 6. 设给定的n个整数为a1, a2, , a n,作 s1 = a1,s2 = a1a2,,s n = a1a2a n, 如果s i中有一个被n整除,则结论已真,否则存在s i,s j,i < j,使得s i与s j 被n除的余数相等,于是n s j s i = a i + 1a j。