2016年寒假高中数学联赛预习材料数论

清北学堂培训课程预习材料清北学堂培训课程预习材料 PAGE13PAGE13 4、定 6、函 1、 相除法，函数并对进位制有一定了解。称b为a的约数。c|a，c|bca，bda，b的公因数，d≥0d则称a，b互素。除法。又称得算法。m是正整数，则m是整数，a|m,b|m，则若a| b|c，则a|cab|pp|abp|ap|bnnnnabmabm若b|ac，且(b,c)=1，则b|a14）若(a,b)=1，则(ac,b)=(c,b)NP1P2...Pn,Pi是正整数。这样的分解称为N 1的正整数N，如果它的标准分解式为：NP1P2...Pn (1+Pn+.并证明ab=(a,b)[a,b].a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。101rr自然数N的r进制是把N表示成r的n次多项式的形式。r进制记数法的基本原则是“逢r进不同进位制的数可以利用辗转相除法相互转换。十进制数转换成P进制数是“除P取余”法，aba进制数转换为十进制数，再由十进制数转换为b进制数。记函数为[],[x]表示不超过x的最大整数，{x}=x-[x],即x的小数部分。要特别注意当x为负数时的情况。函数常常与不等式结合使用是不减函数。……等价定义：（1）m|a−ba,bm同余一类均称为模m的剩余类（又叫同余类。同一类中任一数称为该类中另一数的剩余。剩余类Kr是数集Kr={qm+r}（m是模，r是余数，q∈Z，也即Kra|a∈Z,a≡rmodm)}，它是一个公差为m的（双边无穷）等差数列。完全剩余系：设是模m的（全部）剩余类，从每个Kr中任取一个数Arm个数组成一个组称为模m的一个完全剩余系，简称完系。然数,则称集合{A1,A2,...,Am}为模n的一个简化剩余系，简称缩系,a≡amod5）同余式相乘若a≡b(modm)，c≡d(modm)ac≡bd(modm)6）幂运算如果a≡b(modm)a^n≡b^n(modm)若abmodm)，n|m,abmodabmodmi)i=1,2...n)abmodm1,m2,...mn])其中[m1,m2,...mn]表示m1,m2,...，mn的最小公倍数m是素数，φ(m)=m-1;mP1P2...Pn，则φ(m)=m(1- 1-1)..(1-1ppp ppp 费马小定理：若pa^pa(modp)ap-11(modMii≡1(mod

(mod设f(x)axn xn1...a为x的整系数多项 解定义：x≡b(modmma定理：若(a,m)=d>1d|bax≡b(modm)d个解,若x(modm1)x≡r(modm)d个解为：xr+km(modm)，k=0,1...,d-1其中=a=bmm ax≡b(modm),(a,m)=11(a,m)1s,t,as+mt1as≡1(modm)解法2：原方程变形为x≡b/a(modm)(b/a仅只是形式上的记号)，然后用与m互质的数陆续乘右端的分子分母，直至把分母绝对值变成1（通过分子分母各对模m取余数）定义：若数rnfk(x0(modmk)，k=1,2...nr定理：对同余方程组xc1(modm1)若dc1−c2d|c1−c2，则此同余方程组有对模M的一类剩余解。定理：p为素数，，同余方程组xc(modp xc(modpxc(modp的解（即有解时等价 1xa(modp11xa(modpnn若(a，m）＝1，x2a（modm）有解，则称a为模m的二次剩余（或平方剩余则，称a为模m二次非剩余（或平方非剩余）

2≡-1（modp)q:(p

2（modp）=1或- q

p）=（- （1、（1）2：若(a,b)1,x0y0为ax+by+c=0,(a>b,b≠0)之一解，则其全部解为xx0bty=y0−at(t∈Z)（2）（pell）方数，d0c≠0.Ax2BxyCy2DxEyF0.特别的，x2dy2=1称 x+y最小的解，则方程的全部正整数解为(x1+y1)n=xn+yxn=2x1xn-1-xn-2yn2x1yn-1-yn-定理3：对于x2dy2=c,若存在一组解（x0,y0且x2dy2=1的解为(x1,y1)，则全部正整数解为（x0 dy0）(x1+y1)n=xn+ynx2y2zx2y2z2满足(x,y)=1,z|y的全部正整数解(x,y,z)x=a2-b2,y=2ab,z=a2+b2，其中，a,ba>b>0,a,b一奇一偶，且(a,b)=1的任意整数。1P1mod4)，则p 4：形如4M（8K+7）的正整数不可表示为3个整数平方之和48140是0，1，4，7xy=设(x,z)=ax=ac,z=ad，其中(c,d)=1acy=adtcy=dt，因(c,d)=1d|y，设y=bd，则t=bc，因此方程xy=zt的正整数解可以表示为利用方程两边关于模mm=2时，由Euler定理，恒有m(a)(m)。abmodm)，(am)1，则显然有m(a)m(b)。定义2：若m(a)=(m)，则称a是模m的原根。定理 记=m(a)，则a0,a1,,a1对模m两两不同余定理2 设=m(a)，r与r是正整数则arar(modm)的充要条件是rr(mod)。特别地，ar1(modm)的充要条件是r。推论m(a)(m)定理 设k是非负整数，(ak m (m(a),k推论若m(a)kl，k0，l0，则m(ak)l定理 等式m(ab)=m(a)m(b)与(m(a),m(b))=1是