初等数论一演示文稿课件

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

设a，b是整数，b

0，如果存在整数c，使得

a=bc成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号ba；如果不存在整数c使得a=bc成立，则称a不被b整除，记为ba。第一节数的整除性定义1设a，b是整数，b0，如3第一节数的整除性显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。被2整除的整数称为偶数，不被2整除的整数称为奇数。由定义可得下面定理，证明留作练习。第一节数的整除性显然每个非零整数a都有4第一节数的整除性定理1

下面的结论成立：(ⅰ)ab

ab；(ⅱ)ab，bc

ac；(ⅲ)bai，i=1,2,,k

ba1x1

a2x2

akxk，此处xi(i=1,2,,k)是任意的整数；(ⅳ)ba

bcac，此处c是任意的非零整数；(ⅴ)ba,a0|b||a|;ba且|a|<|b|

a=0。第一节数的整除性定理1下面的结论成立：5第一节数的整除性定义2

若整数a

0，1，并且只有约数1和a，则称a是素数(或质数)；否则称a为合数。以后无特别说明，素数总是指正素数。定理2

任何大于1的整数a都至少有一个素约数。证明若a是素数，则定理是显然的。若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1,d2,,dk。

第一节数的整除性定义2若整数a0，1，并且只6第一节数的整除性不妨设d1是其中最小的。若d1不是素数，则存在e1>1，e2>1，使得d1=e1e2，

因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。

推论任何大于1的合数a必有一个不超过的素约数。证明使用定理2中的记号，有a=d1d2，其中d1>1是最小的素约数，所以d12

a。证毕。第一节数的整除性不妨设d1是其中最小的。若d1不是素数，7第一节数的整除性例1

设r是正奇数,证明:对任意的正整数n,有n

21r

2

r

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

bk=(a

b)(ak

1

ak

2b

ak

3b2

bk

1)=(a

b)q，其中q是整数。记s=1r

2

r

nr，则2s=2(2

r

nr)(3

r

(n

1)r)

(nr

2

r)=2(n

2)Q，

第一节数的整除性例1设r是正奇数,证明:对任意的8第一节数的整除性其中Q是整数。若n2s，由上式知n

22，因为n

2>2，这是不可能的，所以n

2s。例2

设A={d1,d2,,dk

}是n的所有约数的集合,则B=也是n的所有约数的集合。解由以下三点理由可以证得结论：(ⅰ)A和B的元素个数相同；(ⅱ)若diA，即din，则，反之亦然；第一节数的整除性其中Q是整数。若n2s，由上式知9第一节数的整除性(ⅲ)若di

dj，则。例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的正约数d与是成对地出现的。

第一节数的整除性(ⅲ)若didj，则10第一节数的整除性只有当d=,即n=d2时，d和才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。因为442<1997<452，所以在d(1),d(2),,d(1997)中恰有44个奇数，故d(1)

d(2)

d(1997)是偶数。第一节数的整除性只有当d=,即n=d2时11第一节数的整除性例4

设凸2n边形M的顶点是A1,A2,,A2n，点O在M的内部，用1,2,,2n将M的2n条边分别编号，又将OA1,OA2,,OA2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2,OA2A3,,OA2nA1的周长都相等。第一节数的整除性例4设凸2n边形M的顶点是A1,A12第一节数的整除性解假设这些三角形的周长都相等，记为s。则2ns=3(12

2n)=3n(2n

1)，即2s=3(2n

1)，因此23(2n

1)，这是不可能的，这个矛盾,说明这些三角形的周长不可能全都相等。第一节数的整除性解假设这些三角形的周长都相等，记为s13第一节数的整除性例5

设整数k

1，证明：(ⅰ)若2k

n<2k1，1

a

n，a2k，则2ka；(ⅱ)若3k

2n

1<3k+1，1

b

n，2b

1

3k，则3k2b

1。第一节数的整除性例5设整数k1，证明：14第一节数的整除性解

(ⅰ)若2k|a，则存在整数q，使得a=

q2k。显然q只可能是0或1。此时a=0或2k

，这都是不可能的，所以2ka；(ⅱ)若3k|2b-1，则存在整数q，使得2b-1=

q3k，显然q只可能是0，1,或2。此时2b-1=0，3k，或，这都是不可能的，所以3k2b

1。第一节数的整除性解(ⅰ)若2k|a，则存在15第一节数的整除性例6写出不超过100的所有的素数。解将不超过100的正整数排列如下：

第一节数的整除性例6写出不超过100的所有的素数。16第一节数的整除性12

34567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465

676869707172737475767778798081828384858687888990919293949596979899100

———————————————————————————————————————————————————————————————————————————第一节数的整除性123417第一节数的整除性按以下步骤进行：(ⅰ)删去1，剩下的后面的第一个数是2，2是素数,删去2后面的被2整除的数；(ⅱ)剩下的2后面的第一个数是3，3是素数,再删去3后面的被3整除的数；(ⅲ)剩下的3后面的第一个数是5，5是素数,再删去5后面的被5整除的数；(ⅳ)剩下的5后面的第一个数是7，7是素数,再删去7后面的被7整除的数.第一节数的整除性按以下步骤进行：18第一节数的整除性照以上步骤可以到素数2,3,5,7,11,等25个。由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。第一节数的整除性照以上步骤可以到素数2,3,5,719第一节数的整除性例7

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

a（n=1,2,3,）都是合数。解取a=4k4，对于任意的nN，有n4

4k4=(n2

2k2)2

4n2k2=(n2

2k2

2nk)(n2

2k2

2nk)。因为n2

2k2

2nk=(n

k)2

k2

k2，所以，对于任意的k=2,3,

以及任意的nN，n4

a是合数。第一节数的整除性例7证明：存在无穷多个正整数a，使得20第一节数的整除性例8设a1,a2,,an是整数，且a1

a2

an

=0，a1a2an

=n，则4n。解如果2n，则n,a1,a2,,an都是奇数。于是a1

a2

an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2n，即在a1,a2,,an中至少有一个偶数。

第一节数的整除性例8设a1,a2,,an是21第一节数的整除性如果只有一个偶数，不妨设为a1，那么2ai（2

i

n）。此时有等式a2

an=a1，在上式中，左端是(n

1)个奇数之和，右端是偶数，这是不可能的，因此，在a1,a2,,an中至少有两个偶数，即4n。第一节数的整除性如果只有一个偶数，不妨设为a1，那么222第一节数的整除性例9若n是奇数，则8n2

1。解设n=2k

1，则n2

1=(2k

1)2

1=4k(k

1)。在k和k

1中有一个是偶数，所以8n2

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

d(2)2

d(1997)2被4除的余数是多少？第一节数的整除性例9若n是奇数，则8n2123第一节数的整除性例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。第一节数的整除性例10证明：方程解若a1，a24第一节数的整除性由于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，第一节数的整除性由于1999被8除的余数是7，所以a1，25第一节数的整除性其中r和s是整数，而且只能取值0或4。这样a12

a22

a32被8除的余数只可能是1或5，但1999被8除的余数是7，所以这样的a1，a2，a3也不能使式(2)成立。综上证得所需要的结论。第一节数的整除性其中r和s是整数，而且只能取值0或4。这26习题一1.证明定理1。2.证明：若m

pmn

pq,则m

pmq

np。3.证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。4.设p是n的最小素约数，n=pn1，n1>1，证明：若p>，则n1是素数。5.证明：存在无穷多个自然数n，使得n不能表示为a2

p（a>0是整数，p为素数）的形式。习题一1.证明定理1。27初等数论NumberTheory初等数论NumberTheory28第一章整除理论整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。第一章整除理论整除性理论是初等数论的基础。本章要介绍带余29第一节数的整除性定义1

设a，b是整数，b

0，如果存在整数c，使得

a=bc成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号ba；如果不存在整数c使得a=bc成立，则称a不被b整除，记为ba。第一节数的整除性定义1设a，b是整数，b0，如30第一节数的整除性显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。被2整除的整数称为偶数，不被2整除的整数称为奇数。由定义可得下面定理，证明留作练习。第一节数的整除性显然每个非零整数a都有31第一节数的整除性定理1

下面的结论成立：(ⅰ)ab

ab；(ⅱ)ab，bc

ac；(ⅲ)bai，i=1,2,,k

ba1x1

a2x2

akxk，此处xi(i=1,2,,k)是任意的整数；(ⅳ)ba

bcac，此处c是任意的非零整数；(ⅴ)ba,a0|b||a|;ba且|a|<|b|

a=0。第一节数的整除性定理1下面的结论成立：32第一节数的整除性定义2

若整数a

0，1，并且只有约数1和a，则称a是素数(或质数)；否则称a为合数。以后无特别说明，素数总是指正素数。定理2

任何大于1的整数a都至少有一个素约数。证明若a是素数，则定理是显然的。若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1,d2,,dk。

第一节数的整除性定义2若整数a0，1，并且只33第一节数的整除性不妨设d1是其中最小的。若d1不是素数，则存在e1>1，e2>1，使得d1=e1e2，

因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。

推论任何大于1的合数a必有一个不超过的素约数。证明使用定理2中的记号，有a=d1d2，其中d1>1是最小的素约数，所以d12

a。证毕。第一节数的整除性不妨设d1是其中最小的。若d1不是素数，34第一节数的整除性例1

设r是正奇数,证明:对任意的正整数n,有n

21r

2

r

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

bk=(a

b)(ak

1

ak

2b

ak

3b2

bk

1)=(a

b)q，其中q是整数。记s=1r

2

r

nr，则2s=2(2

r

nr)(3

r

(n

1)r)

(nr

2

r)=2(n

2)Q，

第一节数的整除性例1设r是正奇数,证明:对任意的35第一节数的整除性其中Q是整数。若n2s，由上式知n

22，因为n

2>2，这是不可能的，所以n

2s。例2

设A={d1,d2,,dk

}是n的所有约数的集合,则B=也是n的所有约数的集合。解由以下三点理由可以证得结论：(ⅰ)A和B的元素个数相同；(ⅱ)若diA，即din，则，反之亦然；第一节数的整除性其中Q是整数。若n2s，由上式知36第一节数的整除性(ⅲ)若di

dj，则。例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的正约数d与是成对地出现的。

第一节数的整除性(ⅲ)若didj，则37第一节数的整除性只有当d=,即n=d2时，d和才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。因为442<1997<452，所以在d(1),d(2),,d(1997)中恰有44个奇数，故d(1)

d(2)

d(1997)是偶数。第一节数的整除性只有当d=,即n=d2时38第一节数的整除性例4

设凸2n边形M的顶点是A1,A2,,A2n，点O在M的内部，用1,2,,2n将M的2n条边分别编号，又将OA1,OA2,,OA2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2,OA2A3,,OA2nA1的周长都相等。第一节数的整除性例4设凸2n边形M的顶点是A1,A39第一节数的整除性解假设这些三角形的周长都相等，记为s。则2ns=3(12

2n)=3n(2n

1)，即2s=3(2n

1)，因此23(2n

1)，这是不可能的，这个矛盾,说明这些三角形的周长不可能全都相等。第一节数的整除性解假设这些三角形的周长都相等，记为s40第一节数的整除性例5

设整数k

1，证明：(ⅰ)若2k

n<2k1，1

a

n，a2k，则2ka；(ⅱ)若3k

2n

1<3k+1，1

b

n，2b

1

3k，则3k2b

1。第一节数的整除性例5设整数k1，证明：41第一节数的整除性解

(ⅰ)若2k|a，则存在整数q，使得a=

q2k。显然q只可能是0或1。此时a=0或2k

，这都是不可能的，所以2ka；(ⅱ)若3k|2b-1，则存在整数q，使得2b-1=

q3k，显然q只可能是0，1,或2。此时2b-1=0，3k，或，这都是不可能的，所以3k2b

1。第一节数的整除性解(ⅰ)若2k|a，则存在42第一节数的整除性例6写出不超过100的所有的素数。解将不超过100的正整数排列如下：

第一节数的整除性例6写出不超过100的所有的素数。43第一节数的整除性12

34567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465

676869707172737475767778798081828384858687888990919293949596979899100

———————————————————————————————————————————————————————————————————————————第一节数的整除性123444第一节数的整除性按以下步骤进行：(ⅰ)删去1，剩下的后面的第一个数是2，2是素数,删去2后面的被2整除的数；(ⅱ)剩下的2后面的第一个数是3，3是素数,再删去3后面的被3整除的数；(ⅲ)剩下的3后面的第一个数是5，5是素数,再删去5后面的被5整除的数；(ⅳ)剩下的5后面的第一个数是7，7是素数,再删去7后面的被7整除的数.第一节数的整除性按以下步骤进行：45第一节数的整除性照以上步骤可以到素数2,3,5,7,11,等25个。由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。第一节数的整除性照以上步骤可以到素数2,3,5,746第一节数的整除性例7

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

a（n=1,2,3,）都是合数。解取a=4k4，对于任意的nN，有n4

4k4=(n2

2k2)2

4n2k2=(n2

2k2

2nk)(n2

2k2

2nk)。因为n2

2k2

2nk=(n

k)2

k2

k2，所以，对于任意的k=2,3,

以及任意的nN，n4

a是合数。第一节数的整除性例7证明：存在无穷多个正整数a，使得47第一节数的整除性例8设a1,a2,,an是整数，且a1

a2

an

=0，a1a2an

=n，则4n。解如果2n，则n,a1,a2,,an都是奇数。于是a1

a2

an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2n，即在a1,a2,,an中至少有一个偶数。

第一节数的整除性例8设a1,a2,,an是48第一节数的整除性如果只有一个偶数，不妨设为a1，那么2ai（2

i

n）。此时有等式a2

an=a1，在上式中，左端是(n

1)个奇数之和，右端是偶数，这是不可能的，因此，在a1,a2,,an中至少有两个偶数，即4n。第一节数的