2019-2020年高中数学竞赛辅导资料《整除》

2019-2020年高中数学竞赛辅导资料《整除》

整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、最大公约数、最小公倍数、方幂问题.

Ⅰ. 整数的整除性

初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即，如是整除，，则不一定是整数. 由此引出初等数论中第一个基本概念：整数的整除性.

定义一：（带余除法）对于任一整数和任一整数，必有惟一的一对整数，使得，，并且整数和由上述条件惟一确定，则称为除的不完全商，称为除的余数.

若，则称整除，或被整除，或称的倍数，或称的约数（又叫因子），记为.否则，| . 任何的非的约数，叫做的真约数.

0是任何整数的倍数，1是任何整数的约数.

任一非零的整数是其本身的约数，也是其本身的倍数. 由整除的定义，不难得出整除的如下性质： （1）若

（2）若a|bi,则a|?cb,其中ciii?1ni?Z,i?1,2,?,n.

（3）若，则反之，亦成立. （4）若.因此，若. （5）、互质，若

（6）为质数，若则必能整除中的某一个. 特别地，若为质数，

（7）如在等式中除开某一项外，其余各项都是的倍数，则这一项也是的倍数. （8）n个连续整数中有且只有一个是n的倍数. （9）任何n个连续整数之积一定是n的倍数.

本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算术基本定理，我们就可以讨论整数的约数的个数了.

Ⅱ. 最大公约数和最小公倍数

定义二：设、是两个不全为0的整数.若整数c满足：，则称的公约数，的所有公约数中的最大者称为的最大公约数，记为.如果=1，则称互质或互素.

定义三：如果、的倍数，则称、的公倍数. 的公倍数中最小的正数称为的最小公倍数，记为.

最大公约数和最小公倍数的概念可以推广到有限多个整数的情形，并用表示的最大公约数，表示的最小公倍数.

若，则称互质，若中任何两个都互质，则称它们是两两互质的.注意，n个整数互质与n个整数两两互质是不同的概念，前者成立时后者不一定成立（例如，3，15，8互质，但不两两互质）；显然后者成立时，前者必成立.

因为任何正数都不是0的倍数，所以在讨论最小公倍数时，一般都假定这些整数不为0.同时，由于有相同的公约数，且（有限多个亦成立），因此，我们总限于在自然数集合内来讨论数的最大公约数和最小公倍数.

Ⅲ.方幂问题

一个正整数能否表成个整数的次方和的问题称为方幂和问题.特别地，当时称为次方问题，当时，称为平方和问题. 能表为某整数的平方的数称为完全平方数.简称平方数，关于平方数，明显有如下一些简单的性质和结论： （1）平方数的个位数字只可能是0，1，4，5，6，9. （2）偶数的平方数是4的倍数，奇数的平方数被8除余1，即任何平方数被4除的余数只能是0或1. （3）奇数平方的十位数字是偶数. （4）十位数字是奇数的平方数的个位数一定是6. （5）不能被3整除的数的平方被3除余1，能被3整除的数的平方能被3整除.因而，平方数被9除的余数为0，1，4，7，且此平方数的各位数字的和被9除的余数也只能为0，1，4，7. （6）平方数的约数的个数为奇数. （7）任何四个连续整数的乘积加1，必定是一个平方数.

例题讲解

1．证明：对于任何自然数和，数f(n,k)?2n整数之积.

2．设和均为自然数,使得

3k?4nk?10都不能分解成若干个连续的正

p1111?1??????.证明：可被1979整除. q23131813193．对于整数与，定义求证：可整除

4．求一对整数，满足：(1)不能被7整除；（2）能被7整除.

7

5．求设和是两个正整数，为大于或等于3的质数，），试证：（1）；（2）或

6．盒子中各若干个球，每一次在其中个盒中加一球.求证：不论开始的分布情况如何，总可按上述方法进行有限次加球后使各盒中球数相等的充要条件是

7．求所有这样的自然数，使得是一个自然数的平方.

课后练习

1． 选择题

（1）若数n=20·30·40·50·60·70·80·90·100·110·120·130，则不是n的因数的最小质数是（ ）.

（A）19 （B）17 （C）13 （D）非上述答案

（2）在整数0、1、2…、8、9中质数有x个，偶数有y个，完全平方数有z个，则x+y+z等于（ ）.

（A）14 （B）13 （C）12 （D）11 （E）10 （3）可除尽3+5的最小整数是（ ）.

（A）2 （B）3 （C）5 （D）3+5（E）以上都不是 2． 填空题

（1）把100000表示为两个整数的乘积，使其中没有一个是10的整倍数的表达式为__________.

(2)一个自然数与3的和是5的倍数,与3的差是6的倍数,这样的自然数中最小的是_________.

(3)在十进制中,各位数码是0或1,并且能被225整除的最小自然数是________. 3.求使为整数的最小自然数a的值.

4.证明:对一切整数n,n+2n+12不是121的倍数.

5.设是一个四位正整数,已知三位正整数与246的和是一位正整数d的111倍,又是18的倍数.求出这个四位数,并写出推理运算过程. 6.能否有正整数m、n满足方程m+1954=n.

7.证明：（1）133|（11+12），其中n为非负整数.

(2)若将(1)中的11改为任意一个正整数a,则(1)中的12,133将作何改动?证明改动后的结论.

n+2

n+1

2

2

2

11

18

11

18

8.设a、b、c是三个互不相等的正整数.求证:在ab-ab,bc-bc,ca-ca三个数中,至少有一个能被10整除.

333333

9. 100个正整数之和为101101,则它们的最大公约数的最大可能值是多少?证明你的结论.

课后练习答案

１．Ｂ．Ｂ．Ａ

２．（１）２·５．（２）２７． ３．由2000a为一整数平方可推出a=5．

４．反证法．若是１２１的倍数，设ｎ＋２ｎ＋１２＝１２１ｋ（ｎ＋１）＝１

２

１（１１ｋ－１）．∵１１是素数且除尽（＋１），

∴１１除尽ｎ＋１１１除尽（ｎ＋１）或１１｜１１ｋ－１，不可能． ５．由是ｄ的１１１倍，可能是１９８，３０９，４２０，５３１，６４２，７５３；又是１８的倍数，∴只能是１９８．而１９８＋２４６＝４４４，∴ｄ＝４，是１９８４．

７．（１）１１＋１２＝１２１×１１＋１２×１４４＝１２１×１１

ｎｎｎｎ

＋１２×１１－１２×１１＋１２×１４４＝…＝１３３×１１＋１２×（１

ｎｎｎｎ

４４－１１）．第一项可被１３３整除．又１４４－１１｜１４４－１１，∴

ｎ＋２２ｎ＋１

１３３｜１１＋１２． （２）１１改为ａ．１２改为ａ＋１，１３３改为ａ（ａ＋１）＋１．改动后命题

ｎ＋２２ｎ＋１

为ａ（ａ＋１）＋１｜ａ＋（ａ＋１），可仿上证明． ８．∵ａｂ－ａｂ＝ａｂ（ａ－ｂ）；同理有ｂ（ｂ－ｃ）；ｃａ（ｃ－２

ａ）．若ａ

、ｂ、ｃ中有偶数或均为奇数，以上三数总能被２整除．又∵在ａ、ｂ、ｃ中若有

２２２

一个是５的倍数，则题中结论必成立．若均不能被５整除，则ａ，ｂ，ｃ个位数

２２２２２２

只能是１，４，６，９，从而ａ－ｂ，ｂ－ｃ，ｃ－ａ的个位数是从１，４，６，９中，任取三个两两之差，其中必有０或±５，故题中三式表示的数至少有一个被５整除，又２、５互质．

９．设１００个正整数为ａ１，ａ２，…，ａ１００，最大公约数为ｄ，并令

则ａ１＋ａ２＋…＋ａ１００＝ｄ（ａ１′＋ａ２′＋…＋ａ′１００）＝１０１１０１＝１０１×

３

３

２

２

２

２

２

ｎ＋２

２ｎ＋１

ｎ

ｎ

ｎ

２

２２

２

５

５

１００１，故知ａ１′，ａ２′，ａ′１００不可能都是１，从而ａ′１＋ａ′２＋…＋ａ′１００≥１×９９＋２＝１０１，ｄ≤１００１；若取ａ１＝ａ２＝ａ９９＝１００１，ａ１００＝２００２，则满足ａ１＋ａ２＋…＋ａ１００＝１００１×１０１＝１０１１０１，且ｄ＝１００１，故ｄ的最大可能值为１００１

例题答案：

1. 证明：由性质9知，只需证明数不能被一个很小的自然数整除.因

f(n,k)?3n3k?3nk?n3k?nk?10?3(n3k?nk?3)?nk(nk?1)(nk?1)?1,

3|3(n3k?nk?3),3|nk(nk?1)(nk?1),3 1，故3 ，因而不能分解成三个或三个以上

的连续自然数的积. 再证不能分解成两个连续正整数的积. 由上知，，因而只需证方程：无正整数解.而这一点可分别具体验算时，均不是形的数来说明. 故对任何正整数、都不能分解成若干个连续正整数之积. 2. 证明：

p111111?(1????)?2(????) q23131924131811111????)?(1????) 2313192659111111=(?)?(?)???(?) 66013196611318989990111=1979×(????)

660?1319661?1318989?990=(1? 两端同乘以1319！得1319！ 此式说明1979|1319！×由于1979为质数，且1979 1319！，

故1979| 【评述】把1979换成形如的质数，1319换成，命题仍成立.

牛顿二项式定理和(a?b)|a?b,(a?b)|a?b(n为偶数), 为奇数)在整除问题中

nnnn经常用到.

3.证明：当时，F(2m,1)?m?r?m(2m?1),

r?12m

F(2m,k)??rr?12k?1?r?m?1?rm2m2k?1

??rr?1mm2k?1??(2m?1?r)2k?1r?1

??[r2k?1?(2m?1?r)2k?1],r?1 由于[…]能被整除，所以能被整除，另一方面，

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