高中数学竞赛教案讲义(17)整数问题.docx

高中数学竞赛教案讲义(17)整数问题 第十七章 整数问题 一、常用定义定理 1．整除：设a,b ∈Z,a ≠0，如果存在q ∈Z 使得b=aq ，那么称b 可被a 整除，记作a|b ，且称b 是a 的倍数,a 是b 的约数b 不能被a 整除，记作a b. 2 带余数除法：设a,b 是两个给定的整数，a ≠0，那么，一定存在唯一一对整数q 与r ，满足b=aq+r,0≤r1且n 为整数，则k a k a a p p p n 2121 ，其中p j (j=1,2,…,k)是质数（或称素数），且在不计次序的意义下，表示是唯一的 6．同余：设m ≠0,若m|(a-b)，即a-b=km ，则称a 与b 模同m 同余，记为a ≡b(modm)，也称b 是a 对模m 的剩余 7．完全剩余系：一组数y 1,y 2,…,y s 满足：对任意整数a 有且仅有一个y j 是a 对模m 的剩余，即a ≡y j (modm)，则y 1,y 2,…,y s 称为模m 的完全剩余系。

8．Fermat 小定理：若p 为素数，p>a,(a,p)=1，则a p-1≡1(modp)，且对任意整数a,有a p ≡a(modp). 9．若(a,m)=1，则)(m a ≡1(modm), (m)称欧拉函数 10．（欧拉函数值的计算公式）若k a k a a p p p m 2121 ，则 (m)=.)11(1 k i i p m 11．（孙子定理）设m 1,m 2,…,m k 是k 个两两互质的正整数，则同余组： x ≡b 1(modm 1),x ≡b 2(modm 2),…,x ≡b k (modm k )有唯一解， x ≡'1M M 1b 1+'2M M 2b 2+…+'k M M k b k (modM)， 其中M=m 1m 2m k ；i M =i m M ，i=1,2,…,k ；i i M M '≡1(modm i ),i=1,2,…,k. 二、方法与例题 1．奇偶分析法 例1 有n 个整数，它们的和为0，乘积为n ，（n>1），求证：4|n 2．不等分析法 例2 试求所有的正整数n ，使方程x 3+y 3+z 3=nx 2y 2z 2有正整数解。

第十七章 整数问题 一、常用定义定理 1．整除：设a,b ∈Z,a ≠0，如果存在q ∈Z 使得b=aq ，那么称b 可被a 整除，记作a|b ，且称b 是a 的倍数,a 是b 的约数b 不能被a 整除，记作a b. 2 带余数除法：设a,b 是两个给定的整数，a ≠0，那么，一定存在唯一一对整数q 与r ，满足b=aq+r,0≤r1且n 为整数，则k a k a a p p p n 2121 ，其中p j (j=1,2,…,k)是质数（或称素数），且在不计次序的意义下，表示是唯一的 6．同余：设m ≠0,若m|(a-b)，即a-b=km ，则称a 与b 模同m 同余，记为a ≡b(modm)，也称b 是a 对模m 的剩余 7．完全剩余系：一组数y 1,y 2,…,y s 满足：对任意整数a 有且仅有一个y j 是a 对模m 的剩余，即a ≡y j (modm)，则y 1,y 2,…,y s 称为模m 的完全剩余系 8．Fermat 小定理：若p 为素数，p>a,(a,p)=1，则a p-1≡1(modp)，且对任意整数a,有a p ≡a(modp). 9．若(a,m)=1，则)(m a ≡1(modm), (m)称欧拉函数。

10．（欧拉函数值的计算公式）若k a k a a p p p m 2121 ，则 (m)=.)11(1 k i i p m 11．（孙子定理）设m 1,m 2,…,m k 是k 个两两互质的正整数，则同余组： x ≡b 1(modm 1),x ≡b 2(modm 2),…,x ≡b k (modm k )有唯一解， x ≡'1M M 1b 1+'2M M 2b 2+…+'k M M k b k (modM)， 其中M=m 1m 2m k ；i M =i m M ，i=1,2,…,k ；i i M M '≡1(modm i ),i=1,2,…,k. 二、方法与例题 1．奇偶分析法 例1 有n 个整数，它们的和为0，乘积为n ，（n>1），求证：4|n 2．不等分析法 例2 试求所有的正整数n ，使方程x 3+y 3+z 3=nx 2y 2z 2有正整数解。