初等数论试卷
一．填空题：
1、(1859-, 1573)=143
2、对于任意的正整数,a b ，有[,].(,)
ab a b a b = 3、[]{}.x x x =+ 4、22345680的标准分解式是422345680235747283=?????.
5、整数集合A 中含有m 个整数，且A 中任意两个整数对于m 是不同余的，则整数集合A 是模m 的完全剩余系.
6、设a 、b 是任意两个正整数，则不大于a 而为b 的倍数的正整数个数为a b
??????. 7、素数写成两个平方数和的方法是唯一的. 8、不同剩余类中的任何两个不同整数对模m 是不同余的.
9、n 元一次不定方程1122.n n a x a x a x c +++=……有解的充分必要条件是12().n a a a c +……
10、初等数论按研究方法分为：初等数论、解析数论、代数数论、几何数论.
11、数集合A 是模m 的简化剩余系的充要条件（1）A 中含有()f m 个整数；（2）任意两个整数对模m 不同余；
（3）A 中每个整数都与m 互素；
12、 设n 是正整数1321222,,.........,n n n n c c c -的最大公约数为12k + 13、若(,)1a b =，则
(,)(,)a bc a c =.
14、81234被13除的余数是12. 15、模7的最小非负完全剩余系是0、1、2、3、4、5、6.
二、判断题：
1、若n 为奇数，则8|21n -。 （ √ ）
2、设n 、k 是正整数k n 与4k n +的个位数字不一定相同。 （ × ）
3、任何大于1的整数a 都至少有一个素因数. （ √ ）
4、任何一个大于1的合数与a . （ √ ）
5、任意给出的五个整数中必有三个数之和能被整数3整除. （ √ ）
6、最大公约数等于1是两两互素的必要而不充分条件. （ √ ）
7、设p 是素数，a 是整数，则p a 或(,) 1.p a = （ √ ）
8、如果12,n a a a ……是互素的，则12,n a a a ……一定两两互素 （ ×）
9、设p 是素数，若p ab ，则p a 且.p b （ × ）
10、（刘维尔定理）设p 是素数，则(1)p -！1(mod )p ≡- （ √ ）
11、m 是正整数(,)1a m =，则()1(mod ).m a m ?≡（ √ ）
12、由于每个非零整数的约数个数是有限的，所以最大的公约数存在，且正整数。（ √ ）
13、设d 是12,k a a a ……的一个约数，则12,k d a a a ……（ √ ）
14、103319781978-不能被310整除。（ × ）
15、n
1........211+++ (n ?2) 是整数（ × ） 16、n 为正整数，若21n -为素数，则n 不一定是素数（ × ）
17、若1n >并且(1)n -!(mod )n ≡,则n 不是素数（ × ）
18、设()f x 是整系数多项式，并且(1),(2),()f f f m ……都不能被m 整除，则()0f m =有整数解（ × ）
19、若12(,)1m m =（12,m m 是任意两个互质的正整数），是则1211()()()m m m m ???=? （ × ）
20、如果两个整数互相整除，则这两个数仅相差一个符号（ × ）
三、计算题：
1、设a 、b 是整数且229a ab b ++，则3(,).a b 解：由2222293()33()39()a ab b a b ab a b a b a b ++?-+?-?-?-. 再由229a ab b ++得933ab ab ?.
由定理4的推论1（设p 是素数，若p ab ，则p a 或.p b ）得3a 或3.b
2、求(12345, 678).
解：(12345, 678).= 12345,33912006,3396003,3395664,339===（）（）（）（）
177,339177,162177,8196,813,81=（）=（）=（）=（）=（）=3.
3、求3326(25746)+被50除的余数.
解：根据定理4，有33263326216261626(25746)(74)[(77)4][7(1)4]+≡-≡+-≡?--
262655743332129mod50)≡-≡=?≡-≡（）（）（即所
求的余数是29.
4、将
1930
写成三个既约分数之和，它们的分母分别是2，3和5. 解：设1930235x y z =++即1510619.x y z =+=
2(15,105d ==) ∴上述方程等价于151055619x y t t z +=??+=?解得1645t u z u
=-+??=-? 从而，230x t v y t =+??=--?故162163(,)45x u v y u v u v z z u =-++??=--∈??=-?
取0u v ==得1,1,4x y z =-==即1911430235
=-++ 5、求不定方程3615x y +=的解. 解：(3,6)315=∴方程有解
由辗转相除法，可以知道1,1x y =-=是方程363(211,2)x y x y a b +=+=?==的一个解
所以，005,5x y =-=就是原方程的解； 由定理2知52)5x t t z y t
=-+?∈?=-?（
6、用辗转相除法求整数x 、y 使得1387x -162y =(1387,162).
解：作辗转相除：1387(162)(8)91=-?-+，16291(2)20-=?-+
9120411=?+，201119=?+，11912=?+，9241=?+，2120=?+
由此可得6n =，18q =-，22q =-，34q =，41q =，51q =，64q =
x =173(1)n n Q -=-，y =625(1)n n
p =-,又(1387,162).=1=r n ， 故1387731626251(1387,162)?-?==
7、将105
17写成三个既约分数之和，它们的分母分别是3，5和7（第四章习题一1） 解：设7
5310517z y x ++=，即35211517x y z ++=. 因(35,21)7,(7,15)1==，171，故有解.
分别解53x y t t +=+得3,25,,x t u y t u u Z =-+=-∈1115,47,t v z v v Z =+=--∈
消去t 得11153,22305,47,x v u y v u z v u =--+=+-=--、v Z ∈.
对于任意的确定的u 和v 的值，都给出一种表示法。
8、求最大的正整数k ，使得199!10k
解：由定理3（设n 是正整数，1212!k k n p p p ααα=?……是!n 的标准分解式，则1[
]i r i n p r
α∞==∑）
从而得知，
199!的标准分解式中所含的5的幂指数是2199199[][]4755
++=……（199!1025k k k A A =?=??）
所以所求得的最大正整数是47.
9、若四个数2839,4582,5164,6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少？
解：设除数为d ，余数为r ，则由174628364582=-d ，58245825164=-d ，
135851646522=-d ，知194)1358,582,1764(=d 由此得97
,2
d r ==或194,120.d r ==
10、将352134359738367-=分解因数.（ 第三章 第四节 Euler 定理 例7 ） 解：若3521p -，则p 是521-或721-的素因数或者1(mod70).p ≡ 其中有31和127，因为3521311278727391-=??，所以35
21-分别是因数只能用1(mod70).p ≡来寻求
在数列71、211、281……中经检验872739171122921=?
显然，122921的素因数也在31、127或数列71、211、281……中
简单计算122921不能被31、127整除，也不能被数列71、211、281……351<）
整除.
所以122921是素数，故35213112771122921-=???
四、证明题：1、求证：平方数的正因数个数是奇数.
证明：因为每个自然数n 的正因数个数是成对出现的，若d 是n 的因数，则
n d 也是n 的因数
当d ≠n d d
≠.
当d n d d
=即当n n . 于是，当且仅当n 为平方数时，n 的正因数个数是奇数.
2、求证：若(,)1a b =，则(,)1a b a b +-=或2.
证明：假设d 是a b ±的任意一个公约数，则有d a b +且.d a b - 于是2d a ，2.d b 又(,)1a b = 2d ∴ 从而，1d =或2d =.
3、假设a 为正整数，则51234n n n n +++的充要条件为4.n 证明：因为(5)4?=，所以，由费马定理有41(mod5)
(14).k k ≡≤≤ 故
，若4(n q r r =+
≤≤，则
1234123412(2)(1)n n n n r r r r r r r r +++≡+++≡++-+-
用0r =、1、2、3分别代入上式，则当r =1、2、3时51234n n n n +++
当0r =时，4n ，5不整除1234n n n n +++.
因此，若a 为正整数，则51234n n n n +++的充要条件为4.n
4、证明：对任意整数n ，53()357f n n n n =++被15整除.
证明：对任意整数n 记作15(015)n q r r =+≤<
因为对任意的整数m 有11a a m r =+则k
a 与1k r 被m 除的余数相同
0r =222221(15)(15)3015n q r q qr r A r =+=++=+即2n 与2r 被15除的余数是相同的记为1r .
同理，4n 与4
r 被15除的余数是相同的记为2r .即21115r B r =+，42215r B r =+则44215.n A r =+
考虑42
357n n ++被15除的余数 4242213573(15)5(15)7n n A r A r ++=++++
2221113153(15)5(1515)7A B r A B r =?+?+++++211535715Q R Q r r '=+++=+
可见，42
357n n ++与21357r r ++的余数相同记为R . 42()(357)(15)(15)15f n n n n C R q r O Rr ∴=?++=++=+且()f n 与Rr 有相同的余数
记为R '.
当0r =时，0R '=即15().f n
【对于1,2,14r =……的情形通过计算列出下表：】
1r =、14 2r =、13 3r =、12 4r =、11 5r =、10 6r =、9 7r =、8 11r =
14r = 14r = 11r = 110r = 16r = 14r = 21r =
21r = 26r = 21r = 210r = 26r = 21r = 0R =
0R = 10R = 0R = 12R = 10R = 0R = 0R '=
0R '= 0R '= 0R '= 0R '=
0R '= 0R '= 5、定理（带余除法）：若a 、b 是两个整数，其中b ≠0，则存在着两个整数q 和r ，使得a bq r =+,0r b ≤< 成立.而且q 及r 是唯一的. 证明：存在性：若b a ，则()a bq q z =∈可以取0r = 若b a ，考虑集合{,}A a kb k z =+∈集合A 中有无限多个正整数，设其中最小的正整数为0.r a k b =+ 则必有0r b ≤<，否则就有r b ≥（r b ∴≠，若r b =，则b a 矛盾，于是r b >即0r a k b b =+>00a k b b ?+->这样集合A 中又有正整数0a k b b r +-<与r 的最小值矛盾） 故0r b ≤<，取0q k =-使得a bq r =+,0r b ≤< 成立. 存在性得证
唯一性：假设存在两对整数1q 、1r 及2q 、2r 都使得a bq r =+,0r b ≤< 成立.
即有1122a bq r bq r =+=+12(0,)r r b ≤<，则1221()b q q r r -=-，21r r b -<.
12b r r ∴- 121212
0r r r r q q -=?=?= 6、设12{,}m A x x x =……是模m 的一个完全剩余系，以{}x 表示x 的小数部分，证明：若
(,)1a m =，则11{
}(1)2
m i i ax b m m =+=-∑ 证明：当x 通过模m 的完全剩余系时，ax bR +通过模m 的完全剩余系.
因此，对任意的(1)i i m ≤≤，i ax b +一定与且只与某个整数(1)j j m ≤≤同余即存在整数k 使得：(1)i ax b km j j m +=+≤≤ 从而，11111
1(1)1{}{}{}(1)22m
m m m i i j j j ax b j j j m m k m m m m m m -====+-=+===?=-∑∑∑∑ 7、设1m >,(,)1a m =，1x ,2x ,…,)(m f x 是模m 的简化剩余系，证明：
()11
{}()2f m i i ax f m m ==∑.其中{}x 表示x 的小数部分。 证明：由题可设：(0)i i i i ax mq r r m =+≤<由i x 通过模m 的简化剩余系知i r 通过模m 的最
小
非负简化剩余系，于是由定理可知：()()()()
1111111{}{}{}{}()()22
f m f m f m f m i i i i i i i i i ax r r q r mf m f m m m m m m =====+====∑∑∑∑ 8、设a 、b 是正整数，2b <则2121b a -+
证明：（1）若a b <且2121b a -+成立，则21212222(21)2b a b a a b a --≤+?-≤?-≤
于是1a =，1b a -=即2b =与2b >矛盾，故命题结论成立.
（2）若a b =且2121b a -+，则21(21)221221223a a a a a --+?-?-≤?≤
于是1b a ==，与2b >矛盾，故命题结论成立.
（3）若a b >，记(0)a kb r r b =+≤<此时
(1)(2)21(21)(221)(21)()kb k k b k b b Q Q z ---=-+++=-∈…….
故
21212(211)2[(21)1]1(21)(21)()a kb r r kb r b b r Q Q Q z +''+=+=-+=-++=-++∈ 由21212121b a b r -+?-+，在（1）中已经证明这是不可能的，故命题结论成
立.
9、证明：存在无穷多个正整数a ,使得4(1,2n a n +=……)都是合数（即分成两项乘积即可）。 证明：取44a k =,对任意的n N ∈,有
4422224(2)4n k n k n k +=+-2222(22)(22)n k nk n k nk =++?+-
2222222() 2.3.......n k nk n k k k k n N +-=-+≥∴?=?∈4
a N ∴?+都是合数。
10、证明：a 、b 、c N ∈，c 无平方因子且22a b c ,证明：.a b 证明：设(,)a b d =,则有1a da =与1b db =,11(,)1a b =. 由22a b c 得2211a b c ，21a c
因为c 无平方因子，所以11a =，a d =，1.b ab =即.a b .
11、对任意的正整数a 、b 、c .证明下面的结论成立。
（1）由b ac 且(,)1a b =,可得出b|c.（2）由b c 与a c , 且(,)1a b =.可推出ab c . 证明：（1）(,)1a b =.∴存在整数x 与y 使得1ax by +=. .acx bcy c ∴+= b ac .b acx bcy ∴+即b c
(2). 由(,)1a b =,存在整数x 与y 使得1a x b y +=
.又由b c 与a c ,得ab ac ,ab bc .
因此，abqx abpy c +=∴ab c
12、设m 是整数且4m ,{1a ,2a ,…m a }与{1b ,2b ,…m b }是模m 的两个完全剩余系，证明：
{1a 1b ,2a 2b ,…, m a m b }不是模m 的完全剩余系。
证明：因为4m ，若{1a 1b ,2a 2b ,…, m a m b }是模m 的完全剩余系，则其中的奇数与偶数各半.
又因为{1a ,2a ,…m a }与{1b ,2b ,…m b }也是模m 的两个完全剩余系，从而有i i b a 必须使i a ，i b 同为奇数或偶数.即2(mod 4)i i a b ≡,这对于4m 的模m 的完全剩余系是不可能的。
13、设a 、b 、c 、d 是整数，并且(mod )a b m ≡,(mod )c d m ≡.求证：()i (mod )a c b d m +≡+. ()ii (mod )ac bd m ≡
证明：()i 因为(mod )a b m ≡,(mod )c d m ≡，由定义知m a b -，.m c d -
从而，()()()()m a b c d a c b d -+-=+-+ 故，(mod )a c b d m +≡+.
()ii 由定理1（3）知存在整数1q 与2q ，使得1a b q m =+，1c d q m =+,
从而11121()()()a c b q m d q m b d q q m q d q b m
=++=+++.因此，(mod )ac bd m ≡.
初等数论
1：[单选题]已知361a是一个4位数（其中a是个位数），它能被5整除，也能被3整除，则a的值是（）。 A：0B：2C：5D：9参考答案：C
2：[单选题]下面的（）是模4的一个简化剩余系。 A：4,17B：1,15C：3,23D：13,6参考答案：B
3：[单选题]小于20的正素数的个数是（）。 A：11B：10C：9D：8参考答案：D 4：[单选题]
下面的数是3的倍数的数是（）。
A：19B：119C：1119D：11119参考答案：C
5：[单选题]-4除-39的余数是（）。 A：3B：2C：1D：0参考答案：C
6：[单选题]一个正整数n的各位上的数字是0或1，并且n能被2和3整除，则最小的n 是（）。 A：1110B：1101C：1011D：1001参考答案：A
7：[单选题][[4.5]+[3.7]]等于（）。 A：3B：4C：7D：8参考答案：C
8：[单选题]{{1.8}+{2.9}}等于（）。 A：0.4B：0.5C：0.6D：0.7参考答案：D 9：[单选题]100与44的最小公倍数是（）。 A：4400B：2200C：1100D：440参考答案：C
10：[单选题]使3的n次方对模7同余于1的最小的正整数n等于（）。 A：6B：2C：3D：13参考答案：A
11：[单选题]设a,b,c,d是模5的一个简化剩余系，则a+b+c+d对模5同余于（）。 A：0B：1C：2D：3参考答案：A
12：[单选题]下面的（）是不定方程3x + 7y = 20的一个整数解。 A：x=0,y=3B：x=2,y=1C：x=4,y=2D：x=2,y=2参考答案：D
13：[单选题]下面的（）是模4的一个完全剩余系。 A：9，17，-5，-1B：25，27，13，-1C：0，1，6，7D：1，-1，2，-2参考答案：C
14：[单选题]下面的（）是模12的一个简化剩余系。 A：0，1，5，11B：25，27，13，-1C：1，5，7，11D：1，-1，2，-2参考答案：C
15：[单选题]若a，b均为偶数，则a + b为（）。
A：偶数B：奇数C：正整数D：负整数参考答案：A
16：[单选题]1到20之间的素数是（）。 A：1，2，3，5，7，11，13，17，19B：2，3，5，7，11，13，17，19C：1，2，4，5，10，20D：2，3，5，7，12，13，15，17参考答案：B
17：[单选题]如果a|b，b|c，则（）。 A：a=cB：a=-cC：a|cD：c|a参考答案：C
18：[单选题]360与200的最大公约数是（）。 A：10B：20C：30D：40参考答案：D 19：[单选题]如果 a|b，b|a ，则（）。 A：a=bB：a=-bC：a=b或a=-bD：a，b的关系无法确定参考答案：C
20：[单选题]如果5|n ，7|n，则35（）n 。 A：不整除B：等于C：不一定D：整除参考答案：D
21：[单选题]整数6的正约数的个数是（）。 A：1B：2C：3D：4参考答案：D
22：[单选题]设n，m为整数，如果3整除n，3整除m，则9（）mn。 A：整除B：不整除C：等于D：小于参考答案：A
初等数论第二次作业
填空题
1．16除100的余数是 4 _。
2．如果今天是星期一，那么从今天起再过1010天后是星期 四 。
3．{3.2} = 0.8 ；[2.84] = 3 。
4．[{3.6} + {1.7}] = 0.9 。
5．{{4.2}{2.3}}-+=______-1.5________。
6．15的所有正因数的和是 24 。
7．1260的标准分解式是 7532126022???= 。
8．20！的标准分解式是1917131197532!202
24818????????=。
9．98!的末尾有______22_________个零。
10．890的标准分解式是 2×5× 89 。
11．欧拉函数值(50)?= 20 。
12．7除3301的余数是 3 。
13．不定方程ax + by = c 有解的充要条件是 c b a ),( 。
14．设m 为正整数，a ，b 为两个整数，如果用m 去除a 与b 所得的余数相同，那么就称a ，b 对模m 同余 。
15．一次同余式(mod )ax b m ≡有解的充分必要条件是 b m a ),( 。
16．模7的最小非负完全剩余系是 0，1，2，3，4，5，6 。
17．（1516，600）= 4 。
18．不定方程ax + by = c (其中a ，b ，c 是整数)有整数解的充要条件是 （a ，b ）︱c 。
19．710被11除的余数是 1 。
20．77的个位数是_______ 3 ________。
初等数论第三次作业参考答案
计算题
1．写出400与600的标准分解式，并求出400与600的最大公因数。
解 4240025=?，32600235=??，32(400,600)25200=?=。 2．求128121被11除的余数。
解 因为?(11)=10，而128与11互素，所以12810≡1(mod 11)，于是
128121≡128≡7(mod 11)，所以128121被11除的余数为7。
3．求1050与858的最大公因数。
解：因为1050 = 2?3?52?7，858 = 2?3?11?13，所以(1050，858) = 2?3 = 6。
4．求1001！中末尾0的个数。
解：因为10=2?5，所以1001！中末尾相当于1001！的质因数分解式中2?5的个数。由于2<5，所以1001！的质因数分解式中2的个数比5的个数要多，因此，只要考察1001！中因子5的个数即可。因为：1001÷5=200……1，1001÷52=40……1，1001÷53
=8……1，1000÷54=1……375，又因为200+40+8+1=249，所以答案为249。即1001！中末尾0的个数为249个。
5．求不定方程3x + 5y = 20的一切非负整数解。
解：因为（3，5）=1，所以不定方程有整数解。由观察知x 0 = 0，y 0 = 4是不定方程3x +5y =20的一个整数解，所以不定方程3x +5y =20的一切整数解是 543x t y t =??=-?，其中t 取一切整数。
由00x y ≥??≥?可解得403t ≤≤，所以0,1t =，故不定方程的一切非负整数解为 04x y =??=?，51x y =??=?
。 6．求出不定方程7x + 2y = 1的一个整数解，并写出其一切整数解的表达式。
解：因为（7,2）=1,1|1，所以不定方程有解。观察知其一个整数解是
00
13x y =??=-?。 于是其一切整数解为1237x t y t =+??=--?
，t 取一切整数。 7．求不定方程15x + 10y + 6z = 61的一切整数解。
解：不定方程的一切整数解为52653665x u v y u v z v =--??=-++??=+?，其中u ，v 取一切整数。
8．计算欧拉函数值：?（100）。
解：100 = 22?52，由公式有
?（100）=
221125(1)(1)25??-?-= 40。
9．解同余式3x ≡ 8 (mod 10)。
解：因为（3,10）=1,1|8，所以同余式有解，并且只有一个解。由3108x y -=得一个解00
61x y =??=?，所以同余式的解为6(mod10)x ≡。
10．解同余式组： 1(mod 2)1(mod 3)1(mod 5)x x x ≡??≡??≡?
。
解：因为2，3，5两两互质，所以由孙子定理该同余式组有一个解。由孙子定理可得该同余式组的解为x ≡ 1(mod 30)。
11．解同余式28x ≡ 21 (mod 35)。
解 因为（28，35） = 7，而7|21，所以同余式28x ≡ 21(mod 35)有解，且有7个解。同余式28x ≡ 21(mod 35)等价于4x ≡ 3(mod 5)，解4x ≡ 3(mod 5)得x ≡ 2(mod 5)，故同余式28x ≡ 21(mod 35)的7个解为x ≡ 2，7，12，17，22，27，32(mod 35)。
12．解同余式组：
1(mod3)2(mod 7)
x x ≡??≡?。 解：由1(mod3)x ≡得1113,x t t Z =+∈，将其代入2(mod7)x ≡得
1132(mod7)t +≡，即131(mod7)t ≡，解得15(mod7)t ≡，所以
12257,t t t Z =+∈，于是12221313(57)1621,x t t t t Z =+=++=+∈。所以同余式组的解为16(mod 21)x ≡。
初等数论第四次作业参考答案
证明题
1．证明：若)(mod m b a ≡，)(mod m d c ≡，则)(mod m d b c a +≡+。
证明：由)(mod
m b a ≡，)(mod m d c ≡得)(|b a m -，)(|d c m -，由整除的性质得)]()[(|d c b a m -+-，即)]()[(|d b c a m +-+，所以)(mod m d b c a +≡+。
2．证明：设m , n 为整数，求证m +n , m -n 与mn 中一定有一个是3的倍数。
证明：若m 或n 为3的倍数，则mn 是3的倍数；
若m 是3的倍数加1，n 是3的倍数加1，则m -n 是3的倍数；
若m 是3的倍数加1，n 是3的倍数加2，则m +n 是3的倍数；
若m 是3的倍数加2，n 是3的倍数加1，则m +n 是3的倍数；
若m 是3的倍数加2，n 是3的倍数加2，则m -n 是3的倍数，结论成立。
3．证明：若c a |，d b |，则cd ab |。
证明：由c a |，d b |知存在整数p ，q 使得ap c =，bq d =，所以abpq apbq cd ==， 因为pq 为整数，所以由整除的定义知cd ab |。
4．证明：若n 为自然数，求证9n +1≡8n +9(mod 64)。
证明：因为9≡1(mod 8)，所以9k ≡1(mod 8)，k =2，3，…，n -1，于是
9n -1+…+92+9+1≡n (mod 8)，所以9(9n -1+…+92+9+1)≡ n (mod 8)，
从而9?(9-1)?(9n -1+…+92+9+1)≡ 8n (mod 64)，即9(9n -1) ≡ 8n (mod 64)，所以
9n +1≡8n +9(mod 64)。
5．若p 为奇质数，证明2p | (22p -1–2)。
证明：因为p 为质数，所以?(p )=p -1，又p 为奇质数，所以(2，p )=1，于是由欧拉定理得2p -1≡1(mod p )，两边平方得22p -2≡1(mod p )，再由同余的性质有2?22p -2≡2(mod 2p )，即：22p -1≡2(mod 2p )。所以2p |(22p -1-2)。
6．证明：整数a ，b 对模m 同余的充分与必要条件是|()m a b -。
证明：设11a mq r =+，22b mq r =+，10r ≤，2r m <。若a ≡b （mod m ）
，则12r r =，因此12()a b m q q -=-，即m ｜a －b 。
反之，若m ｜a －b ，则1212|()()
m mq q r r -+-，因此12|m r r -，但12r r m -<，故12r r =，
即a ≡b （mod m ）。
7．设a 是大于1的整数，证明44a +是合数。
证明：422224()444a a a a +=++- 222
22(2)4(22)(22)a a a a a a =+-=+-++
由于1a >且是整数，所以22221,221a a a a +->++>，且均为整数，故当a 是大于1
的整数时，4
4a +是合数。
8．设m 为整数，证明：22|(2)m m ++。
证明：因为2(1)m m m m +=+是两个连续整数的积，所以22|()m m +。
又2|2，所以由整除的性质知22|(2)m m ++。
9．设p 是质数，a 与b 是任二整数。证明：()(mod )p p p a b a b p +≡+。
证明：因为p 是质数，a 与b 是整数，所以(mod )p a a p ≡，(mod )p b b p ≡，
于是(mod )p p a b a b p +≡+。又()(mod )p a b a b p +≡+，所以
()(mod )p p p a b a b p +≡+。
10．证明：若|a m ，|b m ，并且(,)1a b =，则|ab m 。
证明：由(,)1a b =得1as bt +=，所以asm btm m +=，于是|ab m 。
初等数论练习题答案
信阳职业技术学院
2010年12月
初等数论练习题一
一、填空题
1、d(2420)=12; ?(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、18100被172除的余数是_256。
8、??? ??10365 =-1。 9、若p 是素数，则同余方程x p - 1 ≡1(mod p )的解数为 p-1 。
二、计算题
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的最小非负余数。
解：易知1271≡50（mod 111）。
由502 ≡58（mod 111）, 503 ≡58×50≡14（mod 111），509≡143≡80（mod 111）知5028 ≡（509）3×50≡803×50≡803×50≡68×50≡70（mod 111） 从而5056 ≡16（mod 111）。
故（127156+34）28≡（16+34）28 ≡5028≡70（mod 111）
三、证明题
1、已知p 是质数，（a,p ）=1，证明：
（1）当a 为奇数时，a p-1+(p-1)a
≡0 (mod p)；
（2）当a 为偶数时，a p-1-(p-1)a ≡0 (mod p)。
证明：由欧拉定理知a p-1≡1 (mod p)及(p-1)a ≡-1 (mod p)立得（1）和（2）成立。
2、设a 为正奇数，n 为正整数，试证n 2a ≡1(mod 2n+2)。 (1)
证明 设a = 2m + 1，当n = 1时，有
a 2 = (2m + 1)2 = 4m (m + 1) + 1 ≡ 1 (mod 23)，即原式成立。
设原式对于n = k 成立，则有
k a 2≡ 1 (mod 2k + 2) ?k a 2= 1 + q 2k + 2， 其中q ∈Z ，所以 12+k a = (1 + q 2k + 2)2 = 1 + q '2k + 3 ≡ 1 (mod 2k + 3)，
其中q '是某个整数。这说明式(1)当n = k + 1也成立。
由归纳法知原式对所有正整数n 成立。
3、设p 是一个素数，且1?k ?p-1。证明：k
p 1C - ≡ （-1 ）k (mod p )。
证明：设A=!
)()2(1C 1k k p p p k
p ---=- ）（ 得： k!·A =（p-1）(p-2)…（p-k ）≡（-1）(-2)…（-k ）(mod p )
又（k!，p ）=1，故A = k
p 1C - ≡ （-1 ）k (mod p )
4、设p 是不等于3和7的奇质数，证明：p 6≡1(mod 84)。
说明：因为84=4×3×7，所以，只需证明：
p 6≡1(mod 4) p 6≡1(mod3) p 6≡1(mod 7) 同时成立即可。 证明：因为84=4×3×7及p 是不等于3和7的奇质数，所以
（p ，4）=1，（p ，3）=1，（p ，7）=1。
由欧拉定理知：p ?(4)≡p 2≡1(mod 4)，从而 p 6≡1(mod 4)。
同理可证：p 6≡1(mod3) p 6≡1(mod 7)。 故有p 6≡1(mod 84)。
注：设p 是不等于3和7的奇质数，证明：p 6≡1(mod 168)。（见赵继源p86）
初等数论练习题二
一、填空题
1、d(1000)=_16_；σ(1000)=_2340_.
2、2010!的标准分解式中，质数11的次数是199__.
3、费尔马(Fermat)数是指Fn=n
22+1,这种数中最小的合数Fn 中的n=5。
4、同余方程13x ≡5(mod 31)的解是x ≡29(mod 31)___
5、分母不大于m 的既约真分数的个数为?(2)+ ?(3)+…+ ?(m )。
6、设7∣(80n -1),则最小的正整数n=_6__.
7、使41x+15y=C 无非负整数解的最大正整数C=__559__.
8、??? ??10146=_1__. 9、若p 是质数，n ∣p - 1，则同余方程x n ≡ 1 (mod p ) 的解数为n .
二、计算题
1、试求200420032002被19除所得的余数。
解：由2002≡7 (mod 19) 20022≡11(mod 19) 20023≡1 (mod 19) 又由20032004≡22004≡（22）1002≡1 (mod 3)可得：
200420032002≡20023n+1≡(20023)n ×2002≡7(mod 19)
2、解同余方程3x 14 + 4x 10 + 6x - 18 ≡ 0 (mod 5)。
解：由Fermat 定理，x 5 ≡ x (mod 5)，因此，原同余方程等价于2x 2 + x - 3 ≡ 0 (mod 5)
将x ≡ 0，±1，±2 (mod 5)分别代入上式进行验证，可知这个同余方程解是x ≡
1 (mod 5)。
3、已知a=5，m=21,求使a x ≡ 1 (mod m)成立的最小自然数x 。
解：因为（5,21）=1，所以有欧拉定理知5?(21)≡1(mod 21)。
又由于?(21)=12，所以x |12，而12的所有正因数为1,2,3,4,6,12。
于是x 应为其中使 5 x ≡ 1 (mod 12)成立的最小数，经计算知：x=6。
三、证明题
1、试证13|(54m +46n +2000)。(提示：可取模13进行计算性证明)
证明：54m +46n +2000 ≡ 252m +642n +2000 ≡（-1）2m +（-1）2n +2000 ≡ 2002≡ 0(mod
13)。
2、证明Wilson 定理的逆定理：若n > 1，并且(n - 1)! ≡ -1 (mod n )，则n 是素数。 证明：假设n 是合数，即n = n 1n 2，1 < n 1 < n ，由题设易知(n - 1)! ≡ -1 (mod n 1)，得
0 ≡ -1 (mod n 1)，矛盾。故n 是素数。
3、证明：设p s 表示全部由1组成的s 位十进制数，若p s 是素数，则s 也是一个素数。