2019年自考公共课数论初步章节讲义

《初等数论》网络课程第一讲第一部分：应考指导一、考试相关情况说明（一）课程基本情况初等数论是研究数的规律，特别是整数性质的数学分支。

它以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、不定方程和连分数理论等。

初等数论是数论的一个最古老的分支，它已经有2000年的历史，公元前300年，欧几里得发现了素数是数论的基石，他自己证明了有无穷多个素数。

公元前250年古希腊数学家埃拉托塞尼发明了一种筛法。

2000年来，数论的一个最重要的任务，就是寻找一个可以表示所有素数的统一公式，或者称为素数普遍公式，为此，人类耗费了巨大的心血。

本课程介绍初等数论中的一些基础知识。

选用的教材是闵嗣鹤、严士健编著的《初等数论》，高等教育出版社，2013年9月第22次印刷。

课程内容及基本要求：第1章整数的可除性【内容】：整除的概念，带余除法，最大公因数与辗转相除法，最小公倍数，素数与合数，素数的性质，算术基本定理，函数[x]及其应用。

【要求】：理解素数与合数的概念、素数的性质，理解算术基本定理，会用筛法求素数。

了解函数[x]的概念、性质，n!的素数分解、组合数为整数的性质。

第2章不定方程【内容】：二元一次不定方程，二元一次不定方程解的形式，二元一次不定方程有整数解的条件，利用剩余定理（辗转相除法）求二元一次不定方程的解。

多元一次不定方程，多元一次不定方程有解的条件，求简单的多元一次不定方程的解。

勾股数。

【要求】：了解二元一次不定方程解的形式、二元一次不定方程有整数解的条件，熟练掌握利用剩余定理（辗转相除法）求二元一次不定方程解的方法。

知道多元一次不定方程有解的条件，会求解简单的多元一次不定方程。

了解勾股数。

第3章同余【内容】：同余的概念及基本性质，剩余类及完全剩余系，简化剩余系与欧拉函数。

欧拉定理、Fermat 小定理及其对循环小数的应用。

【要求】：理解整数同余的概念及同余的基本性质，熟练掌握整数具有素因子的条件，会利用同余简单验证整数乘积运算的结果。

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯精品自学考 料推荐⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯全国 2018 年 7 月高等教育自学考试数论初步试题课程代码： 00418一、单项选择题（本大题共30 小题，每小题 1 分，共 30 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．m, n 是整数，下列式子可能成立的是（ ）A ． 2m=2n+1B ． 4n=4m+1C ． 3m=5n+1D ． 6m=4n+12．下列说法正确的是（ ）A ． -2 除以 -3 余数为 1B ． -5 除以 2，余数为 -1C ． -10 除以 -3，余数为 -7D ． 19 除以 2，余数为 33．任意 12 个连续整数中能被 4 除余数为 2 的数有（）个。

A ． 2B ． 3C ． 4D ． 54．设 m 为整数，则必有（ ）A ． 6|m(m+1)(m+2)B ． 5|m(m+1)(m+2)C ． 4|m(m+1)(m+2)D ． 7|m(m+1)(m+2)(m+3)5．若 m 为偶数， n 为整数，下列说法正确的是（ ）A ．mn是整数B ． m(n1)是偶数22334n是整数C ．nm n 是整数D ．m226．下列数中是合数的是（ ）A ． 17B ． 23C ． 20D ． 19 7．不超过 36 的与 12 互质的自然数有（ ）个。

A ． 11B ． 12C ． 13D ． 148．已知整数 c>0，则（ a ,b） =1 是 c=（ a, b ）的（）c c1A ．充分条件B ．必要条件C ．充分必要条件D ．关系不确定，取决于 c 的奇偶数 9．自 1 到 82 的整数中， 7 的倍数有（ ）个 A ． 12 B ． 13 C ． 10D ． 1110． x, y 为任意实数，则下列式子一定正确的是（ ）A ． [x+y] ≤ [x]+[y]B ． {x+y}<{x}+{y}C ． {x+y} ≤ {x}+{y}D ． [-x]=-[x]-111． 30!的标准分解式中，最高幂指数是 1 的质因数有（）个。

自考数论初步试题及答案一、选择题（每题4分，共20分）1. 以下哪个数是素数？A. 2B. 4C. 6D. 8答案：A2. 一个数n是合数，那么它的因数个数至少是：A. 1B. 2C. 3D. 4答案：C3. 欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的个数，那么φ(10)的值是：A. 4B. 8C. 6D. 10答案：C4. 模n的同余方程ax ≡ b (mod n)有解的充分必要条件是：A. a和n互质B. b能被a整除C. a和n的最大公约数能整除bD. a和n的最大公约数不能整除b答案：C5. 以下哪个算法是用于计算最大公约数的？A. 欧几里得算法B. 牛顿迭代法C. 欧拉算法D. 斐波那契算法答案：A二、填空题（每题5分，共20分）1. 如果p和q都是素数，那么p*q是____。

答案：合数2. 一个数n的最小素数因子是3，那么n至少是____。

答案：33. 如果a和b互质，那么a*b的欧拉函数φ(a*b)等于____。

答案：φ(a) * φ(b)4. 模n的乘法逆元是指一个数x，使得ax ≡ 1 (mod n)，如果a和n 互质，那么a在模n下的乘法逆元是____。

答案：存在且唯一三、解答题（每题15分，共40分）1. 证明：如果p是一个大于3的素数，那么p一定能被6整除或者p-1能被6整除。

答案：证明：设p为大于3的素数，p除以6的余数只能是1、2、3、4、5中的一个。

因为p是素数，所以p不能被2整除，因此p除以6的余数不能是2或4。

如果p除以6的余数是3或5，那么p-1除以6的余数就是3或5的补数，即3或5，因此p-1能被6整除。

如果p除以6的余数是1，那么p-1除以6的余数是5，因此p-1也能被6整除。

综上，p一定能被6整除或者p-1能被6整除。

2. 已知a=2，b=3，n=7，求模7的同余方程2x ≡ 3 (mod 7)的解。

答案：首先，我们需要找到2在模7下的乘法逆元，即找到一个数y，使得2y ≡ 1 (mod 7)。

初等数论初等数论自学安排第一章：整数的可除性（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 及合数模指标组、 特征函数习题要求123p ：3。

➢ 第一章 整除 一、主要内容筛法、[x]和{x}的性质、n ！的标准分解式。

二、基本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除 整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理：带余除法定理和算术基本定理。

认真体会求二个数的最大公因数的求法的理论依据，掌握素数的定义以及证明素数有无穷多个的方法。

1全国2019年4月高等教育自学考试数论初步试题课程代码：00418一、单项选择题（每小题1分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．若a 、b 均为整数，则下列数不一定是整数的是（ ）A ．2a －bB ．2b a +2C ．b a -2D ．23b a + 2．200被－3除的带余除法表达式是（ ）A ．1)67()3(200--⨯-=B ．5)65()3(200+-⨯-=C ．2)66()3(200+-⨯-=D ．4)()68()3(200－+-⨯-= 3．m 为偶数时，模m 的绝对最小完全剩余系为（ ）A ．0，1，2…，m －2，m －1B ．－m ，－（m －1），…，－2，－1C ．－21-m ，…，－1，0，1，…，21-m D ．－2m ，…，－1，0，1，…，12-m 4．［－0.123］＝（ ） A ．0B ．－1C ．0.877D ．0.123 5．下列与1184互为亲和数的数是（ ）A ．1210B ．1320C ．220D ．284 6．下列不属于三元一次不定方程组的是（ ）A ．⎪⎩⎪⎨⎧=++=++100100315z y x z y x B ．⎩⎨⎧=++=++502330z y x z y x C ．⎩⎨⎧=++=79z y x xyz D ．⎩⎨⎧=++=+72320z y x y x 7．关于质数、合数，下列说法正确的是（ ）A ．两个质数之和一定是质数B ．两个质数之积一定是质数C ．两个合数之和一定是合数D ．两个合数之积一定是合数28．下列各数中，能被11整除的是（ ）A ．75523B ．868967C ．1095874D ．38635 9．若a 为整数，则以下式子一定正确的是（ ）A ．a aB ．1 aC ．a 0D ．a 110．24的正约数中，有（ ）A ．3个质数，5个合数B ．2个质数，4个合数C ．3个质数，4个合数D ．2个质数，5个合数 11．下列式子成立的是（ ） A ．132≡2（mod3）B ．－2≡2（mod8）C ．6≡20（mod7）D ．25≡－6（mod3） 12．不超过37而与37互质的正整数的个数为（ ）A ．36B ．35C ．37D ．38 13．若k 为整数，则k k +2与12+-k k 分别为（ ）A ．偶数 奇数B ．奇数 奇数C ．偶数 偶数D ．奇数 偶数 14．若（a,b ）=1，c 为任意正整数，则下列错误的是（ ）A ．（a,b+ac ）＝1B ．（a,a+b ）=1C ．（ac,b ）=1D ．（b,a+b ）=1 15．对于自然数a 、b ，下列说法错误的是（ ）A ．若a b ，则（a ，b ）＝aB ．若a b ，则［a ，b ］＝bC ．若［a ，b ］＝（a ，b ），则a ＝bD ．若（a ，b ）＝1，则［a ，b ］＝1 16．学校排练体操，要求队伍分别变成12行、15行、18行、24行时都能成为矩形，则最少应有（ ）人参加排练。

数论选讲一、整除1．整数是离散的，每两个整数之间的距离至少为1．即1a b a b <⇔-≤，,a b Z ∈2．带余除法．设0b >，对于任一整数a ，总可以找到一对唯一确定的q ，r 满足 a qb r =+，0r b ≤<．我们称r 为a 除以b 的余数．当0r =时，我们说a 被b 整除或b 整除a ，记为|b a ．并称a 是b 的倍数或b 是a 的约数（因数），此时b a ≤．当0r ≠时，我们说a 不被b 整除或b 不整除a ，记为|b a /．3．如果正整数a 除了1及a 以外没有其他的约数，则称a 为质数，否则称a 为合数． 100以内的质数如下： 2，3，5，7，11，13，17，19， 23，19，31，37，41，43，47，53，59，61，67，71，73，79，83，89，914．唯一分解定理．每一个大于1的自然数n 都可写成质数的连乘积，即表示成12121ki k k i i n p p p p αααα===∏的形式，其中12k p p p <<<为质数，*i N α∈，且这种表示是唯一的．5．利用唯一分解定理，我们可以得到关于n 的正约数的两个性质：n 的正约数个数为 121()(1)(1)(1)(1)kk i i d n αααα==+++=+∏． n 的所有正约数之和为 01()ik j i j i n p ασ===∑∏．6．若|x a 且|x b ，则称x 为a 、b 的公约数．设d 为所有x 中的最大者，则称d 为a 、b 的最大公约数，记作(,)d a b =．7．若|a y ，|b y ，则称y 为a 、b 的公倍数．设m 为所有y 中大于零的最小者，则称m 为a 、b 的最小公倍数，记作[,]m a b =．8．对于任意正整数a 、b ，都有(,)[,]ab a b a b =．9．贝佐特（1730~1783）定理．设(,)d a b =，则存在整数u 、v ，使得ua vb d +=．10．如果|a c ，|b c ，(,)1a b =，则|ab c ．【例题选讲】1、证明两个连续正整数的积不可能是完全平方数，也不可能是完全立方数．反设存在正整数x ，y ，使x (x ＋1)＝y 2，由于x ，x ＋1互质，故x ，y 都是完全平方数． 两个完全平方数相差1，只有0与1满足要求，此时x ＝0，y ＝0，与x 为正整数矛盾． 又反设存在正整数x ，y ，使x (x ＋1)＝y 3，由于x ，x ＋1互质，故x ，y 都是完全立方数． 设x ＝u 3，x ＋1＝v 3(u ，v ∈N *，v ＞u )，v 3－u 3＝(v －u )(v 2＋vu ＋u 3)＝1，由于v －u ≥1，v 2＋vu ＋u 2≥7，故v 3－u 3＝1不成立，故证．2、设m ＞n ≥1，(m ，n )＝d ，证明：d mC n m 为整数． 证明：由于C n m 为整数，又n m C n m ＝n m ×m !n !(m －n )!＝C n －1m －1为整数． 存在x ，y ∈Z ，使xm ＋yn ＝d ，所以，d m C n m ＝xm ＋yn m C n m ＝x C n m ＋y n m C n m＝x C n m ＋y C n －1m －1∈Z ．3、证明：若(m ，n)＝1，则m|C n m ＋n －1． C n m ＋n －1＝m m ＋n C m m ＋n ⇒mC n m ＋n －1＋nC n m ＋n －1＝mC m m ＋n ⇒ nC n m ＋n －1＝m(C m m ＋n －C n m ＋n －1)， ∴ m|n C n m ＋n －1，但(m ，n)＝1，故m|C n m ＋n －1． 4、在n 2与(n ＋1)2之间任取若干个互不相同的整数，则这些整数两两的乘积都互不相等． 证明：若只取3个整数a ，b ，c ，满足n 2＜a ＜b ＜c ＜(n ＋1)2，则ab ＜ac ＜bc ．故只有取的数至少有4个时才有可能使两两的积相等．设n 2＜a ＜b ＜c ＜d ＜(n ＋1)2，且有ad ＝bc ．于是b a ＝d c ，令b a ＝d c ＝u v(u ，v ∈N *， (u ，v )＝1)． 于是，必有b ＝up ，d ＝uq ，a ＝vp ，c ＝vq ．由c ＞b ＞a ，知u ＞v ，q ＞p ．所以，u ≥v ＋1，q ≥p ＋1．d ＝uq ≥(v ＋1)(p ＋1)＝vp ＋p ＋v ＋1＝a ＋(p ＋v )＋1≥n 2＋2pv ＋1≥n 2＋2a ＋1＞n 2＋2n ＋1＝(n ＋1)2．与d ＜(n ＋1)2矛盾．5、已知a 、b 为正整数，并且ab 2|(a 3＋b 3)，求证a ＝b ．设(a ，b )＝d ，且a ＝a 1d ，b ＝b 1d (a 1，b 1为自然数)，则(a 1，b 1)＝1.由ab 2|(a 3＋b 3)，可设a 3＋b 3＝kab 2 (k ∈N *)，∴ a 3＝b 2(ka －b )．即a 31＝b 21(ka 1－b 1)．于是，b 1|a 1，故(a 1，b 1)＝b 1＝1． a 31|(ka 1－1)，于是a 1|(ka 1－1)，∴ a 1|1，于是a 1＝1． ∴ a ＝b ＝d ．注：由于ab 2与a 3、b 3均为3次式，故可同时约去d 3而不影响问题的结论．故可设(a ，b )＝1来做．又证：设a 3＋b 3ab 2＝k (k ∈N *)，即(a b )2＋b a ＝k ．记x ＝a b，则x 为有理数，且x 3－kx ＋1＝0． 此方程的有理根只能为x ＝±1，但a ，b 均为自然数，故x ＝1，∴a ＝b ．6、存在1000个连续正整数，其中恰有20个素数．证明：取1001!＋2，1001!＋3，…，1001!＋1000，1001!＋1001，这1000个数都是合数． 记1001!＋2＝a ．则a ，a ＋1，a ＋2，…，a ＋999均为合数．去掉a ＋999，添上a －1，又得1000个数：a －1，a ，a ＋1，…，a ＋998．由于去掉一个合数而添了一个整数，故所得1000个数中至多有1个素数．再去掉a ＋998而添上a －2，此时，这1000个数中素数的个数比刚才的1000个数多1个或相同或减少1个．这一过程可以一起进行到得到1，2，…999，1000这1000个数为止．此时，这1000个数中的素数个数多于20个(2至100中就有25个素数)由于每次置换1个数时，所得的1000个与与原1000个数相比较，素数的个数只能增加1个或相同或减少1个．于是这一过程中每次所得素数个数至多变化1个，于是必有某个时刻，恰有20个素数．说明：《离散的零点定理》设f (n )是定义在整数上的函数，取值也是整数．且|f (n ＋1)－f (n )|≤1，且存在不同两个整数a ，b (a ＜b )，使f (a )f (b )＜0，则必存在整数c ，满足a ＜c ＜b ，使f (c )＝0．7、求出具有下述性质的正整数n ：它被≤n 的所有正整数整除．解：设q 2≤n ＜(q ＋1)2，(q ∈N *)，则[n]＝q ．令n ＝q 2＋r(0≤r ≤2q)．由于q|n ，q|q 2，故q|r ⇒r ＝0，q ，2q ．即所有满足n ＝q 2，q 2＋q ，q 2＋2q 的正整数均为本题的解．解：显然，n ＝1，2，3，4满足题意．现设n ≥5．由此题知，n ＝q 2，q 2＋q ，q 2＋2q ．且q ≥2．又n 能被q －1整除．当n ＝q 2＝q(q －1)＋q ，于是q －1|q ⇒q －1＝1⇒q ＝2时，此时，n ＝4；当n ＝q 2＋q ＝(q －1)(q ＋2)＋2，有q －1|2⇒q ＝2，3，此时，n ＝6，12；当n ＝q 2＋2q ＝(q －1)(q ＋3)＋3，有q －1|3⇒q ＝2，4，此时，n ＝8，24．∴ n ＝1，2，3，4，6，8，12，24．8、证明：有无穷多个n ，满足：n|2n ＋1．分析：证明满足某要求的整数有无穷多个，通常有：⑴ 给出一个公式，可以由此公式得出无穷多满足要求的数；⑵ 给出一个递推式，可以由其中任一个满足要求的数得出只一个满足要求的数；且这些数都互不相同；⑶ 用数学归纳法证明之．解法一：n ＝1时，1|21＋1；n ＝3时，3|23＋1；n ＝9时，9|29＋1．即n ＝30，31，32时均满足要求．故推测3k |23k＋1对于一切正整数k 成立．下用数学归纳法证明：设3k |23k ＋1．则存在正整数t ，使23k ＝3k t －1．故23k ＋1＋1＝(3k t －1)3＋1＝33k t 3－32k ＋1t 2＋3k ＋1t ＝3k ＋1t(32k －1t 2－3k t ＋1)．即3k ＋1|23k ＋1＋1． ∴ 由数学归纳原理知，对于一切正整数k ，都3k |23k＋1．从而有无穷多的整数n ＝3k 使n|2n ＋1，解法二：前已有n ＝1时，3|21＋1＝3，又有23|23＋1＝9，9|29＋1＝513．故推测：若m k |2m k ＋1，记m k ＋1＝2m k ＋1，则m k ＋1|2m k ＋1＋1．下用数学归纳法证明之：由于2m k ＋1为奇数，故m k 为奇数，令2m k ＋1＝m k u ，u 为奇数．即m k ＋1＝m k u ．于是，2m k ＋1＋1＝(2m k )u ＋1＝(2m k ＋1)((2m k )u －1－(2m k )u －2＋…＋1)＝m k ＋1((2m k )u －1－(2m k )u －2＋…＋1)．即m k ＋1|2m k ＋1＋1成立．由数学归纳法知推测成立． 说明：解法一即给出一个解的公式，解法二给出了一个递推．均用数学归纳法证明．9、证明：任意正整数n 可以表示成a －b 的形式，其中a ，b 是正整数，且a 与b 不同的素因子个数相同．证明：n ＝pn －(p －1)n ．若n 为偶数，取p ＝2，a ＝pn ，b ＝n ．此时，a ，b 的不同素因子个数都与n 相同． 若n 为奇数，取不能整除n 的最小素数p ，p ≥3．此时，p －1的素因子或者只有2(p －1＝2k )，或者除2外都是n 的因子(因小于p 的素数都能整除n)，此时a ，b 的素因子都比n 多1个．故证．二、同余11．设*m N ∈，如果整数a 、b 除以m 的余数相同，则其差a b -必被m 整除，即存在q Z ∈使得a b qm -=．则称a 、b 模m 同余，或简称同余．记为()mod a b m ≡．12．同余的基本性质．①()mod a a m ≡．②若()mod a b m ≡，则()mod b a m ≡．③若a b ≡，()mod b c m ≡，则()mod a c m ≡．④若a b ≡，()mod c d m ≡，则 ()mod xa yc xb yd m +≡+，x 、y Z ∈．()mod ac bd m ≡． ()mod n n a b m ≡，n N ∈．⑤若()mod ac bc m ≡，则mod(,)m a b c m ⎛⎫≡ ⎪⎝⎭．⑥若()mod a b m ≡，|n m ，则()mod a b n ≡． ⑦若()mod i a b m ≡，则()12mod[,,,]k a b m m m ≡．13．同余是一种等价关系，整数集Z 可以根据模m 来分类：如果a 、b 模m 同余，则a 、b 属于同一类，否则不属于同一类．这样可以得到模m 的m 个剩余类（同余类），即： {}i M i km k Z =+∈，0,1,2,,1i m =-．从每一类中各取一个数作为代表得到的m 个数称为模m 的一个完全剩余类，简称完系， 当m 为奇数时，其由绝对值最小的数组成的完系为： 10,1,2,,2m -⎧⎫±±±⎨⎬⎩⎭． 当m 为偶数时，其由绝对值最小的数组成的完系为：0,1,2,,(1),22m m ⎧⎫±±±-⎨⎬⎩⎭． 14．在模m 的m 个剩余类{}i M i km k Z =+∈（0,1,2,,1i m =-）中，如果i 与m 互质，那么i M 中每一个数均与m 互质．这样的剩余类共有()m ϕ个，()m ϕ是1、2、…、m 中与m 互质的个数，称为欧拉函数．15．在()m ϕ个剩余类中各取一个代表，称为模m 的缩剩余系，简称缩系．质数p 的缩系由1p -个数组成，即 {}1,2,,1p -，或11,2,,2p -⎧⎫±±±⎨⎬⎩⎭． 16．设正整数m 、n 互质，则()()()mn m n ϕϕϕ=． 事实上，如果{}12,,,t a a a ，{}12,,,s b b b 分别是模m 与模n 的缩系， 那么{}1,1i j mb na i s j t +≤≤≤≤是模mn 的缩系．17．设1i k i i n p α==∏，i p 为不同的质数，*i N α∈．则1111()(1)(1)i kk i i i i i n n p p p αϕ-===-=-∏∏． 18．欧拉定理：设(),1a m =，则()()1mod m a m ϕ≡．19．费马小定理：设p 为质数，则()mod p a a p ≡．当(),1a p =时，()11mod p a p -≡．20．中国剩余定理（孙子定理）：设正整数1m 、2m 、…、k m 两两互质，则对于任意给定的整数1a 、2a 、…、k a ，同余方程组()()()1122mod mod mod k k x a m x a m x a m ≡⎧⎪≡⎪⎨⎪⎪≡⎩一定有解．令1k i i M m ==∏，则其解为 1k i i i iM x a b m =≡⋅∑． 其中i b 满足()1mod i i iM b m m ⋅≡． 【例题选讲】10、证明：若整数a ，b ，c 满足a ＋b ＋c ＝0，记d ＝a 1999＋b 1999＋c 1999．则|d|不是素数．证明：首先，u n ≡u(mod 2)，故d ＝a 1999＋b 1999＋c 1999≡a ＋b ＋c ≡0(mod 2)，即2|d ．又由Fermat 定理，u 3≡u(mod 3)⇒u 3k ≡u(mod 3)，从而u 1999＝u 33·74＋1≡u 74＋1＝u 75≡u 25＝u 24＋1≡u 8＋1≡u(mod 3)，故d ＝a 1999＋b 1999＋c 1999≡a ＋b ＋c ≡0(mod 3)，∴ 6|d ，即|d|不是素数．11、用1，2，3，4，5，6，7这7个数码组成7位数，每个数码恰用一次，证明：这些七位数中没有一个是另一个的倍数．设有两个这样的七位数a ，b ，(a ＞b)，满足a ＝bc ，其中c 为大于1的整数．由于1＋2＋3＋4＋5＋6＋7＝28≡1(mod 9)，故a ≡b ≡1(mod 9)．若a ＝bc ，则bc ≡1(mod 9)，于是，c ≡1(mod 9)．但c ＞1，从而c ≥10．此时bc 不是七位数，与a 是七位数矛盾．12、设p 为素数，a ≥2，m ≥1，a m ≡1(mod p)，a p －1≡1(mod p 2)．求证：a m ≡1(mod p 2)．证明：a m ≡1(mod p)⇒a m ＝1＋px ，故a pm ＝(1＋px)p ＝1＋p 2(……)．所以，a pm ≡1(mod p 2)．∵a p－1≡1(mod p2)⇒a(p－1)m≡1(mod p2)．同乘以a m：a pm≡a m(mod p2)∴a m≡a pm≡1(mod p2)13、设p为给定正整数，m，n为任意正整数，试确定(2p)2m－(2p－1)n的最小正值．解：(2p)2m≡1(mod 2p－1)，故(2p)2m－(2p－1)n≡1(mod 2p－1)．若存在m，n，使(2p)2m－(2p－1)n＝1，则有(2p)2m－1＝(2p－1)n⇒((2p)m＋1)((2p)m－1)＝(2p－1)n．由于(2p)m＋1，(2p)m－1)＝1，故(2p)m＋1＝a n，(2p)m－1＝b n，且(a，b)＝1．即a n－b n ＝2．只有n＝1，a＝b＋2时成立，此时，解(2p)2m－(2p－1)＝1⇒2p((2p)2m－1－1)＝1这是不可能的．故所求最小值≠1．再若存在m，n使(2p)2m－(2p－1)n＝(2p－1)＋1＝2p，此时，(2p)2m－(2p－1)n≡－(－1)n≠0(mod 2p)，故不可能．于是，所求最小值≥4p－2＋1＝4p－1．取m＝1，n＝2，得(2p)2－(2p－1)2＝4p－1．∴所求最小值为4p－1，当m＝1，n＝2时取得此最小值．14、数列{x n}：1，3，5，11，…，满足x n＋1＝x n＋2x n－1(n≥2)，数列{y n}：7，17，55，161，…，满足y n＋1＝2y n＋3y n－1(n≥2)，证明：这两个数列没有相同的项．分析：证明这两个数列mod 8后都是周期数列．证明：mod 8：数列x n(mod 8)：1，3，5，3，5，…．若x2k－2≡3，x2k－1≡5(mod 8)成立，则x2k＋1≡5＋2×3＝11≡3(mod 8)，x2k≡3＋2×5＝13≡5(mod 8)．即x2n≡3，x2n＋1≡5(mod 8)对于一切n∈N*成立．而数列y n(mod 8)：7，1，7，1，…．若y2k－1≡7，y2k≡1(mod 8)成立，则y2k＋1≡1×2＋7×3＝23≡7(mod 8)，y2k＋2≡7×2＋1×3＝17≡1(mod 8)．即y2n≡1，y2n＋1≡7(mod 8)对于一切n∈N*成立．在{x n}中，x1＝1≡1(mod 8)，但y n是单调增的，且y1＞1，故y n＞1，于是不可能y n ＝1，故证．说明：利用抽屉原理可以证明：若数列{x n}满足递推关系：x n＋k＝f(x n＋k－1，x n＋k－2，…x n)，其中f为k元整系数多项式．初始值x1，x2，…，x k为给定整数．于是{x n}为一整数数列．则{x n}模m(m＞1，m∈N*)后终将成为周期数列(可能除去开始的若干项)．15、设m是给定正整数，证明：由x1＝x2＝1，x n＋2＝x n＋1＋x n(k＝1，2，…)定义的数列{x n}的前m2个项中，必有一个能被m整除．证明：记x i≡y i(mod m)(0≤y i≤m－1)．取数组(y1，y2)，(y2，y3)，…，(y i，y i＋1)，…．由于只有m2个不同的数组．故取m2＋1个数组，必有两个数组相同，即存在1≤i＜j ≤m2＋1，使y i＝y j，y i＋1＝y j＋1，于是(y i，y i＋1)＝(y j，y j＋1)，取满足此要求的最小的i，则i必须为1．否则，由i＞1，则y i－1≡y i＋1－y i，y j－1≡y j＋－y j(mod m)，1于是，y i－1＝y j－1，得(y i－1，y i)＝(y j－1，y j)，这与i的最小性矛盾．从而i＝1．即存在(y j，y j＋1)＝(1，1)(j≤m2＋1)，此时y j－1＝0，即m|x j－1．故证．16、连结正n 边形的顶点，得到一个n －折线(即用这个正n 边形的n 个顶点为顶点连出一个有n 条边的闭折线)．证明：若n 为偶数，则连线中有两条平行线；若n 为奇数，则连线中不可能恰有两条平行线．证明：按逆时针顺序把为n 个顶点编号：0，1，2，…，n －1．且按a 0－a 1－…－a n －1－a n ＝a 0连成折线，其中a 0，a 1，…，a n －1是0，1，2，…，n －1的一个排列．由于a i 为正n 边形的顶点，故a i a i ＋1∥a j a j ＋1⇔⌒a i a i ＋1＝⌒a j a j ＋1⇔a i ＋a i ＋1≡a j ＋a j ＋1(mod n)．⑴ 当n 为偶数时，2 |/ n ⁄－1，故模n 的任一完系之和≡0＋1＋…＋(n －1)＝12n(n －1)≡/0(mod n)．但Σi ＝0n －1(a i ＋a i ＋1)＝Σi ＝0n －1a i ＋Σi ＝0n －1a i ＋1＝2Σi ＝0n －1a i ＝2×12n(n －1)≡0(mod n)． 这说明全体a i ＋a i ＋1不构成完系．所以，必有0≤i ，j ≤n －1，i ≠j ，使a i ＋a i ＋1≡a j ＋a j ＋1(mod n)，于是必有两条平行线．若n 为奇数，若恰有一对边a i a i ＋1∥a j a j ＋1，则a i ＋a i ＋1(mod n)的剩余类中，必有一对剩余类r 出现2次，故必有一对剩余类s 没有出现，于是Σi ＝0n －1(a i ＋a i ＋1)＝Σi ＝0n －1a i ＋Σi ＝0n －1a i ＋1＝2Σi ＝0n －1a i ≡0(mod n)， 另一方面，Σi ＝0n －1(a i ＋a i ＋1)≡0＋1＋…＋(n －1)＋r －s ≡r －s ≠0(mod n)． 这说明，n 为奇数时，不可能恰有一对边平行．17、设n 为奇数，n ≥3．集合S ＝{0，1，2，…，n －1}．证明：在S 中去掉任一个元后，余下的元都能划分成两个集合，每个集合都有n －12个元，且两组的和模n 同余． 证明：1° 首先，若去掉的元为0，⑴ n ＝4k ＋1，则余下4k 个元分成2k 对：{1，4k}，{2，4k －1}，…，{2k ，2k ＋1}，每对的和mod n 均为0．于是，任取其中k 对为一组，余下k 对为另一组，两组的和模n 同余；⑵ n ＝4k ＋3，余下4k ＋2个元中，先取{1，2，4k}，{3，4k ＋1，4k ＋2}，再把其余的数分成2k －2对：{4，4k －1}，{5，4k －2}，…，{2k ＋1，2k ＋2}，每对的和mod n 均为0．于是，任取其中k －1对加上{1，2，4k}为一组，余下k －1对加上{3，4k ＋1，4k ＋2}为另一组，两组的和模n 同余；2° 若去掉的数为a ，则把所有的数都加n －a 得到集合S '＝{n －a ，n －a ＋1，…，n ，n ＋1，2n －a －1}，S '仍是模n 的完系．去掉S 中的a 对应于S '中的n ．于是S '可以按1°分成满足要求的两组，再把分好的数各减去n －a 即得到S 的一个分法．18、一个立方体的顶点标上数＋1或－1，各面中心标上一个数，它等于该面4个顶点上标的数的乘积．证明：这样标出的14个数的和不能为0．证明：设此14个数的和为S ．现把任一个标－1的顶点改为标＋1，则它同时使相关3个面上的数的符号改变，改变后14个顶点上数的和为S '．于是S －S '＝2(±1±1±1±1)但任何4个＋1或－1的和为偶数，于是S －S '≡0(mod 4)．这样一起做下去，直到所有顶点标的数都为＋1，此时和S "＝14≡2(mod 4)．于是S ≡2(mod 4)，从而S ≠0．19、求所有正整数n ，使由n －1个数码1及1个数码7组成的n 位数都是素数．解：对于n ，所有这样的n 位数都可写成N ＝A n ＋6×10k (其中，A n 表示由n 个1组成的n 位数，k ＝0，1，…，n －1)．若3|n ，则3|A n ，于是3|N ．此时N 不是素数．现设3 |⁄ n ， A n注意A 6≡0(mod 7)，故有A 6k ＋r ≡A r (k ∈N *，1≤r ≤6)．由于(10，7)＝1，故1，10，102，…，105是7的一个缩系，从而6×10k (k ＝0，1，2，3，4，5)也是mod 7)的一个缩系．又有下表：且6×106k ＋r ≡6×10r (k ∈N *，0≤r ≤5)．∴ n ＞6时，按n ≡1，2，4，5(mod 6)，取k ＝0，4，5，2，即有7|N ．此时N 不是素数．而n ＝4时，7111＝13×547；n ＝5时，11711＝7×1673，即n ＝4，5均不满足要求． ∴ n ＝1，2．三、高斯函数与不定方程21．高斯函数[]x ：表示不超过x 的最大整数，称为x 的整数部分．同时记{}[]x x x =-为x 小数部分（或称尾数部分）．22．[]x 的基本性质：①x R ∀∈，[][]11x x x x -<<+≤；②x R ∀∈，[]{}x x x =+；③x R ∀∈，n Z ∈，[][]x n x n +=+，{}{}x n x +=．④x R ∀∈，y R ∈，[][][]x y x y ++≤，{}{}{}x y x y ++≥．⑤0x ∀≥，0y ≥，[][][]xy x y ≥．【例题选讲】20、若n≡4(mod 9)，证明不定方程x3＋y3＋z3＝n没有整数解．证明：x≡1，2，0(mod 3)⇒x3≡1，2，0(mod 9)，∴x3＋y3＋z3≡0，1，2，3，6，7，8(mod 9)．故此方程无解．21、确定方程x41＋x42＋…＋x4 14≡1599的全部非负整数解．解：x4≡0，1(mod 16)，于是x41＋x42＋...＋x4 14≡0，1，2， (14)而1599≡5(mod 16)．故无解．22、证明：方程x!y!=z!有无穷多组正整数解(x，y，z)满足x＜y＜z．证明：由于n!=n·(n－1)!.故(n!)!=(n!)(n!－1)!从而取x＝n，y＝n!－1，z＝n!，则有无穷多个解．说明：给出了一个解的公式．23、求不定方程x4＋y4＋z4＝2x2y2＋2y2z2＋2z2x2＋24的全部整数解．解：若(x，y，z)是其一个解，则(±x，±y，±z)也是方程的一个解．x4＋y4＋z4－2x2y2－2y2z2－2z2x2＝x4＋y4＋z4－2x2y2－2y2z2＋2z2x2－4z2x2＝(x2－y2＋z2)2－(2zx)2＝(x2－y2＋z2＋2zx)(x2－y2＋z2－2zx)＝(x＋y＋z)(x－y＋z)(x－y－z)(x＋y－z)＝－(x＋y＋z)(－x＋y＋z)(x－y＋z)(x＋y－z)．于是，原方程即(x＋y＋z)(－x＋y＋z)(x－y＋z)(x＋y－z)＝－23×3．由于x＋y＋z，－x＋y＋z，x－y＋z，x＋y－z的奇偶性相同．若它们全为奇数，则其积为奇数，不可能等于－24，若它们全为偶数，则其积可以被24整除，也不可能等于－24．从而本题无满足要求的解．解法2由于左边为偶数，故x，y，z或都为偶数，或两奇一偶．⑴若x，y，z两奇一偶，不妨设x，y为奇数，z为偶数，则x4≡1(mod 16)，y4≡1(mod 16)，z4≡0(mod 16)，x4＋y4＋z4≡2(mod 16)x2≡1，9(mod 16)，y2≡1，9(mod 16)，z2≡0，4(mod 16)．于是x2y2≡1，9(mod 16) 2x2y2＋2y2z2＋2z2x2＋24＝2x2y2＋2z2(x2＋y2)＋24≡2＋0＋8≡10(mod 16)．从而x4＋y4＋z4≡/2x2y2＋2y2z2＋2z2x2＋24(mod 16)；⑵若x，y，z均为偶数，则x4＋y4＋z4≡0(mod 16)，2x2y2＋2y2z2＋2z2x2＋24≡8(mod 16)，仍有x4＋y4＋z4≡/2x2y2＋2y2z2＋2z2x2＋24(mod 16)从而本题无满足要求的解．24、证明：方程y＋y2＝x＋x2＋x3没有非零整数解．证明：反设存在非零整数x，y满足方程，则(y－x)(y＋x＋1)＝x3．下证(y－x，y＋x＋1)＝1．设(y－x，y＋x＋1)＝p，则p|x，于是由p|y－x，知p|y，但p|y＋x＋1，故p|1．即p＝1．于是y－x与y＋x＋1都是完全立方数，设y＋x＋1＝a3，y－x＝b3，x＝ab．则a3－b3＝2x＋1⇒a3－b3＝2ab＋1⇒(a－b)(a2＋ab＋b2)＝2ab＋1．由x＝ab，①若ab＞0，则x＞0．有a＞b．故a－b≥1，a2＋ab＋b2＞2ab＋ab＝3ab ＝2ab＋ab≥2ab＋1．从而(a －b )(a 2＋ab ＋b 2)＞2ab ＋1，矛盾；② ab ＝0，则x ＝0，与x 非零矛盾；③ ab ＜0，于是2x ＋1＜0，故a ＜b ．b ＞0，a ＜0，|a －b |≥2．a 2＋ab ＋b 2≥2|ab |＋ab ＝|ab |，所以|a －b ||a 2＋ab ＋b 2|≥2|ab |，而|2ab ＋1|＜2|ab |，从而|(a －b )(a 2＋ab ＋b 2)|＞|2ab ＋1|，矛盾．故证．25、求不定方程(n －1)!＝n k －1的全部正整数解．解：n ＝2时，有解(n ，k )＝(2，1)．当n ＞2时，左边为偶数，故n 只能为奇数．取n ＝3，(3－1)!＝2＝31－1，故有解(n ，k )＝(3，1)；取n ＝5，(5－1)!＝24＝52－1，故有解(n ，k )＝(5，2)．下设n ≥7且n 为奇数．于是n －12为整数且n －12≤n －4，所以，2×n －12|(n －2)!，从而(n －1)2|(n －1)!．∴ (n －1)2|n k －1＝[(n －1)＋1]k －1＝(n －1)k ＋C 1k (n －1)k －1＋C 2k (n －1)k －2＋…＋C k －2k(n －1)2＋k (n －1)．∴ (n －1)2|k (n －1)⇒(n －1)|k ⇒k ≥n －1．此时，n k －1≥n n －1－1＞(n －1)!，故n ≥7时不定方程无解．即方程的解为(n ，k )＝(2，1)，(3，1)，(5，2)．26、证明方程x 2＋y 2＋z 2＝3xyz 有无穷多组正整数解(x ，y ，z )．证明 由于方程具有对称性，故可改证此方程的满足x ≤y ≤z 的解有无数组．若x ＝y ＝z ＝a (a ∈N*)，则3a 2＝3a 3⇒a ＝1．即方程有解(1，1，1)；若x ＝y ＝1，则得2＋z 2＝3z ，得方程的另一组解为(1，1，2)；若x ＝1，y ＝2，则得方程z 2－6z ＋5＝0，得方程的另一组解(1，2，5)；现设(a 0，b 0，c 0) (其中a 0＜b 0＜c 0)是方程的一组正整数解，即a 20＋b 20＋c 20＝3a 0b 0c 0成立，考虑方程b 20＋c 20＋z 2＝3b 0c 0z ，即z 2－3b 0c 0z ＋(b 20＋c 20)＝0，此方程必有一正整数解z ＝a 0，由韦达定理，其另一解为z 1＝3b 0c 0－a 0必为正整数．于是原方程必有解(b 0，c 0，3b 0c 0－a 0)且这一组解也满足b 0＜c 0＜3b 0c 0－a 0．令a 1＝b 0，b 1＝c 0，c 1＝3b 0c 0－a 0为方程的一组满足a 1＜b 1＜c 1的正整数解，则又可从此解出发得到方程的另一组解(b 1，c 1，3b 1c 1－a 1)．这一过程可以无限延续下去，从而原方程有无穷多组解．27、求不定方程组 ⎩⎨⎧x ＋y ＋z ＝3，x 3＋y 3＋z 3＝3．的全部整数解． 解：(1，1，1)是一组解．消去z ： x 3＋y 3＋(3－x －y)3＝3⇒3(x ＋y)2－xy(x ＋y)－9(x ＋y)＋8＝0．∴ (x ＋y)(xy －3(x ＋y)＋9)＝8．于是x ＋y|8⇒x ＋y ＝±1，±2，±4，±8．若x ＋y ＝1，则xy ＝2(无解)；x ＋y ＝－1，xy ＝－20⇒x ＝－5，y ＝4，z ＝4，或x ＝4，y ＝－5，z ＝4；x ＋y ＝2，xy ＝1⇒x ＝y ＝1，z ＝1；x ＋y ＝－2，xy ＝－19(无解)；x ＋y ＝4，xy ＝5(无解)；x ＋y ＝－4，xy ＝－23(无解)；x ＋y ＝8，xy ＝16⇒x ＝y ＝4，z ＝－5；x ＋y ＝－8，xy＝－34(无解)．∴ 解为(1，1，1)，(－5，4，4)，(4，－5，4)，(4，4，－5)．28、求不定方程x 3＋x 2y ＋xy 2＋y 3＝8(x 2＋xy ＋y 2＋1)的全部整数解．解：(x ＋y)((x ＋y)2－2xy)＝8((x ＋y)2－xy ＋1)．令x ＋y ＝u ，xy ＝v ，则得u(u 2－2v)＝8(u 2－v ＋1)是一个关于v 的一次方程．显然u 必为偶数，设u ＝2w ，则得w(2w 2－v)＝2(4w 2－v ＋1)．∴ v ＝2w 3－8w 2－2w －2＝2w 2－4w －8－18w －2．于是w －2＝±1，±2，±3，±6，±9，±18． ∴ ⎩⎨⎧w ＝ 3， 1， 4， 0，5，－1，8，－4，11，－7， 20，－16；v ＝－20，8，－1，1，16， 4，85，43，188，120，711， 569．x ，y 是方程t 2－2wt ＋v ＝0的整数解，故w 2－v 为完全平方数．其中只有w ＝5，v ＝16满足此要求． ∴ (x ，y)＝(2，8)，(8，2)．29、对任意的∑∞=+*+=∈01].22[,K k kn S N n 计算和 解：因]212[]22[11+=+++k k n n 对一切k =0,1,…成立，因此，].2[]22[]212[111+++-⋅=+k k k n n n 又因为n 为固定数，当k 适当大时,.)]2[]2([,0]2[,1201n n n S n n K k k k k ==-==<∑∞=+ 故从而 30、计算和式.]503305[5020的值∑==n nS解：显然有：若.,,1][][][,1}{}{R y x y x y x y x ∈++=+=+则503是一个质数，因此，对n=1,2,…,502, 503305n 都不会是整数，但503305n +,305503)503(305=-n 可见此式左端的两数的小数部分之和等于1，于是，[503305n ]+.304]503)503(305[=-n 故 ∑∑===⨯=-+==25115021.76304251304]),503)503(305[]503305([]503305[n n n n n S 31、设M 为一正整数，问方程222}{][x x x =-，在[1，M]中有多少个解？解：显然x =M 是一个解,下面考察在[1，M]中有少个解.设x 是方程的解.将222}{}{}{2][x x x x x +⋅+=代入原方程，化简得=}]{[2x x ,1}{0].}{}]{[2[2<≤+x x x x 由于所以上式成立的充要条件是2[x ]{x }为一个整数..1)1(],1[,.)1())1(21(2),1[,11.2)1,[),12,,1,0(2}{,][个解中有原方程在因此个解中方程有可知在又由于个解中方程有即在则必有设+--⋅=-+++-≤≤+-==∈=M M M M M M M M m m m m m k mk x N m x 32、求方程.051][4042的实数解=+-x x解：.0][,1][][不是解又因<+<≤x x x x⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≥>⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≥<⎩⎨⎧≤-->--⎪⎩⎪⎨⎧≤+->+-+∴.217][,23][,211][;217][,23][,25][.07][2)(3][2(.0)11][2)(5][2(.051][4][4,051][40)1]([422x x x x x x x x x x x x x x 或 经检验知，这四个值都是原方程的解. 33、.][3]3[2]2[1][][:,,n nx x x x nx N n R x ++++≥∈+∈* 证明 【证】.,2,1,][2]2[][ =+++=k kkx x x A k 令 由于.,1],[1命题成立时则==n x A .2269,02694;2229,02294;2189,01894;229,0294:,876][2][2222==-==-==-==-==x x x x x x x x x x 分别代入方程得或或或解得.,,,],[][][][][][][])[])1([(]))2[(]2([])1[(]([][]2[])2[(])1[(][])1[(]2[][][])1[(]2[][][])1[(]2[][)(:].[],2[22,],)1[()1()1(],[,][,][,].)1[(,],2[],[,1122112111221111121证毕均成立故原不等式对一切命题成立时即故相加得所以成立对一切即因为即有时命题成立设*---------∈=≤∴=+++≤++-++-++-+=+++-+-++-+++≤++++++-+++=+-+++=+++-==--=---=-=-=--≤≤≤-≤N n k n kx A kx k kx kx kx kx kx x x k x k x x k x x x x k x k kx x k x x A A A A kx x k x x kA kx x k x x A A A kA x A x A A x k A k A k kx kA kA k kx kA kA kkx A A x k A x A x A k n k k k k k k k k k k k k k k k34、对自然数n 及一切自然数x ，求证：].[]1[]2[]1[][nx n n x n x n x x =-+++++++ . 解：M ＝|f(x)|max ＝max{|f ⑴|，|f(－1)|，|f(－2a )|} ⑴若|－2a |≥1 (对称轴不在定义域内部) ，则M ＝max{|f ⑴|，|f(－1)|} 而f ⑴＝1＋a ＋b f(－1)＝1－a ＋b|f ⑴|＋|f(－1)|≥|f ⑴＋f(－1)|＝2|a|≥4则|f ⑴|和|f(－1)|中至少有一个不小于2，∴ M≥2＞21 ⑵|－2a |＜1 M ＝max{|f ⑴|，|f(－1)|，|f(－2a )|} ＝max{|1＋a ＋b|，|1－a ＋b|，|－4a 2＋b|} ＝max{|1＋a ＋b|，|1－a ＋b|，|－4a 2＋b|，|－4a 2＋b|} ≥41(|1＋a ＋b|＋|1－a ＋b|＋|－4a 2＋b|＋|－4a 2＋b|) ≥41[(1＋a ＋b)＋(1－a ＋b)－(－4a 2＋b)－(－4a 2＋b)] ＝)2a 2(412+ ≥21 综上所述，原命题正确.四、阶：对于(a ，n)=1的整数，满足a r ≡1 (mod n ) 的最小整数r,称为a 模n 的阶。