1、第一讲 整除性理论及其应用一. 基本概念和性质.1. 整除:设 a,b 是两个整数,且 b 0,如果存在一个整数 q,使等式 a=bq 成立,那么我们称 a 能被 b 整除或 b 整除 a,记作 ba, 其性质有( 设 b 0,c=0)1).若 ba , a 0,则 2) 若 ba, ab ,a 0,则 a=b 或 b=a3) 若 c b, ba, 则 ca4) 若 ba, 则 cbca5) 若 c a, cb,则 cma+nb,m,n Z2. 整除的基本定理:对于任意整数 a,b(b 0,),存在唯一的一对整数 q,r,使得 a=qb+r,0 rb其中,q 和 r 分别称为 b 除 a 的商
2、和余数.3. 最大公约数和最小公倍数: a,b 的最小公倍数记为a,b,a,b 的最大公约数记为(a,b) ,其性质有:1).设 m 为正整数,则(am,bm)=m(a,b) am,bm=ma,b2)设 a,b 是两个正整数,则(a,b)a,b=ab3)设 a,b,c 是三个正整数,则(ab,bd,ac)a,b,c=abc4)设正整数 k 是整数 a,b 的公倍数,则(k/a,k/b)=k/a,b5)设正整数 c 是 a,b 的公约数,则(a/c,b/c)=(a,b)/c6)若(a,b)=1, (ab,c)=(a,c)(b,c)7)若 a1, a2, an,是 n 个不全为零的整数 ,则(a
3、1, a2, an)=( (a1, a2, ak), (ak+1, ak+2, an)4. 两个定理: 1) 欧拉函数: 设整数 n 2,n= , , ,是 n 的质因数分解式，以 （n）表1p2m示小于 n 且与 n 互质的自然数的个数，则 （n）=121()()mpp2)勒让得定理:在乘积 n！中，质因数 p 的指数为 p(n!)=231mp二. 例题选讲.1. 设 ,求证： f(n)2,()(526)nNfnn102. 设 p 为奇质数,证明: 的分子 a 是 p 的倍数13pb3 p,q 均为正整数,使得 1124389pq试证:1979p4 求同时满足下列条件的一组整数 a，b1）a
4、b（a+b）不能被 7 整除2） 能被 7 整除。7()ab5. 是否存在 1000000 个连续整数，使得每一个都含有重复的质因子，即都能被某个质数的平方所整除。6设 ，则,abN21ab7设 a,b,c 为整数，且满足 ，试证：当（a,b.c ）=1 时，a+b，a-c，b-c 均是c完全平方数。8给定正整数 a,b,c，定义函数 (,),fxyzabxczyZ试求： 的最小正整数的值。(,)fxyz9求 1988！中 6 的最高幂。10将与 105 互质的所有的正整数从小到大排列，试求出这个数列的第 1000 项。三练习题。1 试证：对于任意不小于 2 的整数 n， 不是整数。123An
5、2 对于正整数 n 与 k，定义： ，求证： 1(,)krF(,1)F(,)k3 数列 满足： ，其中0,1na 0111,2nnaa2 是给定的质数，求满足下列两条件的 a 的最小值：0NP1）若 p 是质数，且 p ，则 能被 p 整除02）若 p 是质数，且 p ，则 不能被 p 整除。a4 若 n 是大于 1 的自然数，它有 r 个不同的质因数，则 ()2rn5 设 且 n ，则 n,abNabnab6 设正整数 a 与 b，使得 ab+1 整除 ，求证： 是某一个正整数的平方。2217 已知：n 个正整数 满足 2n，其中任意两个(1)in1a2 na的最小公倍数都大于 2n，求证： ,()ijaia23n
