初等数论期末复习资料

数论教案

§1整数的整除 带余除法

1 整数的整除

设a,b是整数,且b≠0,如果有整数q,使得a=bq,则称b整除a,记为b|a,也称b是a的因数,a是b的倍数. 如果没有整数q,使得a=bq,则称b不能整除a,记为b?a.例如 2|4, 4|-12, -5|15; 2?3， -3?22. 在中小学数学里,整除概念中的整数是正整数,今天讲的整除中的整数可正可负. 判断是否b|a？当a,b的数值较大时,可借助计算器判别.

如果b除a的商数是整数,说明b|a;如果b除a的商不是整数,说明b?a.

例1判断下列各题是否b|a？(1) 7|127? (2) 11|129? (3) 46|9529? (4) 29|5939? 整除的简单性质

(1)如果c|b,b|a,那么c|a;

(2)如果d|a,d|b,那么对任意整数m,n,都有d|ma+nb.

(3)如果

a1,a2,?,an都是m的倍数,q1,q2,?,qn是任意整数,那么

q1a1?q2a2???qnan是m的倍数.

(4)如果c|a,d|b,那么cd|ab。

例如： 2|4,2|(-6),那么2|4+(-6),2|4-(-6). 2|4,3|(-6),那么2×3|4×(-6). 例2证明任意2个连续整数的乘积,一定可被2整除. 练习 证明任意3个连续整数的乘积,一定可被3整除. 2.带余除法

设a,b是整数,且b>0,那么有唯一一对整数q,r使得 a=bq+r,0?r＜ b. (1) 这里q称为b除a的商,r称为b除a的余数.

例如-5=3×(-2)+1 5=3×1+2 -5=(-3)×2+1 5=(-3)×(-1)+2 15=(-5)×(-3), -24=(-2)×12. 事实上,以b除a的余数也可以是负的.例如 -5=3×(-1)-2=3×(-2)+1.

求b除a的余数,也称为模运算(取余):mod.可用计算器进行.

1

具体操作:输入a-按mod(取余)键-输入b-按=键得出余数.如果b除a的余数=0,则b|a;如果b除a的余数≠0,则b?a.

例3 利用计算器求余数:

(1) 7除127;(2)11除-129 ;(3)46除-9529;(4)-29除5939 奇数、偶数及性质

能被2整除的整数称为偶数.如,0,4,10,-6,-8都是偶数. 不能被2整除的整数称为奇数.如,-5,-3,1,7,11都是奇数. 偶数的形式为2n(n是整数);奇数的形式为2n-1(n是整数).

奇数、偶数的性质: 偶数±偶数=偶数,奇数±奇数=偶数,奇数±偶数=奇数,

偶数×偶数=偶数,偶数×奇数=偶数,奇数×奇数=奇数.

例如 2+4,2-4,3+1,3-1,3+4,6+5

设a,b是任意两个整数,则a+b与a-b同奇同偶. 例如3+5,3-5,6+3,6-3,

22a?b?2n,证明n是偶数. 例4设a,b,n是任意3个整数,而且

例5设a是任一奇数,试证明8|

例6设n是正整数,证明形如3n-1整数不是完全平方数.

证明 对任意整a,设a=3q或a=3q±1,于是

222qa=9或 a=9q±6q+1=3(3q2±2q)+1.

a?1.

22即

a2≠3n-1,故3n-1不是完全平方数.

练习 设n是正整数,证明形如4n-1、4n+2的整数都不是完全平方数. 习题:P3-4:1t,2t.

§2公因数、最大公因数

1.最大公因数、辗转相除法

2

中小学里的公因数、最大公因数的概念：

几个数的公有因数叫做这几个数的公因数.公因数中最大的整数称为这几个数的最大公因数. (1)几个数:不能确定;(2)因数、公因数:都是正整数; 最大公因数:没有专门的符号. 定义设1a,a2,?,an,d都是整数,d≠0,如果dai,i=1,2,?,n,称d是

a1,a2,?,an的公因数,a1,a2,?,an的公因数中最大的整数称为最大公因数.记为(a1,a2,?,an).如果(a1,a2,?,an)=1,则

称12n互质。

例1 (-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.

在中小学数学里,求正整数a,b的最大公因数主要有这个样几种方法：

(1)观察法；

(2)将a,b的所有公因数都求出来,再从中挑最大的； (3)用短除法.

辗转相除法:设a,b是正整数,而且有

a,a,?,aa?bq1?r1,0?r1?b;

b?rq12?r2,0?r2?r1; r1?r2q3?r3,0?r3?r2;

????? （*）

rn?2?rn?1qn?rn,0?rn?rn?1;

rn?1?rnqn?1.

(a,b)?rn。

例2用辗转相除法求(123,78),

练习:用辗转相除法求(66,54).

下面说明辗转相除法的正确性.先证明

性质1设整数a,b,c不全为0,而且有整数q使得a=bq+c则(a,b)=(b,c). 证明 由a,b,c不全为0知,(a,b)、(b,c)都存在.

因(a,b)|a,(a,b)|b,c=a-bq,得(a,b)|c,又得(a,b)?(b,c); 反之,由(b,c)|b,(b,c)|c,a=bq+c,得(b,c)|a,(b,c)?(a,b). 所以(a,b)=(b,c).

3

由(*)式知

b?r1?r2???rn?1?rn?0,而n是有限正整数,再由性质1得

(a,b)?(b,r1)?(r1,r2)??=(rn?2,rn?1)?(rn?1,rn)?(rn,0)?rn.

2.最大公因数的性质 最大公因数的几个性质：

性质2 (am,bm)=(a,b)m,m>0.(短除法的根据) 例3求(84,90),(120,36).

(84,90)=3(28,30)=6(14,15)=6.(120,36)=12(10,3)=12. 性质3 (a,b)=(|a|,|b|). 性质4 (a,b,c)=((a,b),c).

例4求(-84,120),(-120,-72),(24,-60,-96).

例5设n是任意整数,证明3n?15n?2是既约分数.

证明 设d=(3n+1,5n+2),则d|3(5n+2)-5(3n+1),即d|1,d=1，

所以3n+1与5n+2互质.

作业 1.利用辗转相除法求(84,90). 2.求(120,36).

3n?1 3.设n是整数，证明

7n?2是既约分数。

§3整除的进一步性质及最小公倍数

1.整除的进一步性质

推论1设a,b不全为零,那么有s,t∈Z使得as+bt=(a,b). 证明 将(*)中每式中的余数解出得

rn?rn?2?rn?1qn,

rn?1?rn?3?rn?2qn?1,?,

r2?b?rq12,

r1?a?bq1rn?1,rn?2,?,r2,r1的表达式依次代入到rn?rn?2?rn?1qn中就得au+bv=rn=(a,b)=d,u,v∈Z.

例1用辗转相除法求(120,54),并求整数u,v使得

120u+54v=(120,54).

解∵120=2×54+12,54=12×4+6,12=6×2,∴(120,54)=6. 12=120-2×54,6=54-12×4=54-(120-2×54)×4 =120×(-4)+54×9. ∴ u=-4,v=9.

练习用辗转相除法求(84,45),并求整数u,v使得

84u+45v=(84,45).

设a,b都是正整数,问a,b的公因数与最大公因数有什么关系？ 例2 ①求(12,18)及12与18的所有正的公因数；

通过这个例子,请同学们观察最大公因数与公因数有何关系？能否提出自己的猜想？能否证明自己的猜想？

性质1 设d 是a,b的最大公因数,那么,a,b的任一公因数都是d的因数.

4

,再将

证明 如果d=(a,b),由性质2有u,v∈Z使得au+bv=d.设s是a,b的任一公因数,则s|au,s|bv,且s|au+bv,即s|d.

ab,性质2如果d=(a,b),则(

dd)=1.

性质3如果(a,c)=1,且c|ab,则c|b. 性质4如果(a,c)=1,则(ab,c)=(b,c). 性质5如果(a,b)=1,且a|c,b|c,则ab|c. 例3证明 三个连续整数的积一定可被6整除. 2最小公倍数

定义 如果m是

a1,a2,?,an中每一个数的倍数,则称m是整数

a1,a2,?,an的一个公倍数.a1,a2,?,an的公倍中最小正整数称为a1,a2,?,an的最小公倍数.用

[

a1,a2,?,an]来表示.

a1,a2,?,an]=[|a1|,|a2|,?,|an|].

例如 [2,4,-3]=12,[15,12,20]=60,[6,10,15]=30.

定理3 [

定理4 设a,b是两个正整数,则 (i)a,b的任一公倍数是[a,b]的倍数；

ab(ii)[a,b]=

(a,b).而且若(a,b)=1,则[a,b]=ab.

证明(i)设m是a,b的任一公倍数,而且m=t[a,b]+r,0?r<[a,b]

,因m,[a,b]都是a,b的公倍数,由r=m-t[a,b]知r也是a,b的公倍数,若0

a[a,b]ab?(ii)记d=,则d是整数,由a|[a,b],a|[a,b]及

[a,b]db,

b[a,b]?da知d|a,d|b,即d是a,b的公因数.

ababdabba??Z?a?b 设h是a,b的任一公因数,由,所以h|d,

hhh是a,b的公倍数及TH16知[a,b]|h,即[a,b]hh

5

ab(a,b)=d,从而(a,b)=

[a,b].

定理5 设

a1,a2,?,an都是正整数,令

[a1,a2]?m2,[m2,a3]?m3,?,[mn?1,an]?mn,则[a1,a2,?,an]?mn.

定理19设

a1,a2,?,an是n(?2)个正整数,且两两互素,则

[a1,a2,?,an]?a1a2?an

例2 求[123,456,-789]

例3 求正整数a,b,满足:a+b=120,(a,b)=24,[a,b]=144.

abc例14设a,b,c是正整数,则[a,b,c]=

(ab,bc,ca)

作业:P14:1.

2.求(84,45),并求整数u,v使得84u+45v=(84,45) .

§4质数 算术基本定理

1.质数

定义设整数a>1,如果a除了1和a外再无其它正因数,则称a为质数,也称为素数.否则,称a为合数. 2,3,5,7,11都是质数，4,6,8,9,10都是合数.

1-100内有素数25个,1-1000内有素数168个,1-10000内有素数1229,10万内有素数9592个,100万之内78498个.

定理1设整数a>1,则a除1外的最小正因数q是素数,而且当a是合数时,q?

a.

证明 假定q是合数,设q=bc,1

若a是合数,设a=qm,由q的最小性知a=qm?qq,即q?

a.

6

素数判定定理 设整数a>1,不超过

a所有素数为p1,p2,?,pk,如果pi?a,i=1,?,k,则a为素数.

例1 以下正整数哪个是素数？哪个是合数？ 231,89,103,169.

素数判别威尔逊定理:设整数p>1,那么p是素数的充分必要条件是 p|(p-1)!+1. 例2 利用威尔逊定理判别3,5,7,11都是素数.

当p较大时,(p-1)!+1的数值非常大,在实际运用时不可行。 定理2 设P是素数,a为任一整数,则或P|a,或(P,a)=1.

证明 因(P,a)|P,P为素数,所以(P,a)=P,或(P,a)=1.即P|a,或(P,a)=1.

2.整数的唯一分解定理

?定理3 任何a>1的整数都有标准分解式:a=p11p?22?p?kk (3)

这里

p1,p2,?,pk为不同素数,整数?i?0,i=1,?,k.

p??1 若正整数

a>1

的标准分解式为

a=

12?推论

k1p2?pk,则a的正因数?1?2?kd=

p1p2?pk,0??i??i,i=1,?,k.而且a有不同的正因数(1??1)(1??2)?(1??k)个.

?推论2设a=

p11p?22?p??1?2?kkk,b=

p1p2?pk,?i?0,?i?0,i=1,?,k.

则

?1?2?kp??(1)(a,b)=p1p2?pk,[a,b]=

11p22?p?kk，

其中?i?min(?i,?i),?i?max(?i,?i),i=1,?,k.

(2)a,b共有正公因数(1??1)(1??2)?(1??k)个; (3)a,b共有公因数

2(1??1)(1??2)?(1??k)个.

例3 求725760,154200的标准分解式,并求它们的最大公因数和最小公倍数.

解 因725760=28×5×11×41, 154200=23×3×52×257,

所以(725760,154200)=

23×5, [725760,154200]=282×3×5×11×41×257.

7

d为

例4求下列各组数的最大公因数及其公因数的个数:

(1)123,78；(2)120,54.

练习:求下列各组数的最大公因数及其公因数的个数:

(1)125,70；(2)140,56.

22例8设p,q都是大于3的素数,证明24|.

p?q3质数的多少和质数的求法

定理4 素数有无穷多个.

证明 反证法,设质数只有k个:

p1,p2,L,pk,令M?p1p2Lpk?1,

M>1,于是M有素数因数p.因

pi?M,i=1,2,?,k,p|M,所以p≠pi,i=

1,2,?,k.这就是说,

p1,p2,L,pk,p是k+1个不同素数.这与假设矛盾.

1-n之间的所有素数怎样求出来？

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

按以下步骤进行：

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

(2)删去2后面被2整除的数(从4开始),2后面剩下的第一个数3是素数； (3)删去3后面的被3整除的数(从9开始),3后面剩下的第一个数5是素数； (4)删去5后面的被5整除的数(从25开始),5后面剩下的第一个数7是素数； ? ?

现在表中剩下的就全为素数了:

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.判别1577是否为素数;2.P19:5t；

8

3.求725760,154200的标准分解式,并求它们的最大公因数和最小公倍数,并求它们的所有公因数的个数。

§5 函数[x],{x}及其应用

1. 函数[x],{x}的定义

定义1 设x是实数,以[x]表示不超过x的最大整数，称它为x的整数部分，又称{x} = x ? [x]为x的小数部分。 例1 [3.5]=3,[-3.5]=-4,[-0.1]=-1,[0.1]=0,[?]=3,[-?]=-4. 性质 设x与y是实数,则 (1)x?y?[x]?[y]；

(2)若m是整数,?[m?x]=m?[x]； (3)若0?x<1,则[x]=0；

aa[]+b{}.

(4)(带余除法)设a,b是整数,且b>0,则a=b

bbaraaraa?q?,故[]=q,{}?,所以a=b[]+b{}.

设a=bq?r,0?r

bbbbbbba[]个。

(5)设a与b是正整数,则1-a中能被b整除的整数有

baa[].

证明 能被b整除的正整数是b,2b,3b,?,因此,若数1,2,?,a中能被b整除的整数有k个,则kb?a<(k+1)b?k?

bb10150099例2 不超过101且是5的倍数的正整数有[

5]=20个,100-500的整数中7的倍数的正整数有[7]-[7]=71-14=57.

2. 函数[x]的应用

设

p是素数,n是整数,如果pk│n,

pk?1?n,则称

pk恰好整除n.

kp例3设是素数,那么在1-n的整数中,恰好被p整除的整数有多少个？

定理1 在n!的标准分解式中,质因数p的指数是

9

nn h=[]+[2pp]+[

np3]+?

证明 在1,2,3,?,n中,

①

nn恰被p整除的整数有[]-[2ppnp2np3npr]-[

]个;

② 恰被p整除的整数有[

np3]个;

③ 恰被p整除的整数有[]-[

np4]个;?,

④ 恰被p整除的整数有[]-[

npr?1np3]个,?,于是

nnh=[]-[2pp性质 [

]+2([

np2]-[

np3])+3([]-[

np4])+?+r([

npr]-[

npr?1nn])+?=[]+[2pp]+[

np3]+?.

npr?1]=[[

npr]/r].

例3 求50!的标准分解式中,素数2,3,5的指数,并确定50!的十进制数的末尾0的个数. 练习1:200-300的整数中,求11的倍数的整数的个数.

练习2:60!的十进制数的末尾0的个数. 作业P23:1t.

2t,求100!的十进制数的末尾0的个数.

习题课

第二章 不定方程

§1二元一次不定方程 1.二元一次不定方程概念

例1百鸡问题:“鸡翁一,值钱五,鸡母一,值钱3,鸡雏三,值钱一.百钱买百鸡,问鸡翁、鸡母、鸡雏各几何？” 设百钱买鸡翁、鸡母、鸡雏分别x只、y只、z只.依题意得

10

x+y+z=100,且5x+3y+z/3=100. 整理得 14x+8y=200且x+y+z=100.

这里要求x,y,z都是非负整数.14x+8y=200称为二元一次不定方程.

二元一次不定方程的一般形式为ax+by=c,(a,b,c∈Z).如果整数m,n满足am+bn=c, 则称m,n为ax+by=c的一组整数解,ax+by=c的一组已知整数解,也称为特解. 2.二元一次不定方程解法

定理1二元一次不定方程ax+by=c有整数解的充分必要条件是,(a,b)|c. 证明 若不定方程ax+by=c有整数解m,n,则am+bn=c,因为(a,b)|a,(a,b)|b,所以 (a,b)|am+bn,即(a,b)|c.

反之,若(a,b)|c,设c=t(a,b).由第一章§3定理1知,有整数u,v使得au+bv=(a,b),两边都乘以t得aut+bvt=t(a,b)=c,即ut,vy是ax+by=c的整数解。

定理2二元一次不定方程 ax+by=c,(a,b)=1 (1) 有整数解m,n,则方程的一切整数解为

x=m-bt,y=n+at,t∈Z,或x=m+bt,y=n-at,t∈Z. (2) 证明 易知?t∈Z,由(2)得到的整数x,y都是方程(1)的解.

设x,y是(1)的任一整数解,于是ax+by=c,am+bn=c，所以a(x-m)+b(y-n)=0,又得 a(x-m)=-b(y-n),从而b|a(x-m).因为(a,b)=1,所以b|(x-m),设x-m=bt,t∈Z,a(x-m) =-b(y-n)得y-n=-at,这样就得x=m-bt,y=n+at,t∈Z. 3.例子与应用

例1 求14x+8y=200的一切整数解和所有非负整数解. 例2 求111x-321y=75的一切整数解.

例3 甲物品每件12元，乙物品每件18元，现用100元钱去买这两种物品，若要求每种物品至少买1件，且尽量不剩或少剩钱，问甲乙物品各买多少件？ 作业P31:1(a),2.

§2多元一次不定方程

n元一次不定方程的一般形式为 a1x1?a2x2???anxn?N (1) 其中a1,a2,?,an,N?Z.n?2是整数.

Th1 不定方程(1)有整数解充分必要条件是,(a1,a2,?,an) |N.

11

例1求9x+24y-5z=1000的一切整数解.

解 因(9,24,-5)=1,所以不定方程有整数解,因(9,24)=3,可设9x+24y=3u,于是 ①3x+8y=u, ②3u-5z=100

①的通解为x=u-8s,y=-u+3s,s∈Z,②的通解为u=5t,z=-20+3t,t∈Z. 故原不定方程的通解为x=5t-8s,y=-5t+3s,z=-20+3t,s,t∈Z.

例2 把17/60写成分母两两互质的三个既约分数之和.

17xyz???60345,整理得20x+15y+12z=17.因(20,15,12=1,不定故方程有整数解,设20x+15y=5u,则 ①解 因60=3×4×5,设

4x+3y=u, ②5u+12z=17.

①的通解为

x=u-3s,y=-u+4s,s∈Z,②的通解为

u=1-12t,z=1+5t,t∈Z. x=1-12t-3s,y=-1+12t+4s,z=1+5t,s,t∈Z.

17所以，60?1?12t?3s?1?12t?4s1?5t3?4?5.当t=s=0时,x=-y=z=1,此时有 171?1160?3?4?5. 作业:1求3x+6y-5z=15的一切整数解.

§3 勾股数

1.不定方程x2?y2?z2

不定方程x2?y2?z2的一组整数解(x,y,z)称为一组勾股数.

例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股数.

定理 不定方程x2?y2?z2， (1)

满足x>0,y>0,z>0,(x,y)=1,2 |x (2)

一切正整数解可由下式表出：x=2ab,y=a2?b2,z=a2?b2 (3)

其中a>b>0,(a,b)=1,a,b一奇一偶. (4) ① a=2,b=1,x=4,y=3,z=5; ②a=3,b=2,x=12,y=5,z=13; ③ a=4,b=1,x=8,y=15,z=17; ④a=4,b=3,x=24,y=7,z=25; ⑤ a=5,b=2,x=20,y=21,z=29; ⑥a=5,b=4,x=40,y=9,z=41. 2.其它不定方程

例3 求不定方程的全部整数解 ①xy=6, ②xy-x+y-4=0.

解① x=±1且y=±6,或x=±6,且y=±1,或x=±2,且y=±3,或x=±3,且y=±2。

12

故原不定方程的通解为

②原方程可变为(x+1)(y-1)-3=0,即(x+1)(y-1)=3.所以有

x+1=±1且y-1=±3,或x+1=±3,且y-1=±1.故得不定方程的全部整数解为 x=0,y=4;x=-2,y=-2;x=2,y=2,x=-4,y=0.

222x?y?z作业:1.写出不定方程的满足x>0,y>0,z>0,(x,y)=1,2 |x的2组正整数解。

2.求不定方程xy-x-y-4=0的全部整数解.

第三章 同 余 §1同余的概念及其性质

1.同余及性质

定义 设m是正整数,称m为模.a,b∈Z,如果a,b被m除所得的余数相同,则称a,b对模m同余,记为a≡b(modm).如果a,b被m除所得的余数不同,则称a,b对模m不同余,记为a?b(modm).

例如 4≡7(mod3),6≡11(mod5),4?5(mod3),6?8(mod5).

定理1 整数a,b对模m同余的充分必要条件是,m|a-b,即a=b+mt,t∈Z. 证明 必要性,若a≡b(modm).可设a=msa=r,b=mua=r,s,u∈Z,则a-b=m(s-u)=mt, T=s-u∈Z.所以m|a-b,且a=b+mt.

充分性,设a=ms+r1,b=mu+r2,a-b=m(s-u)+r1-r2.因m|a-b,所以m|r1-r2,但|r1-r2|

甲:a≡b(modm).

乙:若a≡b(modm),b≡a(modm).

丙:若a≡b(modm),b≡c(modm),则a≡c(modm). 丁、戊:a1?b1(modm),a2?b2(modm),则

a1?a2?b1?b2(modm),

a1a2?bb12(modm)

13

由此可得,若a1?b1(modm),a2?b2(modm),?,ak?bk(modm)则

a1?a2???ak?b1?b2???bk(modm),由此可得定理2. 2.同余的应用 A.3(9)|a的条件

a1a2?ak?bb12?bk(modm).

nn?ia10?a10???a110?a0,0?ai?9,i?1,?,n,an?0.则 nn?1设a=

i因10?1(mod3(9)),i=1,?,n,则a?an?an?1???a1?a0(modm),于是

3(9)|a?是3(9)|an???a1?a0. B.7(11,13)|a的条件

nn?ia1000?a1000???a11000?a0,0?ai?999,i?1,?,n,an?0.因 n?1设a=nn1000i??1(mod7(11,13)),则a?a0?a1???(?1)an(modm),于是 na?a???(?1)an. 01?7(11,13)|a是7(11,13)|

例1 设a=5874192,b=435693,an???a1?a0=5+8+7+4+1+9+2=36,an???a1?a0 =4+3+5+6+9+3=30,所以9|a,3|b.

na?a???(?1)an=693-637=56, 01 例2若a=637693,

7|56,11?56,13?56,所以7|5a,11?a6,13?a. 作业：1.p53:2.

§2 剩余类及完全剩余系

1.模m的剩余类及完全剩余系

设m是正整数,Z是整数集,令Kr={mt+r|t∈Z},r=0,1,?,m-1,则K0,K1,?,Km?1称为模m的剩余类. 易知,?a,b∈Kr,则a≡b(modm).称a为Kr中其它数的剩余. 设ar?Kr,r=0,1,?,m-1,称a0,a1,?,am?1为模m的完全剩余系. 定义 设m是正整数,0,1,?,m-1称为模m的非负最小完全剩余系.

14

m为偶数时,

??mmmmm,??1,?,?1,0,1,?,?1,或-?1,?,?1,0,1,?,22222称为模m的绝对最小完全剩余系；m为奇数

m?1m?1,?,?1,0,1,?,22称为模m的绝对最小完全剩余系. 时,

例1 m=6,模6的剩余类为K0,K1,K2,K3,K4,K5,0,1,2,3,4,5是模6的一个完全剩余系,1,2,3,4,5,6也是模6的一个完全剩余系.-3,-2,-1,0,1,2;-2,-1,0,1,2,3都是模6的完全剩余系,称为模6的绝对最小完全剩余系.

例2 m=5时,0,1,2,3,4;-2，-1,0,1,2分别叫做模5的非负最小完全剩余系和绝对最小完全剩余系. 2.完全剩余系的判定

定理1 m个整数a1,a2,?,am为模m的完全剩余系的充分必要条件为，a1,a2,?,am 对模m两两不同余.

定理2 设m是正整数,(a,m)=1,b∈Z,x1,x2,?,xm是模m的一个完全剩余系,则

ax1?b,ax2?b,?, axm?b是模m的一个完全剩余系.

证明 对j≠i,m?

(xj?xi),因为

axj?b?(axi?b)?a(xj?xi),且(a,m)=1,于是m?

a(xj?xi)全剩余系.

,所以m?

axj?b?(axi?b)axj?baxi?b.?（modm）,i,j=1,2,?,m, j≠i,从而ax1?b,ax2?b,?,axm?b是模m的一个完

例3 ①写出模9的一组完全剩余系,它的每一个数都是偶数; ②写出模9的一组完全剩余系,它的每一个数都是奇数. 作业：1.分别写出模7、模8的非负最小完全剩余系、绝对最小完全剩余系.

3 简化剩余系与欧拉函数

1.简化剩余系、欧拉函数

定义若模m的一个剩余类里的数与m互质,则称这个剩余类为与模m互质的.

对与模m互质的全部剩余类,从每一类里任取一数组成的集合,叫做模m的简化剩余系. m=6时,K1,K5是全部与模m互质的剩余类,1,5是模6的简化剩余系.m=8时, K1,

K3,K5,K7是模8的简化剩余系.

定义设a是正整数,欧拉函数?(a)=0,1,?,a-1中与a互质的整数的个数. 例如?(1)=1,?(2)=1,?(3)=2,?(4)=2,?(5)=4,?(6)=2,?(7)=6. 模m的一个简化剩余系中含有?(m)个数。

15

2.简化剩余系的判定

定理1 模m的剩余类Kr与模m互质的?是?a∈Z,使得(a,m)=1.与模m互质的剩余类的个数是?(m).模m的每一个简化剩余系,是由与m互质的对模m两两不同余的?(m)个整数组成.

定理3设m是正整数,(a,m)=1,x1,x2,?,

x?(m)是模m的一个简化剩余系,则ax1,

ax2,?,ax?(m)是模m的一个简化剩余系.

定理4若m1,m2是互质的两个正整数,x1,x2分别通过模的简化剩余系,则m1x2+

m2x1通过模m1m2的简化剩余系.

推论 若m1,m2是互质的两个正整数,则?(m1m2)??(m1)?(m2).

?k?1?2pp?pk,则 定理5 设正整数a的标准分解式为a=12??1??1??1p(p?1)p(p?1)?p(pk?1)=?(a)1122k =

12ka(1?111)(1?)?(1?)p1p2pk

证明 在数列1,2,?,p-1,p,p+1,?,p+p-1,2p,??,

??1??1??1pppp(-1)+1,?, p(-1)+p-1,p

中与

p互质的整数有p???1???1?(p)?p(p?1).

(p-1)个，即

作业P60:3.

§4欧拉定理 费尔玛定理及其应用 1.欧拉定理 费尔玛定理

?(m)a?1(modm). 定理1(Euler)设a,m∈Z,m>1,(a,m)=1,则

证明取模m的一个简化剩余系b1,b2,?,bs,(s??(m)),由于(a,m)=1,由§3定理3知,ab1,ab2,?,abs也是模m的一个简化剩余系，于是

?(m)(ab1)(ab2)?(abs)?bb?b(modm)abb12s12?bs?bb12?bs(modm),因(m,bi)=1,i= ,即

?(m)b1,b2,?,b?(m)?(m)a?1(modm).证毕。 1,2,?,,所以(m,)=1,从而

P?1Pa?1(modP)a? 推论(费尔玛定理)设P是素数,则,而且a∈Z,?a(modP).

Pa证明 若p |a,则?a?0(modP)，若(a,m)=1，则aP?1?1(modP)，所以

16

aP?a(modP).

P?1q?1q?p?1(modpq). 例1 设p,q是不同的素数,证明

P?1q?1q?p?1(modp), 证明 因p,q是不同的素数,所以(p,q)=1,由费尔玛定理知,

qP?1?pq?1?1(modq).由同余的性质得,qP?1?pq?1?1(modpq).

例2设p≠2,5为素数,整数a的十进制数由p-1位,而且每一位上的数字都是9,证明p |a. 证明因p≠2,5为素数,所以(10,p)=1,由费尔玛定理得,a=99?9=10dp),即p |a.

nb?bx???bx01n例3 若变量x取整数时,多项式P(x)=的值总为整数,则称P(x)

P?1?1≡0(mo

1(x13?x)为整值多项式.证明,2730是整值多项式.

证明 2730=2×3×5×7×13,当x取整数值时,由费尔玛定理,

x13?x?0(mod13),即13|x13?x.

x13?x?(x7?x)(x6?1)?0(mod7),即7|x13?x. x13?x?(x5?x)(x8?x4?1)?0(mod5),即5|x13?x.

x13?x?(x3?x)(x10?x8?x6?x4?x2?1)?0(mod3),即3|x13?x. x13?x?(x2?x)(x11???x?1)?0(mod2),即2|x13?x.

13因2,3,5.7.13两两互质,由整除的性质知,2×3×5×7×13|x?x，即2730|

1(x13?x)13x?x.故2730是整值多项式.

例4 今天是星期一，问从今天起再过101010天是星期几？

22333?6??1(mod7),所以 解 10?3(mod7),10?3?2(mod7), 10?3?2?106?1(mod7)。又因10?-2(mod6), 102?22??2(mod6),故1010??2?4(mod6)。

10106k?4?106k104??3?4(mod7),这就是说，从今天起再过1010天是星期五（1+4）设10?6k?4，k为正整数,于是10?10。

101020112011例5求

2011被8除的余数。

作业:P64:1.例3

17

2.分数与循环小数

定义 如果无限小数0.a1a2?an?（an?{0,1，?,9}）从任何一位数后不全为0,且能找到两个整数s?0,t＞0,使得

as?i?as?i?kt,i=1,2,?,t,k=0,1,2,?. (*)

则称它为循环小数，并简记为0.a1a2?asas?1?as?t.

对满足(*)的最小正整数t,称as?1?as?t为循环节，称t为循环节的长度.若最小的s=0,那小数就叫做纯循环小数，否则叫做混循环小数。

a定理2有理数b,0

t????tt充分性：如果(b,10)=1,由定理1知有一正整数t使得10?1(modb),0

qb?(10?1)a,

t0?q?(10t?1)a?10t?1b.

t?1t?2a10?a10???10at?1?at,显然a1,a2,?,at不全为9,也不全为0.而且 12令q=

qaq1a1aa1a???0.aa?a?0.aa?a??t12t12t0.a1a2?at,又由10a?qb?a得b10t10tb=10t10tb，反复利用b10tb 即得a??aa?aa?a?b=0.12t1t=0.a1?at.

aa??5b1,?,?不全为0,(b1,10)=1,b1?1,则b能表成纯循环小数.其中不循环部分的位数是定理3有理数b,0

18

四章 同余方程

§1基本的概念及一次同余方程

1.同余方程的概念

na?ax???ax01n定义 设f(x)=,这里ai?Z,i=0,1,?,n.m是正整数,则称 na?ax???ax?0(modm). (1) 01n f(x)=

为同余式,或模m的同余方程.

若an?0(modm),n称为同余方程(1)的次数.若a∈Z而且f(a)≡0(modm),则称 x≡a(modm)为同余方程(1)的解.

2例1 f(x)=x?x?3≡0(mod5)是模5的2次同余方程,由于f(1)=5≡0(mod5),因此

x≡1(mod5)是同余方程的一个解.另外x x=m1t?x0，m1?m/d, t=0,±1,±2,?, (mod5)也是同余方程的一个解. 2一次同余方程

一次同余方程的一般形式：ax≡b(modm),a?0(modm) (2) 例如 2x≡3(mod5), 4x≡8(mod7), 3x≡9(mod11),

定理1 同余方程(2)有解的充分必要条件是,(a,m)|b.而且当(2)有解时,(2)对模m来说有(a,m)个解. 证明 (2)有解的充分必要条件是ax-my=b有整数解,充分必要条件是(a,m)|b.

设d=(a,m),如果(2)有解,则满足(2)的一切整数可以写成x=m1t?x0,m1?tm/d, t=0,±1,±2,?,但对模m来说,这些整数可以写成x≡m1t?x0(modm),t=0,1,2,?,d-1. 而它们关于模m 两两不同余.

例2 解一次同余方程2x+6≡0 (mod4),

解 因(2,4)|6,由定理1,同余方程有(2,4)=2个整数解.设2x-4y=-6,则x-2y=-3,由此可得x=-1+2t,t∈Z,所以同余方程的结为x≡-1+2t(mod4),t=0,1.即x≡-1(mod4) x≡1(mod4).

例3 解一次同余方程12x+4≡0 (mod8),

因(12,8)=4,4|4,由定理1,同余方程有4个整数解.设12x-8y=-4,则3x-2y=-1,由此可得x=-1+2t,t∈Z,所以同余方程的结为x≡-1+2t(mod4),t=0,1,2,3. 即x≡-1,1,3 5(mod8).

19

例4 解一次同余方程15x+6≡0 (mod9),

作业:1 解一次同余方程:12x-6≡0(mod9).

§2 孙子定理

中国古代的《孙子算经》中有物不知数：

今有物不知数,三三数之剩二，五五数之剩三,七七数之剩二,问物几何？答曰二十三. 设物的数量为x,则x≡2(mod3),x≡3(mod3),x≡2(mod7).求满足此条件的整数x. 这个同余方程可推广为

x≡b1(modm1), x≡b2(modm2),?,x≡bk(modmk). (1) 这里m1,m2,?,mk为两两互质的正整数.

定理 设m1,m2,?,mk为两两互质的正整数,m=m1m2?mk=miMi.i=1,2,?,k.则同余方程(1)的解为

???x≡M1M1b1?M2M2b2???MkMkbk(modm).

?这里MiMi?1(modmi),i=1,2,?,k.

例1 解同余方程x≡b1(mod5),x≡b2(mod6),x≡b3(mod7),x≡b4(mod11).

?解m=2310=5·6·7·11=5·462=6·385=7·330=11·210.解MiMi?1(modmi), i=1,2, ????3,4得,M1?3,M2?1,M3?1,M4?1.故原同余式组的解为

x=3·426b1+385b2+330b3+210b4(mod2310).

例2 韩信点兵:有兵一队,若列成五行纵队,则末行一人,若列成六行纵队,则末行五人, 若列成七行纵队,则末行四人, 若列成十一行纵队,则末行十人,求兵数.

解 此时b1?1,b2?5,b3?4,b4?10,由例1即得

x=3·426·1+385·5+330·4+210·10=6730≡2111(mod2310). 例3 解同余方程组x≡2(mod3),x≡3(mod3),x≡2(mod7).

??解 105=3×5×7=3×35=5×21=7×15.由35M1?1(mod3),21M2?1(mod5),15 ???1??M3(mod7)得M1??1,M2?1,M3?1.所以原同余方程组的解为

x=35·(-1)·2+1·21·3+1·15·2=23(mod105).

作业P79:1(i).

20

本文来源：https://www.bwwdw.com/article/fkkt.html