信息学奥赛初赛真题解析.pptx

第1节第2节第3节第4节第5节第6节第7节第8节

《信息学奥赛一本通·初赛真题解析》

第三章数学问题

第1节第2节第3节第4节第5节第6节第7节第8节

《信息学奥赛一本通·初赛真题解析》

五、最大公约数与最小公倍数

目录

01整数性质

1.带余除法，即欧几里德除法

设a，b为整数，b≠0，则存在整数q和r，使得a=bq+r，其中0rb，并且q

和r由上述条件唯一确定；整数q被称为a被b除得的(不完全)商，数r称为a被b除得的余数。

注意：r共有|b|种可能的取值：0，1，ⅆ,|b|−1。若r=0，即为a被b整除的情形，

的基本手法是将a分解为b与一个整数之积。

带余除法的核心是关于余数r的不等式：

0rb

因此，证明

b|a

。

01整数性质

2.任何一个正整数n，都可以写成n=2l的形式，其中m为非负整数，l为奇数。

m

3.若a=Z，a1，则a的除1以外的最小正因数q是一个质（素）数，如果q≠a，则q。

推论：如果不超过a的所有质数均不是a的约数，则a必为质数。

01整数性质

4.算术基本定理(素数唯一分解定理)任何一个大于1的正整数a，能唯一地表示成质（素）

因数的乘积（不计较因数的排列顺序）

（pipj(ij)），aiN+，i=1，2，ⅆ,k。上式叫做整数a的标准分解式。

推论1：若a的标准分解式是（1）式，则d是a的正因数的充要条件是：

d=ppp,0βiai，i=1，2，ⅆ,k。（2）

k

βk

2

β2

1

β1

任何大于1的整数a能唯一地写成

（1）的形式，其中

a=p1p2

2

a

1

a

为素数

pk

k

a

pi

推论2：设a=bc，且(b，c)=1，若a是整数的k（k≥2）次方，则b，c也是整数的k

次方。特别地，若a是整数的平方，则b，c也是整数的平方。

一般地，设正整数a，b，ⅆ,c之积是一个正整数的k次方幂（k≥2），若a，b，ⅆ,c

两两互素，则a，b，ⅆ,c都是正整数的k次方幂。

01整数性质

应注意（2）不能称为是d的标准分解式，其原因是其中的某些βi可能取零值（当d

不含某个素因数pi时，βi=0）。

02整除

（一）常见数字的整除判定方法

1.一个数的末位能被2或5整除，这个数就能被2或5整除;一个数的末两位能被4或

25整除，这个数就能被4或25整除;一个数的末三位能被8或125整除，这个数就能被8或125整除。

2.一个数各位数字和能被3整除，这个数就能被3整除;一个数各位数字和能被9整除，

这个数就能被9整除。

3.如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么

这个数能被11整除。

02整除

4.如果一个整数的末三位与末三位以前的数字组成的数之差能被7、11或13整除，那

么这个数能被7、11或13整除。

5.如果一个数能被99整除，这个数从后两位开始两位一截所得的所有数(如果有偶数

位，则拆出的数都是两位数;如果是奇数位，则拆出的数中有若干个两位数，还有一个是一位数)的和是99的倍数，这个数一定是99的倍数。

02整除

（二）整除的性质

1.性质1如果数a和数b都能被数c整除，那么它们的和或差也能被c整除。

2.性质2如果数a能被数b整除，b又能被数c整除,那么a也能被c整除。3.性质3如果数a能被数b与数c的积整除，那么a也能被b或c整除。

02整除

（二）整除的性质

4.性质4如果数a能被数b整除，也能被数c整除，且数b和数c互质，那么a一定

能被b与c的乘积整除。

例如:如果3|12,4|12，且(3,4)=1,那么(3x4)|12。

5.性质5如果数a能被数b整除，那么am也能被bm整除。

6.性质6如果数a能被数b整除，且数c能被数d整除，那么ac也能被bd整除。

03