2019-2020年高中数学竞赛教案讲义（17）整数问题

2019-2020年高中数学竞赛教案讲义（17）整数问题一、常用定义定理1．整除：设a,b∈Z,a≠0，如果存在q∈Z使得b=aq，那么称b可被a整除，记作a|b，且称b是a的倍数,a是b的约数。b不

2019-2020年高中数学竞赛教案讲义（17）整数问题 一、常用定义定理 1．整除：设a,b∈Z,a≠0，如果存在q∈Z使得b=aq，那么称b可被a整除，记作a|b，且称 b是a的倍数,a是b的约数。b不能被a整除，记作ab. 2带余数除法：设a,b是两个给定的整数，a≠0，那么，一定存在唯一一对整数q与r，满 足b=aq+r,0≤r<|a|，当r=0时a|b。 3．辗转相除法：设u,u是给定的两个整数，u≠0，uu,由2可得下面k+1个等式： 01110 u=qu+u,0<u<|u|； 001221 u=qu+u,0<u<u； 112332 u=qu+u,0<u<u； 223443 … u=qu+u+u,0<u<u； k-2k-21k-1kkk-1 u=qu,0<u<u； k-1k-1k+1k+1k u=qu. kkk+1 4．由3可得：（1）u=(u,u)；（2）d|u且d|u的充要条件是d|u；（3）存在整数x k+10101k+1 ,x，使u=xu+xu. 01k+10011 5．算术基本定理：若n>1且n为整数，则，其中p(j=1,2,…,k)是质数（或称素数），且在 j 不计次序的意义下，表示是唯一的。 6．同余：设m≠0,若m|(a-b)，即a-b=km，则称a与b模同m同余，记为a≡b(modm)，也称 b是a对模m的剩余。 7．完全剩余系：一组数y,y,…,y满足：对任意整数a有且仅有一个y是a对模m的剩余， 12sj 即a≡y(modm)，则y,y,…,y称为模m的完全剩余系。 j12s p-1 8．Fermat小定理：若p为素数，p>a,(a,p)=1，则a≡1(modp)，且对任意整数a,有 p a≡a(modp). 9．若(a,m)=1，则≡1(modm),(m)称欧拉函数。 10．（欧拉函数值的计算公式）若，则(m)= 11．（孙子定理）设m,m,…,m是k个两两互质的正整数，则同余组： 12k x≡b(modm),x≡b(modm),…,x≡b(modm)有唯一解， 1122kk x≡Mb+Mb+…+Mb(modM)， 1122kk 其中M=mmm；=，i=1,2,…,k；≡1(modm),i=1,2,…,k. 12ki 二、方法与例题 1．奇偶分析法。 例1有n个整数，它们的和为0，乘积为n，（n>1），求证：4|n。 2．不等分析法。 333222 例2试求所有的正整数n，使方程x+y+z=nxyz有正整数解。