数学特训数论一导学

ab是给定的数，b0cabc则称b整除ab|a，并称ba的一个约数(因子)，称a是b的一个倍数，如果不存在上述c，则称b不能整除a记作b|a.若b|c且c|a，则b|a(传递性质n若b|a且b|c，则b|ac即为某一整数倍数的整数之集关于加、减运算封闭.若反复运用这一性质，b|a及b|c，则对于任意的整数u,v有b|(aucv).更一般，若na1a2an都是b的倍数，则b|a1a2an.或着a|bi，则a|cibiciZ,i1,2,,n若b|a，则或者a0，或者|a||b|，因此若b|a且a|babab互质，若a|cb|c，则ab|cp|anp|a；(6)(带余除法)abb0，则存在整数qr，使得abqr0rbqrq被称为a被b除得的(不完全)r称a被b除得的余数.r共有b种可能的取值：0,1，……b1.若r0，即为a被b，带余除法中的商实际上为a（不超过a的最大整数而带余除法 是 于余数r0rb.证明b|a的基本手法是将a分解为b与一个整数之积，在较12.nxnyn(xy)(xn1xn2yxyn2yn1nxnynxy)(xn1xn2yxyn2yn1（在上式中用y

knn奇数奇数=偶数，偶数偶数＝偶数，奇数偶数＝奇数，偶数偶数＝偶数，奇数偶数＝偶数，奇数奇数＝奇数；即任意多个偶数的和、差、积仍为偶数，奇数个奇任何一个正整数n，都可以写成n2ml的形式，其中ml为奇数4814除的余01；33133整除.因而，0,14,7设正整数ab之积是一个正整数的k次方幂（k2（ab）＝1，则ab都是整数的k次方幂.一般地，设正整数ab,c之积是一个正整数的k次方幂（k2ab,c两两互素，则ab,ck次方幂整数a的个位数也称为整数a的尾数，并记为G(aG(a也称为尾数函数，尾数函数（1）G(G(a))G(a)（2）G(a1a2an)＝G[G(a1)G(a2)G(an)]（4）G(10a)0；G(10ab)G(b)若ab10c，则G(a)G(bG(a4k)G(a4),a,kNG(a4kr)G(ar),k0,0r4,a,k,rNbb2 bb2G(a

)G(a4)G(ab

当bb同为奇数时 2（5）2（5）整除，否则8（125）8（125）整除11整除，否则不能同余的概念是Gauss在1800年左右给出的.设m是正整数若用m去除整数a,b所得的余数相同，则称为a与b关m同余，记作ab(modm)，否则，称为a与bm不同余.

同余设m0m|ab)a和b对模mab(modm若不然，则称a和b对模m不同余，记作10001(mod7等等

b(modm.344(mod15当0bmab(modm，则称b是a对模m的最小非负剩余a和b对模m同余的充要条件是a与b被m除得的余数相同.对于固定的模mm的同余式与通常的等式有许多类似的性质：

ab(modm的充要条件是abmt,tZ也即m|(ab)（1（（2（对称性）若ab(modm，则ba(modm（3（传递性）若ab(modmbc(modm，则ac(modm（4（同余式相加）若ab(modmcd(modm，则acbd(modm（5（同余式相乘）若ab(modmcd(modmacbd(modm（4（5式.（5）ab(modm，kc为整数且k0akcbkc(modm；但是同余式的消去律一般并不成立，即从acbc(modm)未必能推出ab(modm)，可

若acbc(modm，则ab

，由此可以推出，若(cm)1(m,c)ab(modm，即在c与m互素时，可以在原同余式两边约去c而不改变模（这一点再若ab(modmd｜m，则ab(modd若ab(modmd0dadb(moddm

),

21k,i，则aibi(modmaibi

4.f(xab(modm

f(a)

使计算大大地简化.3. 2.设(am)1dad1(modm成立的最小正整，则称d为a对模m 阶在取定某数m后，按照同余关系把彼此同余的整数归为一类，这些数称为模m不相同，这样我们就把全体整数按照模m划分为了m个剩余类：Kr{qmr|qZ,0余数rm为模m的一个完全剩余系.7，下面的每一组数都是一个完全剩余系：（2）系.模m的最小非负完全剩余系是：0，1，2，………,m1;即除数为m时，余数可能取到的

m2

m；2 3.（同余类）Mr{x|xZxr(modmr0,1,m1，每一个这样的类为模m的同余类.说明：整数集合可以按模m来分类，确切地说，若a和b模m同余，则a和b属同一类，否则不属于同一类，每一个这样的类为模m的一个同余类.由带余除法，任一整数必恰0,1,……m1中的一个模m0,1,……m1这m个数彼此模m不同余，因此m共有mMr{x|xZxr(modmr0,1,m1.式2k和2k1（k为任意整数）.4.（剩余类）设m是正整数，把全体整按对模m的余数分成m类，相应的m个集合记为：K0K1,Km1Kr{qmr|qZ,0余数rm1}，称为模m的一（1）Z

KiKiK

(i

j)K0K1,Km1对于任意abZ，则a,bKr的充要条件是ab(modm)5.（完全剩余系）y1y2,ys称为模m的完全剩余系，如果对任意a有yj是a对模m的剩余，即ayj(modm.得m个数a0,a1,,am1组成的数组，叫m的一个完全剩余系.说明：在m个剩余类中各任取一个数作为代表，这样的m个数称为模m的一个完全剩余系，简称模m的完系.m个数c1c2,cm称为模m的一个完系，是指它们彼此模m0,1，2，……m1是模m的一个完系，这称作是模m的最小非负完（1）（2）若(am)1xaxb同时跑遍模m的完全剩余系：：部分，记为｛x｝.例如［0.5］＝0，[ 由[x],{x}的定义可得如下性质：1x[x]{x};0{x1；2.x1x]xx1；

3.设aZ，则[axa[x4.[xyxy;{xyx{y};[x]

x5.[x][x

x性质6.对于任意的正整数n，都有如下的埃恒等式成立[x][x

1][xn

2][xn

nn

][nx]7，我们给出如下记号：若b|a，且b1|a，则称为b恰好整除a，记为b||a.例如：我们有24||2000,53||2000等等，其实，由整数唯一分解定理：任何大1的整数a能唯一地写成apa1pa2paki1,2kp为质（素） （

p

(i

j）.pai||a,i1,2,ki7.p|n!，则i

[n][n][n pkn，因而0pk1，故[pk

0，而且对于mk时，都有

n0.pm式实际上是有限项的和.另外，此式也了乘数n!的标准分解式中，素因数p的指数的d(n)＝(11)(21)(k11,2,,k1为素数唯一分解定理中的指数.为了叙例如：242223.1的正整数a

1

2

k此式称为a的标准分解式.1的整数的标准分解k1.若a的标准分解式是（1）式，则d是a 12ppkpd

应说明（2）不能称为是di可能取零值（d也pii0）2.设abc(b,c)1a是整数的kbc也是整数的k次方.特别地，a是整数的平方，则bc也是整数的平方.三.(Euler)函数设n正整数0,1，……n1中与n互素的个数，称之为n的函数，并记为(n).若的标准分解式是npa1pa2pak,i1,2,,,k，则(n)的计算是 (n)pa11pa21pak1(p1)(p1)(

1),i1,2,,, 例如：(2000)(2453245321)(51)800(2001)(32329)(31)(231)(291)1432定义（(Euler)函数一组数x1,x2,,xs称为是模m的既约剩余系，如果对任的1

js，(xjm)1且对于任意的aZ，若(am＝1xj是am的剩余，即axj(modm).并定义(m)s1,2,m中和m(m)称为（Euler）函数这是数论中的非常重要的一个函数，显然(1)1，而对于m1，(mm1中与mp是素数，则有p)p1.1引理：(m)m

－PP1（证明：取模m的一个既约剩余系b1,b2,,bs,(s(m))ab1ab2,,absa与m互质，故abj(1

js仍与m互质，且有

abj(1i

js个1

js都能找到唯一的一个1j)sab

bjmodm 是一一的，从而(ab) (modm)b(modm)，as(b)(b)(modm)j

ss(m,j

1，as1(modm，故a(m)1(modm.证毕分析与解答：要证a(m)1(modm，我们得设法找出(m个n相乘，由(m个数我们想到1,2,m中与m互质的(m)a1a2a(m)，由于(am)＝1，从而aa1aa2aa(m)也是与m互质的(m)

a

aa1,

,,aa

a(m)

a

1而（1

a

m）＝1a(m)1(modm2（费尔马（Fermat）小定理）p及任意整数a有apa(modpp为质数，若ap的倍数，则ap0a(modp.若ap的倍数，则(ap定理3（（Wilson）定理）设p为质数，则(p1)!1(modp)证明：对于(x,p)1x,2x,p1)xp1x,2x,p1)xp从而对x{1,2,p1y{1,2,,p1xy1(modpxy1xy2(modp(xp1xy1y20(modp)p|y1y2于y1,y2{1,2,,p1}，有 xy2(modp).即对于不同的x对应于不同的y，1,2,p1p1xx21(modp)，即与它自x210(modp(x1)(x10(modpx1x1(modp)，xp1x1.fj(x为整系数多项式（1jkxfj(x0(modmj（1jk）称为同余方程组.fi(xx的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数cfj(c)0(modmj，1jk，则剩余类Mc{x|xZxc(modm（其中mm1m2,mk]）称为同余方程组的一个解，xc(modm)4（a1a2,akxaj(modmj，1jkxM1N1a1M2N2a2MkNkak(mod这里mmmmMm(1ikNM

im1 imi

1jk（NjMjmj的逆1010定理（郎日定理设p是质数，n是非负整数多项式f(x)

xnaxpn次的整系数多项式（p|anf(x0(modp至多有n个解（p有意义的情况下）.6：若l为a对模ms为某一正整数，满足as1(modm，则s必为l数

n为奇数时n20(mod

3整除n

（.（1.形如axbyca,bc,Z,ab不同时为零)的方程称为二元一次不定方程.1.方程axbyc有解的充要是(a,b)|c；2.若(a,b)1x0y0axbyc0x0

a

(t为任意整数yy0

3n元一次不定方程a1x1a2x2anxnc，a1a2,ancN)有解的充要条件是(a1,a2,an)|c.若有解，可先求xyc(a1,a2)d2,(d2,a3)d3，……，(dn1,an)dndn|c a1x1a2x2 d2t2a3x3dn|c

dd

an1xn1 dn1tn1anxn求出最后一个方程的一切解，然后把tn1的每一个值代入倒数第二个方程，求出它的一mn元一次不定方程组成的方程组，其中mnm1而消去了m1个不定方程，将方程组转化为一个nm1元的一次不定方程F(x1,,xn)0mN(x1,,xn无限递降法：若关于正整数n题P(n)对某些正整数成立，设n0是使P(n)成

N*n

无限递法论的设法构出方程新解使得它比选择的解格地小由此产生.利用分解法求不定方程axbycxy(abc0整数解的基本思路：将axbycxy(abc0转化为(xa)(cybab后，xai则解的一般形式为

cb

y 2x2y2z2xyz为正整数x2y2z2，如果(xy)dd2|z2，从而只需讨论(xy)1的情形，此时x,y,z两两互素，这种两两互素的正整数组叫方程的本原解.3.x2y2z2满足条件2|yxa2b2y2abza2b2，其中ab0,(a,b)1ab为一奇一偶x2y2z2的全部正整数解（xy的顺序不加区别）x(a2b2d,y2abdz(a2b2d