初等数论教案

【www.guakaob.com--教案】

初等数论教案(一)
初等数论教案

第一章 整除理论

整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。

第一节 数的整除性

定义1 设a，b是整数，b  0，如果存在整数c，使得

a = bc

成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号ba；如果不存在整数c使得a = bc成

|a。 立，则称a不被b整除，记为b

显然每个非零整数a都有约数 1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

被2整除的整数称为偶数，不被2整除的整数称为奇数。

定理1 下面的结论成立：

(ⅰ) ab  ab；

(ⅱ) ab，bc  ac；

(ⅲ) bai，i = 1, 2, , k  ba1x1  a2x2    akxk，此处xi（i = 1, 2, , k）是任意的整数；

(ⅳ) ba  bcac，此处c是任意的非零整数；

(ⅴ) ba，a  0  |b|  |a|；ba且|a| < |b|  a = 0。

定义2 若整数a  0，1，并且只有约数 1和 a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。

定理2 任何大于1的整数a都至少有一个素约数。

证明 若a是素数，则定理是显然的。

若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, , dk 。不妨设d1是其中最小的。若d1不是素数，

则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。

推论 任何大于1的合数a必有一个不超过a的素约数。

证明 使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12  a。证毕。

例1 设r是正奇数，证明：对任意的正整数n，有

n  2|1r  2 r    n r。

解 对于任意的正整数a，b以及正奇数k，有

ak  bk = (a  b)(ak  1  ak  2b  ak  3b2    bk  1) = (a  b)q，

其中q是整数。记s = 1r  2 r    n r，则

2s = 2  (2 r  n r)  (3 r  (n  1)r)    (n r  2 r) = 2  (n  2)Q，

其中Q是整数。若n  2s，由上式知n  22，因为n  2 > 2，这是不可能的，所以n  2|s。

例2 设A = { d1, d2, , dk }是n的所有约数的集合，则

B ={

也是n的所有约数的集合。

解 由以下三点理由可以证得结论：

(ⅰ) A和B的元素个数相同；

(ⅱ) 若diA，即din，则

(ⅲ) 若di  dj，则nnn,,, d1d2dkn|n，反之亦然； dinn。 didj

例3 以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2) = 2，d(3) = 2，d(4) = 3， 。问：

d(1)  d(2)    d(1997)

是否为偶数？

解 对于n的每个约数d，都有n = dnnn，因此，n的正约数d与是成对地出现的。只有当d =，即n = d2时，d和ddd

n才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。 d

因为442 < 1997 < 452，所以在d(1), d(2), , d(1997)中恰有44个奇数，故d(1)  d(2)    d(1997)是偶数。 例4 设凸2n边形M的顶点是A1, A2, , A2n，点O在M的内部，用1, 2, , 2n将M的2n条边分别编号，又将OA1, OA2, , OA2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2, OA2A3, , OA2nA1的周长都相等。

解 假设这些三角形的周长都相等，记为s。则

2ns = 3(1  2    2n) = 3n(2n  1)，

即

2s = 3(2n  1)，

因此23(2n  1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。

例5 设整数k  1，证明：

|a； (ⅰ) 若2k  n < 2k  1，1  a  n，a  2k，则2k

|2b  1。 (ⅱ) 若3k  2n  1 < 3k + 1，1  b  n，2b  1  3k，则3k

|a； 解 (ⅰ) 若2k|a，则存在整数q，使得a= q2k。显然q只可能是0或1。此时a= 0或2k ，这都是不可能的，所以2k

(ⅱ) 若 3k|2b-1，则存在整数q，使得2b-1= q3k，显然q只可能是0，1, 或2。此时2b-1= 0，3k，或23，这都是不可能的，所以3k|2b  1。

例6 写出不超过100的所有的素数。

解 将不超过100的正整数排列如下：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 k

71 73 79 83 89 97

按以下步骤进行：

(ⅰ) 删去1，剩下的后面的第一个数是2，2是素数；

(ⅱ) 删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；

(ⅲ) 再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；

(ⅳ) 再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数；

 

照以上步骤可以依次得到素数2, 3, 5, 7, 11, 。

由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。

在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。

例7 证明：存在无穷多个正整数a，使得

n4  a（n = 1, 2, 3, ）

都是合数。

解 取a = 4k4，对于任意的nN，有

n4  4k4 = (n2  2k2)2  4n2k2 = (n2  2k2  2nk)(n2  2k2  2nk)。

因为

n2  2k2  2nk = (n  k)2  k2  k2，

所以，对于任意的k = 2, 3,  以及任意的nN，n4  a是合数。

例8 设a1, a2, , an是整数，且

a1  a2    an = 0，a1a2an = n，

则4n。

|n，则n, a1, a2, , an都是奇数。于是a1  a2    an是奇数个奇数之和，不可能等于零，这与题设矛盾，解 如果2

|ai（2  i  n）所以2n，即在a1, a2, , an中至少有一个偶数。如果只有一个偶数，不妨设为a1，那么2。此时有等式

a2    an = a1，

在上式中，左端是(n  1)个奇数之和，右端是偶数，这是不可能的，因此，在a1, a2, , an中至少有两个偶数，即4n。

例9 若n是奇数，则8n2  1。

解 设n = 2k  1，则

n2  1= (2k  1)2  1 = 4k(k  1)。

在k和k  1中有一个是偶数，所以8n2  1。

例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，我们可以提出下面的问题： 问题 d(1)2  d(2)2    d(1997)2被4除的余数是多少？

例10 证明：方程

a12  a22  a32 = 1999 (1)

无整数解。

解 若a1，a2，a3都是奇数，则存在整数A1，A2，A3，使得

a12 = 8A1  1，a22 = 8A2  1，a32 = 8A3  1，

于是

a12  a22  a32 = 8(A1  A2  A3)  3。

由于1999被8除的余数是7，所以a1，a2，a3不可能都是奇数。

由式(1)，a1，a2，a3中只能有一个奇数，设a1为奇数，a2，a3为偶数，则存在整数A1，A2，A3，使得

a12 = 8A1  1，a22 = 8A2  r，a32 = 8A3  s，

于是

a12  a22  a32 = 8(A1  A2  A3)  1  r  s，

其中r和s是整数，而且只能取值0或4。这样a12  a22  a32被8除的余数只可能是1或5，但1999被8除的余数是7，所以这样的a1，a2，a3也不能使式(2)成立。

综上证得所需要的结论。

习 题 一

1. 证明：若m  pmn  pq，则m  pmq  np。

初等数论教案(二)
初等数论教案

厦门大学教案

院（系） 任课教师 祝辉林 课程名称

授课章节：第4.3节 一次同余方程组和孙子定理 授课教材：《初等数论》，北京大学出版社 授课对象：数学类专业一年级本科生 【教学要求】

1. 了解孙子定理的历史背景和起源出处，理解用孙子定理求解一次同余方程组的思想方法和公式，掌握求解一次同余方程组的计算步骤；

2. 掌握一次同余方程组的模两两不互素时，应当如何转化成模两两互素时的等价一次同余方程组，再用孙子定理求解；

3. 理解一次同余方程组的意义，并能用孙子定理的方法解决一些实际应用问题。 【教学重点】

1. 孙子定理的思想方法和计算步骤； 2. 如何应用孙子定理解决实际应用问题。 【教学难点】

理解孙子定理的思想方法。 【教学内容】

第三节 一次同余方程组和孙子定理

本节主要讨论一次同余方程组的解法。为了解决这类同余方程组，我们需要弄清楚剩余系的结构。孙子定理(又称中国剩余定理)就是解决这类实际问题的有力工具。

一、 “物不知其数”问题及其解法

1.1问题的提出

例1：（“物不知其数”问题）

大约在公元四世纪，我国南北朝时期有一部著名的算术著作《孙子算经》，其中就有一个“物不知其数”问题：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三”。

1.2 问题的解法及理由

明朝程大位编著的《算法统宗》里记载了此题的解法，他是用一首歌谣叙述出来的：

三人同行七十稀，五树梅花廿一枝。七子团圆正月半，除百零五便得知。

这首诗翻译成数学算式就是：702213152233，233105223。

解题步骤及理由如下：

（1）先在5和7的公倍数中找除以3余1的数，进而找到除3余2的数。

因为[5,7]35，35311(余2)，(352)323(余1)，而(702)346(余2)，所以140符合条件。

（2）在3和7的公倍数中找除以5余1的数，进而找到除5余3的数。 因为[3,7]21，2154(余1)，(213)512(余3)，

所以63就是符合条件的数。

（3）在3和5的公倍数中找除以7余1的数，进而找到除7余2的数。

因为[3,5]15，1572(余1)，(152)74(余2)，所以30就是符合条件的数。

（4）将上面得到的分别符合上面三个条件的三个数相加：702213152233。 因为70(或140)是5和7的倍数，而3除余1(或余2)的数。21(或63)是3和7的倍数，而5除余1(或余3)的数。15(或30)是3和5的倍数，而7除余1(或余2)的数。 所以233是除以3余2、除以5余3和除以7余2的数。

又因为[3，5，7]105，233210523也是它的解，而且23105，

所以23是最小解，其所有解为x105k23(k0,1,2,)。

1.3 注释

“物不知其数”问题及其解答，是我国古代研究一次同余方程组并取得辉煌成果的经典例证。上面的解法中，总是先求出余1的数，再求出余几的数，这种解法逐渐被总结成简洁实用的“求一术”。“物不知其数”又名“鬼谷算”，“秦王暗点兵”，“剪管术”，“隔墙算”，“神奇妙算”，“大衍求一术”等等。方法总结如下：

m25，m37均为定母，m13，M135，M221，M315m105为衍母，例1中，

为衍数，乘率M1

1

12，M211，M311分别满足“求一术”中的M1M11(mod3)，

M2M211(mod5)，M3M311(mod7)，用数分别为 M1M1170，M2M2121，

M3M3115，剩数为a12，a23，a32，各总分别为M1M11a1140，M2M21a2

63，M3M31a330，所求率为M1M11a1M2M21a2M3M31a3233，所以

xM1M11a1M2M21a2M3M31a370221315223(mod105)。

二、一次同余方程组和孙子定理 2.1 一次同余方程组

xa1(modm1)xa(modm)22

我们本节要讨论的是形如 (1)

xak(modmk)

的一次同余方程组的解法。前面的“物不知其数问题”，其实就是一次同余方程组

x2(mod3)



x3(mod5)。 (2) x2(mod7)

它的解为x23(mod105)。

2.2 孙子定理

定理1：设m1,m2,,mk是两两互素的正整数，那么对于任意整数a1,a2,,ak，一次同余

xa1(modm1)xa(modm)22

方程组  必定有解，其解为

xak(modmk)

xM1M11a1M2M21a2MkMk1ak(modm)。这里mm1m2mkmjMj，

MjMj11(modmj)，1jk。

证明：由于m1,m2,,mk两两互素，所以m[m1,m2,,mk]m1m2mk。若一次同余方程组有解c1,c2，则c1c2(modm)。因为m1,m2,,mk两两互素，c1c2(modmj)，

1jk，这就证明了同余方程若有解，则其解数为1。下面证明

xM1M11a1M2M21a2MkMk1ak(modm)确实是同余方程的解。显然

(mj,Mj)1，根据扩展的欧几里德算法，满足MjMj11(modmj)的Mj1必存在。由

MjMj11(modmj)及mj|Mi(ji)就推出cMjMj1ajaj(modmj)，即c是解。

1

注释：(1)从孙子定理的算法思想来看，整个计算的难点集中在求Mj上， 需要扩展的欧几里德算法来实现，当然在实际解题中我们通常采用拼凑法。

(2)孙子定理要求一次同余方程组的模m1,m2,,mk两两互素，如果出现了某两个模不互素的情形，则应该将其转化为模互素的情形下的等价的一次同余方程组。

x7(mod9)

例如：一次同余方程组就是模9和15不互素的一次同余方程组。我们将9

x1(mod15)x7(mod9)

2

和15完全素因子分解为93，1535，则原方程组等价于x1(mod3)，显然

x1(mod5)

x7(mod9)是x1(mod3)的特殊情形，不是矛盾方程(否则无解)，故原方程组等价于x7(mod9)

，再应用孙子定理求解。 

x1(mod5)

三、孙子定理的应用

孙子定理是数论中最重要的基本定理之一，它实质上刻画了剩余系的结构。它的应用是非常广泛的，在数学计算、保密通讯、测距和日常生活中都通常会用到。

2

2

2

2

例2. 求相邻的四个整数，它们依次可被2，3，5及7整除。【初等数论教案】

x1(mod22)2x0(mod3)

解：设这四个相邻整数是x1，x，x1，x2，按要求应满足 。

2

x1(mod5)x2(mod72)

所以，这是一个解同余方程组问题，m12，m23，m35，m47两两互素，满

2

2

2

2

初等数论教案(三)
初等数论教案

初等数论教案

一、数论发展史

数论是研究整数性质的一门很古老的数学分支， 其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布 以及数论函数等内容，统称初等数论（Elementary Number Theory）。

初等数论的大部分内容早在古希腊欧几里德的《 几何原本》中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法， 即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代《孙子算经》中的下卷第26题，我国称之为“孙子定理”。

近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，高斯的《算术探究》是数论的划时代杰作。

“数学是科学之王，数论是数学之王”。 -----高斯

由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等 新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了 广泛的应用，无疑同时间促进着数论的发展。

二 几个著名数论难题

初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。

其中，非常著名的问题有：哥德巴赫猜想 ；费尔马大定理 ；孪生素数问题 ；完全数问题等。

1、哥德巴赫猜想：

1742年,由德国中学教师哥德巴赫在教学中首先发现的。1742年6月7日，哥德巴赫写信给当时的大数学家欧拉,正式提出了以下的猜想：

一个大于6的偶数可以表示为不同的两个质数之和。

陈景润在1966年证明了“哥德巴赫猜想”的“一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”〔所谓的1+2〕，是筛法的光辉顶点，至今仍是“哥德巴赫猜想”的最好结果。

2、费尔马大定理：

费马是十七世纪最卓越的数学家之一，他在数学许多领域中都有极大的贡献，因为他的本行是专业的律师，世人冠以“业余王子”之美称。在三百七十多年前的某一天，费马正在阅读一本古希腊数学家戴奥芬多斯的数学书时，突然心血来潮在书页的空白处，写下一个看起来很简单的定理。

nnn

经过8年的努力，英国数学家 安德鲁·怀尔斯 终于在1995年完成了该定理的证明。

3、孪生素数问题

存在无穷多个素数 p, 使得 p+2 也是素数。

究竟谁最早明确提出这一猜想已无法考证，但是1849年法国数学 Alphonse de Polignac 提出猜想：对于任何偶数 2k, 存在无穷多组以2k为间隔的素数。对于 k=1，这就是孪生素数猜想，因此人们有时把 Alphonse de Polignac 作为孪生素数猜想的提出者。不同的 k 对应的素数对的命名也很有趣，k=1 我们已经知道叫做孪生素数； k=2 (即间隔为4) 的素数对被称为 cousin prime ；而 k=3 (即间隔为 6) 的素数对竟然被称为 sexy prime (不过别想方程xyz(n3)无非0整数解

歪了，之所以称为 sexy prime 其实是因为 sex 正好是拉丁文中的 6。)

4、最完美的数——完全数问题

完美数又称为完全数,最初是由毕达哥拉斯的信徒发现的,他们注意到,数6有一个特性,它等于它自己的因子(不包括它自身)的和， 如：6=1+2+3.下一个具有同样性质的数是28, 28=1+2+4+7+14.接着是496和8128.他们称这类数为完美数.

欧几里德在大约公元前350-300年间证明了:

若2n1是素数，则2n1(2n1)是完全数

注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数。

三、我国古代数学的伟大成就

1、周髀算经

公元前100多年，汉朝人撰，是一部既谈天体又谈数学的天文历算著作，主要讨论盖天说，提出了著名的“勾三股四弦五”这个勾股定理的一个特例。

2、孙子算经

约成书于四、五世纪，作者生平和编写年代都不清楚。现在传本的《孙子算经》共三卷。卷上叙述算筹记数的纵横相间制度和筹算乘除法则，卷中举例说明筹算分数算法和筹算开平方法。卷下第31题，可谓是后世“鸡兔同笼”题的始祖，后来传到日本，变成“鹤龟算”。

具有重大意义的是卷下第26题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？《孙子算经》不但提供了答案，而且还给出了解法。南宋大数学家秦九韶则进一步开创了对一次同余式理论的研究工作，推广“物不知数”的问题。德国数学家高斯﹝1777-1855﹞于1801年出版的《算术探究》中明确地写出了上述定理。1852年，英国基督教士伟烈亚士将《孙子算经》中物不知数问题的解法传到欧洲，1874年马蒂生指出孙子的解法符合高斯的定理，从而在西方的数学史里将这一个定理称为“中国剩余定理” 。

3、算数书

1983年在湖北省江陵县张家山，出土了一批西汉初年，即吕后至文帝初年的竹简，共千余支。经初步整理，其中有律令、《脉书》、《引书》、历谱、日书等多种古代珍贵的文献，还有一部数学著作，据写在一支竹简背面的字迹辨认，这部竹简算书的书名叫《算数书》。 《算数书》是中国现已发现的最古的一部算书，大约比现有传本的《九章算术》还要早近二百年，而且《九章算术》是传世抄本或刊书，《算数书》则是出土的竹筒算书，属于更可珍贵的第一手资料，所以《算数书》引起了国内外学者的广泛关注，目前正在被深入研究之中。

4、数术记遗【初等数论教案】

《数术记遗》相传是汉末徐岳所作，亦有数学史家认为本书是北周甄鸾自著。

《数术记遗》把大数的名称按不同的涵义排列三个不同的数列，另一部份是关于一个幻方的清楚的说明，它成为数论中这一发现的最古的文字记载之一，书中至少提到了四种算盘，因此它是谈到算盘的最古老的书籍。

5、九章算术

根据研究，西汉的张苍 、耿寿昌曾经做过增补和整理，其时大体已成定本。最后成书最迟在东汉前期。九章算术将书中的所有数学问题分为九大类，就是“九章”。

三国时期的刘徽为《九章》作注，加上自己心得体会，使其便于了解，可以流传下来。 唐代的李淳风又重新做注(656年)，作为《算数十经》之一，版刻印刷，作为通用教材。 《九章算术》的出现，标志着我国古代数学体系的正式确立，当中有以下的一些特点：

1.是一个应用数学体系，全书表述为应用问题集的形式；

2.以算法为主要内容，全书以问、答、术构成，“术”是主要需阐述的内容；

3.以算筹为工具。

《九章算术》取得了多方面的数学成就，包括：分数运算、比例问题、双设法、一些面积、体积计算、一次方程组解法、负数概念的引入及负数加减法则、开平方、开立方、一般二次方程解法等。《九章算术》的思想方法对我国古代数学产生了巨大的影响。自隋唐之际，《九章算术》已传入朝鲜、日本，现在更被译成多种文字。

6、海岛算经

《海岛算经》由三国刘徽所着，最初是附于他所注的《九章算术》（263）之后，唐初开始单行，体例亦是以应用问题集的形式。

全书共9题，全是利用测量来计算高深广远的问题，首题测算海岛的高、远，故得名。《海岛算经》是中国最早的一部测量数学事着，亦为地图学提供了数学基础。

7、算经十书

唐代国子监内设立算学馆，置博士、助教指导学生学习数学，规定《周髀算经》、《九章算术》、《孙子算经》、《五曹算经》、《夏侯阳算经》、《张丘建算经》、《海岛算经》、《五经算术》、《缀术》、《缉古算经》十部算经为课本，用以进行数学教育和考试，后世通称为算经十书．算经十书是中国汉唐千余年间陆续出现的十部数学著作．北宋时期（1084年），曾将一部算经刊刻发行，这是世界上最早的印刷本数学书．（此时《缀术》已经失传，实际刊刻的只有九种）。

8、测圆海镜

《测圆海镜》由中国金、元时期数学家 李冶所著，成书于1248年。全书共有12卷，170问。这是中国古代论述容圆的一部专箸，也是天元术的代表作。《测圆海镜》所讨论的问题大都是已知 勾股形而求其内切圆、旁切圆等的直径一类的问题。在《测圆海镜》问世之前，我国虽有文字代表未知数用以列方程和多项式的工作，但是没有留下很有系统的记载。

李冶在《测圆海镜》中系统而概栝地总结了天元术，使文词代数开始演变成符号代数。 所谓天元术，就是设“天元一”为未知数，根据问题的已知条件，列出两个相等的多项式，经相减后得出一个高次方式程，称为天元开方式，这与现代设x为未知数列方程一样。欧洲的数学家，到了16世纪以后才完全作到这一点。

数论是以严格和简洁著称，内容既丰富又深刻。我将会介绍数论中最基本的概念和理论，希望大家能对这门学问产生兴趣，并且对中小学时代学习过的一些基本概念，例如整除性、最大公因子、最小公倍数、辗转相除法等，有较深入的了解。

第一章 整数的整除性

第一节 整除的概念

• 一、基本概念

1、自然数、整数

2、正整数、负整数

3、奇数、偶数

关于奇数和偶数性质：

1.奇数+奇数=偶数；

奇数+偶数=奇数；

偶数+偶数=偶数；

2.两个数之和是奇（偶）数，则这两个数的奇偶性相反（同）。【初等数论教案】

3.若干个整数之和为奇数，则这些数中必有奇数，且奇数的个数为奇数个；若干个整数之和为偶数，则这些数中若有奇数，奇数的个数必为偶数个。

关于奇数和偶数性质：

4.奇数×奇数=奇数；

奇数×偶数=偶数；

偶数×偶数=偶数；

5.若干个整数之积为奇数，则这些数必为奇数；若干个整数之积为偶数，则这些数中至少有一个是偶数。

6.若a是整数，则|a| 与a 有相同的奇偶性。

7.若a ，b 是整数，则a +b 与a -b 奇偶性相同。

例1 在1,2,3， ，1998,1999这1999个数的前面任意添加一个正号或负号，问它们的代数和是奇数还是偶数？

例2 设n 为奇数， 1 2 n 是1,2，  ，n 的任意一个排列， 证明 (a 1  1)( ( a n  n ) 必是偶数。 a 2 2)

例3 将正方形ABCD分割成 n 2 个相等的小方格（n 是正整数），把相对的顶点A,C染成红色，B,D染成蓝色，其他交点任意染成红蓝两色中的一种颜色，证明：恰有三个顶点同颜色的小方格的数目必是偶数。

例4 设正整数d 不等于2,5,13，证明集合 d  中可以找到两个数a ，b ，使得 2,5,13.

a b-1 不是完全平方数。

a,a,,a

• 一个性质：

整数+整数=整数

整数-整数=整数

整数*整数=整数

二、整除

• 1、定义：设a，b是整数，b≠0。如果存在一个整数q使得等式：

a=bq

成立，则称b能整除a或a能被b整除，记b∣a；

如果这样的q不存在，则称b不能整除a，记为b a。

注：显然每个非零整数a都有约数 1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

素数：

定义 设整数n≠0，±1.如果除了显然因数±1，±n以外，n没有其他因数，那么，n叫做素数（或质数或不可约数），否则，n叫做合数.

规定：若没有特殊说明，素数总是指正整数，通常写成p或 p1， p2，„， pn. 例 整数2，3，5，7都是素数，而整数4，6，8，10，21都是合数.

2、整除的性质

设a，b，c是整数

（1）a ∣ a

（2）如果 a ∣ b ， b ∣ c ，则a ∣ c

（3）如果 a ∣b ， a ∣c ,则对任意整数m，n 有a ∣mb+cn.

（4）如果a ∣ c ，则对任何整数b ， a ∣ b c.

（5）若（ a，b ）=1，且a ∣ b c，则a ∣ c

（6）若（ a，b ）=1，且a ∣c， b ∣ c则a b ∣ c

（7）若（ a，b ）=1，且a b ∣c，则a ∣c， b ∣ c

mn aibj（8）若在等式 i j 1 中，除某一项外，其余各项都能被c整除，则这1

一项也能被c整除。

常用结论：

（1）设p为素数 ，若p ∣ b a ，则p ∣a 或 p ∣b .

（2） p|a 或 (p，a)=1 . 

p  a 2  pa

例6 证明：121 n 2   12 ，nZ。 2 n

初等数论教案(四)
初等数论教案4

第八节 一次不定方程

教学目的：1、掌握一次不定方程的一些简单性质；

2、掌握一次不定方程有解的判别条件；

3、会解二元、三元一次不定方程.

教学重点：有解的判别条件、求解二元、三元一次不定方程. 教学过程

设a1, a2, , an是非零整数，b是整数，称关于未知数x1, x2, , xn的方程(n2)

a1x1  a2x2    anxn = b (1)

是n元一次不定方程.

若存在整数x10, x20, , xn0满足方程(1)，则称(x10, x20, , xn0)是方程(1)的解，或说x1 = x10，x2 = x20，，xn = xn0是方程(1)的解.

1、定理1 方程(1)有解的充要条件是(a1, a2, , an)b. (2) 证明：记d = (a1, a2, , an).若方程(1)有解，设为(x1, x2, , xn).则由dai（1  i  n）及整除的性质容易知道式(2)成立. 必要性得证.

另一方面，存在整数y1, y2, , yn使得

a1y1  a2y2    anyn = (a1, a2, , an) = d.

因此，若式(2)成立，则(by1,by2,,byn)就是方程(1)的解，充分性得ddd

证. 证毕

2、定理2 设a，b，c是整数，方程ax  by = c (3) 若有解(x0, y0)，则它的一切解具有

xx0b1t， yyat01

tZ (4)

的形式，其中a1ab，b1. (a,b)(a,b)

证明：容易验证，由式(4)确定的x与y满足方程(3). 下面证明，方程(3)的解都可写成式(4)中的形式.

设(x, y)是方程(3)的解，则由

ax0  by0 = ax  by = c

得到 a(x  x0) = b(y  y0)，

ab(xx0)(yy0). (a,b)(a,b)

由此，以及 (

得到ab,)1 (a,b)(a,b)b|x  x0，因此存在整数(a,b)

xx0t，使得 证毕 bat，yy0t. (a,b)(a,b)

定理1和定理2说明了解方程(3)的步骤：

(ⅰ) 判断方程是否有解，即(a, b)c是否成立；

(ⅱ) 利用辗转相除法求出x0，y0，使得ax0  by0 = (a, b)； (ⅲ) 写出方程(3)的解

xx0c1b1t，tZ，yy0c1a1t ab其中(a,b)c1c，a1，b1.(a,b)(a,b)

3、定理3 设a1, a2, , an, b是整数，再设 (a1, a2, , an  1) = dn  1，(a1, a2, , an) = dn，则(x1, x2, , xn)是方程(1)的解的充分必要条件是存在整数t，使得(x1, x2, , xn, t)是方程组

 a1x1a2x2an1xn1dn1t (5) dtaxbnnn1

的解.

证明：若有整数t，使得(x1, x2, , xn, t)是方程组(5)的解，则显然(x1, x2, , xn)满足方程(1).

设(x1, x2, , xn)是方程(1)的解，则

a1x1  a2x2    an  1xn  1  anxn = b. (6)

令 a1x1  a2x2    an  1xn  1 = b，

则 dn  1 = (a1, a2, , an  1)b.

因此，存在tZ，使得 a1x1  a2x2    an  1xn  1 = dn  1t， (7) 再由式(6)，得到 dn  1t  anxn = b，

即(x1, x2, , xn, t)满足方程组(5). 证毕

定理3说明了求解n元一次不定方程的方法：先解方程组(5)中的第二个方程，再解方程组(5)中的第一个方程，于是，解n元一次不定方程就化为解n  1元一次不定方程.重复这个过程，最终归结为求解二元一次不定方程. 记

(a1, a2) = d2，(d2, a3) = d3，，(dn  2, an  1) = dn  1，(dn  1，an) = dn， 逐个地解方程 dn  1tn  1  anxn = b，

dn  2tn  2  an  1xn  1 = dn  1tn  1，

 

d2t2  a3x3 = d3t3，

a1x1  a2x2 = d2t2，

并且消去中间变量t2, t3, , tn  1，就可以得到方程(1)的解.

例1 求不定方程3x  6y = 15的解.

解 (3, 6) = 315，所以方程有解.

由辗转相除法（或直接观察），可知x = 1，y = 1是

3x  6y = 3

的解，所以x0 = 5，y0 = 5是原方程的一个解.由定理2，所求方程的

x52t解是 y5t， tZ. 

例2 求不定方程3x  6y  12z = 15的解.

解 原方程等价于 x  2y  4z = 5. (8) 由定理3，依次解方程 t  4z = 5， x  2y = t，

t14u分别得到 z1u， uZ， (9) 

xt2v， vZ. (10) ytv

将式(9)与式(10)中的t消去，得到

x14u2vy14uv， u, vZ. z1u

注：本例在解方程时，首先将原方程化为等价方程(8)，这使问题简化. 例1也可以如此处理.

例3 设a与b是正整数，(a, b) = 1，则任何大于ab  a  b的整数n都可以表示成n = ax  by的形式，其中x与y是非负整数，但是n = ab  a  b不能表示成这种形式.

解 (ⅰ) 由定理2，方程 ax  by = n (11)

xx0bt

的解具有 yyat， tZ (12) 0

的形式，其中x0与y0满足方程(11).

由假设条件n > ab  a  b及式(11)与式(12)，有

ax = n  by = n  b(y0  at) > ab  a  b  b(y0  at). (13) 取整数t，使得 0  y = y0  at  a  1，

则由式(13)得到 ax > ab  a  b  b(a  1) = a，

x > 1，x  0，

即n = ax  by，x  0，y  0.

(ⅱ) 设有x  0，y  0，使得 ax  by = ab  a  b， (14) 则 a(x  1)  b(y  1) = ab. (15) 所以ab(y  1).但是(a, b) = 1，于是必有

ay  1，y  1  a.

同理可以证明x  1  b，从而 a(x  1)  b(y  1)  2ab， 这与式(15)矛盾，所以 (14) 式是不可能的.

例4 设a，b，c是整数，(a, b) = 1，则在直线ax  by = c上，任何一个长度大于a2b2的线段上至少有一个点的坐标都是整数.

解 由定理2，直线ax  by = c上的坐标都是整数的点(xt, yt)的坐

xtx0bt标是 yyat， tZ，

0t

其中(x0, y0)是直线ax  by = c上的坐标都是整数的点，由定理1，这样的点是存在的.

对于任意的tZ，记Pt是以(xt, yt)为坐标的点，则Pt  1与Pt 之间

22的距离 Pt1Ptxt1xtyt1yta2b2.

这说明，两个“相邻的”坐标是整数的点的距离是

出所求之结论.

a2b2，从而得

初等数论教案(五)
初等数论教案

第一章 整除理论

整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。

第一节 数的整除性

定义1 设a，b是整数，b  0，如果存在整数c，使得

a = bc

成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号ba；如果不存在整数c使得a = bc成立，则称a不被b整除，记为b|a。

显然每个非零整数a都有约数 1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

被2整除的整数称为偶数，不被2整除的整数称为奇数。 定理1 下面的结论成立： (ⅰ) ab  ab； (ⅱ) ab，bc  ac； (ⅲ) bai，i = 1, 2, , k  ba1x1  a2x2    akxk，此处xi（i = 1, 2, , k）是任意的整数；

(ⅳ) ba  bcac，此处c是任意的非零整数；

(ⅴ) ba，a  0  |b|  |a|；ba且|a| < |b|  a = 0。 证明 留作习题。

定义2 若整数a  0，1，并且只有约数 1和 a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。 定理2 任何大于1的整数a都至少有一个素约数。 证明 若a是素数，则定理是显然的。

若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, , dk 。不妨设d1是其中最小的。若d1不是素数，则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。 推论 任何大于1的合数a必有一个不超过a的素约数。证明 使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12  a。证毕。

例1 设r是正奇数，证明：对任意的正整数n，有

n  2|1r  2 r    n r。

解 对于任意的正整数a，b以及正奇数k，有

ak  bk = (a  b)(ak  1  ak  2b  ak  3b2    bk  1) = (a  b)q， 其中q是整数。记s = 1r  2 r    n r，则

2s = 2  (2 r  n r)  (3 r  (n  1)r)    (n r  2 r) = 2  (n  2)Q， 其中Q是整数。若n  2s，由上式知n  22，因为n  2 > 2，这是不可能的，所以n  2|s。

例2 设A = { d1, d2, , dk }是n的所有约数的集合，则

B ={

nnd,,

n1

d,2

d

k

也是n的所有约数的集合。

解 由以下三点理由可以证得结论： (ⅰ) A和B的元素个数相同；

1

(ⅱ) 若dniA，即din，则d|n，反之亦然；

i

(ⅲ) 若di  dj，则

ndn。

i

d

j

例3 以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2)

= 2，d(3) = 2，d(4) = 3， 。问：

d(1)  d(2)    d(1997)

是否为偶数？

解 对于n的每个约数d，都有n = dn，因此，n的正约

d

数d与

n

是成对地出现的。只有当d =

n

，即n = d2时，d和

n

ddd

才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。

因为442 < 1997 < 452，所以在d(1), d(2), , d(1997)中恰有44个奇数，故d(1)  d(2)    d(1997)是偶数。

例4 设凸2n边形M的顶点是A1, A2, , A2n，点O在M的内部，用1, 2, , 2n将M的2n条边分别编号，又将OA1, OA2, , OA2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2, OA2A3, , OA2nA1的周长都相等。

解 假设这些三角形的周长都相等，记为s。则

2ns = 3(1  2    2n) = 3n(2n  1)，

即

2s = 3(2n  1)，

因此23(2n  1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。

2

例5 设整数k  1，证明：

(ⅰ) 若2k  n < 2k  1，1  a  n，a  2k，则2k|a； (ⅱ) 若3k  2n  1 < 3k + 1，1  b  n，2b  1  3k，则3k|2b  1。

解 (ⅰ) 若2k|a，则存在整数q，使得a= q2k。显然q只可能是0或1。此时a= 0或2k ，这都是不可能的，所以2k|a；

(ⅱ) 若 3k|2b-1，则存在整数q，使得2b-1= q3k，显然q只可能是0，1, 或2。此时2b-1= 0，3k，或23k

，这都是不可能的，所以3k|2b  1。

例6 写出不超过100的所有的素数。 解 将不超过100的正整数排列如下：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

按以下步骤进行：

(ⅰ) 删去1，剩下的后面的第一个数是2，2是素数； (ⅱ) 删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；

(ⅲ) 再删去3后面的被3整除的数，剩下的3后面的第一

个数是5，5是素数；

(ⅳ) 再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数；

 

照以上步骤可以依次得到素数2, 3, 5, 7, 11, 。

由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。

在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。

例7 证明：存在无穷多个正整数a，使得

n4  a（n = 1, 2, 3, ）

都是合数。

解 取a = 4k4，对于任意的nN，有

n4  4k4 = (n2  2k2)2  4n2k2 = (n2  2k2  2nk)(n2  2k2 

2nk)。

因为

n2  2k2  2nk = (n  k)2  k2  k2，

所以，对于任意的k = 2, 3,  以及任意的nN，n4  a是合数。

例8 设a1, a2, , an是整数，且

a1  a2    an = 0，a1a2an = n，

则4n。

解 如果2|n，则n, a1, a2, , an都是奇数。于是a1  a2    an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2n，即在a1, a2, , an中至少有一个偶数。如果只有一个偶数，不妨设为a1，那么2|ai（2  i  n）

。此时有等式 a2    an = a1，

在上式中，左端是(n  1)个奇数之和，右端是偶数，这是不可能的，因此，在a1, a2, , an中至少有两个偶数，即4n。

例9 若n是奇数，则8n2  1。 解 设n = 2k  1，则

n2  1= (2k  1)2  1 = 4k(k  1)。

在k和k  1中有一个是偶数，所以8n2  1。

例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，我们可以提出下面的问题：

问题 d(1)2  d(2)2    d(1997)2被4除的余数是多少？ 例10 证明：方程

a12  a22  a32 = 1999 (1)

无整数解。

解 若a1，a2，a3都是奇数，则存在整数A1，A2，A3，使得

a12 = 8A1  1，a22 = 8A2  1，a32 = 8A3  1，

于是

a12  a22  a32 = 8(A1  A2  A3)  3。

由于1999被8除的余数是7，所以a1，a2，a3不可能都是奇数。

由式(1)，a1，a2，a3中只能有一个奇数，设a1为奇数，a2，a3为偶数，则存在整数A1，A2，A3，使得

a12 = 8A1  1，a22 = 8A2  r，a32 = 8A3  s，

于是

a12  a22  a32 = 8(A1  A2  A3)  1  r  s，

其中r和s是整数，而且只能取值0或4。这样a12  a22  a32被8除的余数只可能是1或5，但1999被8除的余数是7，所以这样的a1，a2，a3也不能使式(2)成立。

综上证得所需要的结论。

3

习 题 一

1. 证明定理1。

2. 证明：若m  pmn  pq，则m  pmq  np。

3. 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。

4. 设p是n的最小素约数，n = pn1，n1 > 1，证明：若p >n，则n1是素数。

5. 证明：存在无穷多个自然数n，使得n不能表示为

a2  p（a > 0是整数，p为素数）

的形式。

第二节 带余数除法

在本节中，我们要介绍带余数除法及其简单应用。

定理1(带余数除法) 设a与b是两个整数，b  0，则存在唯一的两个整数q和r，使得

a = bq  r，0  r < |b|。 (1)

证明 存在性 若ba，a = bq，qZ，可取r = 0。若b|a，考虑集合

A = { a  kb；kZ },

其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的集合。

在集合A中有无限多个正整数，设最小的正整数是r = a  k0b，则必有

0 < r < |b|， (2)

4

否则就有r  |b|。因为b|a，

所以r  |b|。于是r > |b|，即a  k0b > |b|，a  k0b  |b| > 0，这样，在集合A中，又有正整数a  k0b  |b| < r，这与r的最小性矛盾。所以式(2)必定成立。取q =  k0知式(1)成立。存在性得证。

唯一性 假设有两对整数q ，r 与q ，r 都使得式(1)成立，即

a = q b  r  = q b  r ，0  r , r  < |b|，

则

(q  q )b = r   r ，|r   r | < |b|， (3)

因此r   r  = 0，r  = r ，再由式(3)得出q  = q ，唯一性得证。证毕。

定义1 称式(1)中的q是a被b除的商，r是a被b除的余数。

由定理1可知，对于给定的整数b，可以按照被b除的余数将所有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。

以后在本书中，除特别声明外，在谈到带余数除法时总是假定b是正整数。

例1 设a，b，x，y是整数，k和m是正整数，并且

a = a1m  r1，0  r1 < m， b = b1m  r2，0  r2 < m，

则ax  by和ab被m除的余数分别与r1x  r2y和r1r2被m除的余数相同。特别地，ak与r1k被m除的余数相同。

解 由

ax  by = (a1m  r1)x  (b1m  r2)y = (a1x  b1y)m  r1x  r2y 可知，若r1x  r2y被m除的余数是r，即

r1x  r2y = qm  r，0  r < m，

则

ax  by = (a1x  b1y  q)m  r，0  r < m，

即ax  by被m除的余数也是r。

同样方法可以证明其余结论。

例2 设a1, a2, , an为不全为零的整数，以y0表示集合

A = { y；y = a1x1    anxn，xiZ，1  i  n }

中的最小正数，则对于任何yA，y0y；特别地，y0ai，1  i  n。

解 设y0 = a1x1    anxn，对任意的y = a1x1    anxnA，由定理1，存在q, r0Z，使得

y = qy0  r0，0  r0 < y0 。

因此

r0 = y  qy0 = a1(x1  qx1)    an(xn  qxn)A。

如果r0  0，那么，因为0 < r0 < y0，所以r0是A中比y0还小的正数，这与y0的定义矛盾。所以r0 = 0，即y0y。

显然aiA（1  i  n），所以y0整除每个ai（1  i  n）。 例3 任意给出的五个整数中，必有三个数之和被3整除。 解 设这五个数是ai，i = 1, 2, 3, 4, 5，记

ai = 3qi  ri，0  ri < 3，i = 1, 2, 3, 4, 5。 分别考虑以下两种情形：

(ⅰ) 若在r1, r2, , r5中数0，1，2都出现，不妨设r1 = 0，r2 = 1，r3 = 2，此时

a1  a2  a3 = 3(q1  q2  q3)  3

可以被3整除；

(ⅱ) 若在r1, r2, , r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1 = r2 = r3 = r（r = 0，1或2），此时

a1  a2  a3 = 3(q1  q2  q3)  3r

可以被3整除。

例4 设a0, a1, , anZ，f(x) = anxn    a1x  a0 ，已知f(0)与f(1)都不是3的倍数，证明：若方程f(x) = 0有整数解，则

3f(1) = a0  a1  a2    (1)nan 。

解 对任何整数x，都有

x = 3q  r，r = 0，1或2，qZ。

(ⅰ) 若r = 0，即x = 3q，qZ，则

f(x) = f(3q) = an(3q)n    a1(3q)  a0 = 3Q1  a0 = 3Q1  f(0)， 其中Q1Z，由于f(0)不是3的倍数，所以f(x)  0；

(ⅱ) 若r = 1，即x = 3q  1，qZ，则

f(x) = f(3q  1) = an(3q  1)n    a1(3q  1)  a0

= 3Q2  an    a1  a0 = 3Q2  f(1)，

其中Q2Z。由于f(1)不是3的倍数，所以f(x)  0。

因此若f(x) = 0有整数解x，则必是x = 3q  2 = 3q  1，q

Z，于是

0 = f(x) = f(3q   1) = an(3q   1)n    a1(3q   1)  a0 = 3Q3  a0  a1  a2    ( 1)nan = 3Q3  f(1)，

其中Q3Z。所以3f(1) = a0  a1  a2    (1)nan 。

例5 证明：对于任意的整数n，f(n) = 3n5  5n3  7n被15整除。

解 对于任意的正整数n，记

n = 15q  r，0  r < 15。

由例1，

n2 = 15Q1  r1，n4 = 15Q2  r2，

其中r1与r2分别是r2与r4被15除的余数。

以R表示3n4  5n2  7被15除的余数，则R就是3r2  5r1  7被15除的余数，而且f(n)被15除的余数就是rR被15除的余数，记为R 。

当r = 0时，显然R  = 0，即153n5  5n3  7n。

5

本文来源：http://www.guakaob.com/shiyongwendang/655722.html