初等数论-整除课件

《初等数论》8/26/202306:44教师：何艳数论的基本内容8/26/202306:44按照研究方法的不同，数论可分为初等数论解析数论代数数论几何数论参考书目8/26/202306:441、南基洙主编《初等数论》；2、柯召、孙琦编著《数论讲义》，高等教育出版社；3、闵嗣鹤、严士健编《初等数论》，高等教育出版社；4、郑克明主编《初等数论》，西南师范大学出版社。初等数论8/26/202306:40第一章整除§1

自然数与整数归纳原理设S是N的一个子集，满足条件：1∈S;如果n

∈S，则n+1

∈S,那么，S=N.8/26/202306:40定理1

数学归纳法设P(n)是关于自然数n的一种性质或命题.如果当n=1时，P(1)成立；由P(n)成立必可推出P(n+1)成立，那么，P(n)对所有自然数n成立.8/26/202306:40定理2

最小自然数原理设T是N的一个非空子集.那么，必有t0

∈T,使对任意的t

∈T有t0≤t，即t0是T中的最小自然数.8/26/202306:40定理3

最大自然数原理设M是N的非空子集.若M有上界，即存在

a∈N,使对任意的m

∈M有m≤a,那么必有m0

∈M，使对任意的m

∈M有m

≤m0，即m0是M中的最大自然数。8/26/202306:40定理4

第二数学归纳法设P(n)是关于自然数n

的一种性质或命题.如果(ⅰ)当n=1

时，P(1)成立；(ⅱ)设n>1.

若对所有的自然数m<n,P(m)成立，则必可推出P(n)成立，那么,P(n)对所有自然数n成立.8/26/202306:40定理5鸽巢原理设n是一个自然数.现有n个盒子和n+1个物体.无论怎样把这n+1个物体放入这n个盒子中，一定有一个盒子中被放了两个或两个以上的物体。8/26/202306:45§2

整除8/26/202306:45定义1设a，b是整数，a≠0，如果存在整数q，使得b=aq，则称b可被a整除，记作a⏐b

，且称b是a的倍数，a是b的约数(因数、除数)；如果不存在整数q使得b=aq成立，则称b不被

a整除，记为a

b。被2整除的数称为偶数，不被2整除的称为奇数8/26/202306:45定理1

下面的结论成立：|a|||b|；(ⅰ)

a|b

(-a)|b

a|(-b) (-a)|(-b)(ⅱ)

a⏐b，b⏐c

⇒

a⏐c；(ⅲ)

a⏐b,

a⏐c对任意x、y,有a⏐bx+cy,一般地，a⏐bi，i=

1,

2,

,

ka⏐b1x1

+

b2x2

+

+

bkxk，此处xi（i=1,2,

,k）是任意的整数；(ⅳ)

a⏐b

ac⏐bc，c是任意的非零整数；(ⅴ)a⏐b且b⏐a

⇒a=±b；(ⅵ)a⏐b，b

≠0

⇒|a|

≤|b|；a⏐b且|b|<|a|

⇒b

=0.8/26/202306:41例1

证明：若3|n且7|n，则21|n.例2

设a=2t-1.

若a|2n,则a|n.例3设a

、b是两个给定的非零整数，且有整数

x、y，使得ax+by=1.

证明：若a|n且b|n,则ab|n.例4

设f(x)=anxn+an-1xn-1+

+a1x+a0

∈Z[x],8/26/202306:41其中Z[x]表示全体一元整系数多项式组成的集合.若d|b-c,则d|f(b)-f(c).定义28/26/202306:41显然每个非零整数a都有约数±1，±a，称这四个数为a的显然因数，a的另外的因数称为非显然因数。若整数a≠0，±1，并且只有约数±1和±a，则称a是素数（或质数）；否则称a为合数。以后在本书中若无特别说明，素数总是指正素数。定理2设A

={d1,d2,

,dk

}是n的所有约数的集合，则B=

也是n的所有约数的集合。解 由以下三点理由可以证得结论：A和B的元素个数相同；若di∈A，即di⏐n，则

n，反之亦然；(ⅲ)

若di

≠dj，则.8/26/202306:42定理38/26/202306:42a>1是合数的充要条件是

a=de,1<d<a,1<e<a;若d>1,

q是不可约数且d|q,则d=q.定理4

若a是合数，则必有不可约数p|a.定理5

设整数a≥2,那么a一定可表为素数的乘积8/26/202306:42(包括a本身是素数)，即a=p1p2

ps其中pj（1≤j

≤s)是素数.证明

当a=

2时，结论显然成立。假设对于2≤a≤k，式(1)成立，我们来证明式(1)

对于a

=k

+1也成立，若k

+1是素数，式(1)显成立.如果k+1是合数，则存在素数p与整数d，使得k+1=pd.由于2≤d

≤k，由归纳假定知存在素数q1

,q2

,

,ql，使得d

=q1q2

ql，从而k

+1=pq1q2

ql.从而由归纳法推出式(1)对任何大于1的整数a成立。证毕。推论8/26/202306:42任何大于1的合数a必有一个不超过a1/2的素因数。证明由于a是合数，故存在整数b和c使a＝bc,其中:1<b<a,1<c<a.若b和c均大于a1/2,则a＝bc＞a1/2·a1/2＝a,这是不可能的.因此b和c中必有一个小于或等于a1/2.例5写出不超过100的所有的素数.8/26/202306:42解

将不超过100的正整数排列如下：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100按以下步骤进行：8/26/202306:42删去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的全部素数.在例5中所使用的寻找素数的方法,称为

Eratosthenes筛法.它可以用来求出不超过任何固定整数的所有素数.在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的.8/26/202306:47定理7.

(Euclid)素数有无穷多个.证明：(反证法)假设素数是有限多个,共有n个,令它们是p1

,p2

,…,pn,并令a=

p1p2…pn+1.

若a是素数,则因a≠pi，其中1<i<n,故素数个数最少是n+1个,这与假设素数个数为n个矛盾.若a

不是素数,则由定理4知,a

的大于1的最小因数b是素数.由于pi|

p1p2…pn

,但pi

不能整除1,

故pi不能整除a,因此b≠pi,其中1≤i≤n,那么a也为素数.所以在p1,p2,…,pn,还有素数,这也与已知共有n个8素/26/数202矛3

盾.06:47最大公因数与最小公倍数8/26/202306:47定义3最大公因数8/26/202306:43设al

,a2,…,ak和d都是整数,k≥2.若d|ai，1≤i≤k,则称d是al,a2,…,ak的公因数.所有公因数中最大的那一个数，称为al

,a2,…,ak的最大公因数,记为(al,a2,…,ak).由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。显然，(a

,1)=1，(a,0)=|a|，(a,a)=|a|；定理8下面的等式成立：8/26/202306:43（a1

,a2)=(a2

,a1)=(-a1

,a2)；一般地(a1

,

a2

,

,ai

,

,

ak)=

(ai

,

a2

,

,a1

,

,

ak)=

(-a1

,

a2

,

,

ak)=(|a1|

,

|a2|

,

,

|ak|)；若a1|aj

,j

=2,

,k,则（a1

,a2)=(a1

,a2,

,ak)=(a1)=|a1|对任意整数x

，(a1

,a2)=(a1

,a2

,a1x)(a1

,

,

ak)=(a1

,

,

ak

,

a1x)；对任意整数x,（a1

,a2)=(a1

,a2+a1x)(a1

,a2

,a3

,

,ak)=(a1

,a2+a1x

,a3

,

,ak)；(ⅴ)若p是素数,则(p

,a)=1或p⏐a；一般地（p

,a1,

,ak)=1或p⏐a

.例58/26/202306:43定义5

互素8/26/202306:43如果(a1

,a2

,

,ak)=1，则称a1

,a2

,

,ak是互素的（或互质的）；如果(ai,aj)=1，1≤i,j≤k，i≠j，则称a1,a2

,

,ak是两两互素的（或两两互质的）.显然，a1,a2,

,ak两两互素可以推出(a1,a2,

,ak)=1，反之则不然，例如

(2,6,

15)=1，但(2,6)=2.定理98/26/202306:43(a1,a2,

,ak)=1的充要条件是存在整数x1,x2,

,xk，使得a1x1

+a2x2

+

+akxk

=1.充分性

若式(1)成立，如果(a1,a2,

,ak)=d>1，那么由d⏐ai（1≤i≤k）推出d⏐a1x1

+a2x2

+

+akxk

=1，这是不可能的.所以有(a1,a2,

,ak)=1.证毕.定理10设正整数m|(a1,a2,

,ak).我们有m(a1/m,a2/m,

,ak/m)=

(a1,a2,

,ak)特别地有=

1.8/26/202306:43定义6最小公倍数8/26/202306:43设a1

,a2,

,ak和m都是整数,k≥2.若ai|m,1≤i≤k,则称m是a1,a2,

,ak的公倍数.在a1

,a2

,

,ak所有公倍数中最小的那一个正整数,称为a1,a2,

,ak的最小公倍数,记为[a1,a2,

,ak].定理118/26/202306:43[a1

,a2]=[a2

,a1]=[-a1

,a2].

一般地有,[a1,a2,

,ai,

,ak]=

[ai,a2,

,a1,

,ak]=

[-a1,a2,

,ai,

,ak]若a2|a1

,则[a1,a2]=|a1|；对任意的d|a1[a1

,a2]=[a1,a2,d][a1,a2,

,ak]=

[a1,a2,

,ak,d]定理128/26/202306:43设m>0,

我们有[ma1

,…,mak]=m[a1

,…,ak]§3

带余除法与辗转相除法8/26/202306:43定理1带余数除法设a与b是两个整数，a

≠

0,

则存在唯一的两个整数q和r，使得b=aq+

r，0≤r≤

|a|

(1)证明

存在性

若a⏐b，b

=

aq，q∈Z，可取r

=

0.若a b，考虑集合

A=

{b

+

ka；k∈Z

}，在集合A中有无限多个正整数，设最小的正整数是r=

b

+

k0a，则必有

0

<

r<|a|，

(2)否则就有r

≥

|a|.因为a b，所以r

≠

|a|.于是r>

|a|，即

b+

k0a>

|a|，b+

k0a

−

|a|

>

0，这样,在集合A中,又有正整数r1=b

+

k0a

−

|a|

<r，这与r的最小性矛盾。8/26/202306:43所以式(2)必定成立.

取q

=

−

k0

知式(1)成立.存在性得证.8/26/202306:43唯一性

假设有两对整数q′、r′与q′′、r′′都使得式(1)成立，即b

=q

′′a

+r

′′=q

′a

+r

′，0

≤r

′,r

′′≤|a|，则(3)(q′′

−

q

′)a

=

r

′

−

r

′′，|r

′

−

r

′′|

<

|a|，因此r

′−r

′′=0，r

′=r

′′，再由式(3)得出q

′=q

′′，唯一性得证.证毕.定理28/26/202306:48设a与b是两个整数，a≠0，设d是一给定的整数.那么，一定存在唯一的两个整数q1和r1，使得b=aq1

+

r1，d≤r1≤

|a|

+d

(4)此外，a⏐b的充要条件是a⏐r1.定义18/26/202306:48称式(1)中的q是b被a除的商，r是b被a除的最小非负余数。式(4)中的r1统称为余数.由定理1可知，对于给定的整数a，可以按照被a除的余数将所有的整数分成a类。在同一类中的数被a除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。推论38/26/202306:48设a>0.

任一整数被a

除后所得的最小非负余数是且仅是0,1,…,a-1这a个数中的一个.

由此全体整数按被a除后所得的最小非负余数可分为两两不相交的a个类.0moda,1moda,…,(a-1)modaa=2时，全体整数分为两类：

0mod2，1mod2例28/26/202306:49(ⅰ)

0mod2∩

0mod3=0mod6;1mod2∩

1mod3=1mod6；0mod2∩

1mod3=4mod6.例31mod2=1mod6∪3mod6∪5mod6例4

a进位表示8/26/202306:49设a≥2是给定的正整数.那么，任一正整数n必可唯一表为

n=rkak+rk-1ak-1+…+r1a+r0,

(4)其中整数k

≥0，0≤rj

≤a-1，(0≤j≤k)，rk≠0.这就是正整数的a进位表示.例58/26/202306:49设a>2是奇数.证明：一定存在正整数d

≤a-1,使得a|2d-1.设d0是满足(ⅰ)的最小正整数d.那么，a|2h-1(h∈N)的充要条件是d0|h.必有正整数d使得（2d-3,a)=1.定理4

(Euclid)欧几里德算法.设a,b是给定的两个整数，b≠0,b a.

我们一定可以重复定理1得到下面的等式：0＜rl＜|b|0＜r2＜r10＜r3＜r2a=bq1+r1,b=r1q2+r2,r1=r2q3+r3,…….rn-2=rn-1qn+rn,

0＜rn＜rn-1rn-1=rnqn+1+0则(a,b)=rn.8/26/202306:45证明:由于|b|＞r1＞r2＞…＞rn＞0,

故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式,即rn+1=0.根据前面定理可知：

(a,b)=(b,r1)=…=(rn-1,rn)=(rn,0)=rn.欧几里德算法也称辗转相除法.8/26/202306:45在Euclid算法中,

由:

rn=rn-2-

rn-1qn,

rn-1=rn-3-rn-2qn-1,得rn=rn-2(1+qnqn-1)-rn-3qn,再将rn-2=rn-4-rn-3qn-2代入上式,如此继续下去,最后得到:rn=sa+tb,

其中s和t是整数.于是有(a,b)是a和b线性组合表示定理.定理5

(ⅲ)若任给整数a,b,则存在整数x和y,使得(a,b)=ax+by.容易证明下面结论．(ⅱ)a和b的公因数整除(a,b).8/26/202306:45例68/26/202306:45①用欧几里德算法求(1997,57).②用1997和57的线性组合表示(1997,57)．③求1997和57的所有公因数．解①用下划线标识余数．1997＝57·35

+257＝2·28

+12＝l·2

+

0因此,(1997,57)=l,即1997和57是互素的.②

1=57-2·28=57-(1997-57·35)·28=-28·1997+(57+57·35·28）=-28·1997+981·57③由于1997和57是互素的,公因数只有1和-1.8/26/202306:45例7设m,n是正整数.证明（2m-1,2n-1)=2(m,n)-18/26/202306:45§4

最大公因数理论8/26/202306:45定理1

aj|c(1≤j≤k)的充要条件是[a1,…,ak]|c证明：充分性显然.必要性，设[a1

,…,ak]=m.c是a1

,…,ak的任一公倍数,利用带余除法得:c

=mq+r,0≤r<m,aj|c,

aj|m,aj|r,(1≤j

≤k).故a1|r,

…,ak|r,即r是a1,…,ak的公倍数.但由于: 1≤r＜m与

m是a1,…,ak的最小公倍数发生矛盾,故:

r=0,即:

c＝mq.故m|c.即[a1,…,ak]|c8/26/202306:45定理28/26/202306:45设D是正整数.那么D

=（a1,a2,

,ak）的充要条件是：D|

aj(1≤

j≤k);若d⏐aj

(1≤j

≤k),则d⏐(a1,a2,

,ak).这个结论表明：公约数一定是最大公约数的约数。定理38/26/202306:45(ma1,

ma2,

,

mak)=

|m|(a1,a2,

,ak).定理4(ⅰ)(a1

,a2

,…,ak)=((

a1,a2),a3,…,ak)；(ⅱ)

(a1,a2

,…,ak+r)=((

a1

,…,ak),(ak+1,…,ak+r))；推论（a1,a2)(b1,b2)=(a1b1,a1b2,a2b1,a2b2)定理58/26/202306:45若(m,a)=1，则(m,ab)=(m,b).证明:(m,b)=(