杨晓鸣基础数论讲义.doc

杨晓鸣基础数论讲义.doc基础数论讲义第一章整除性理论一、 整除的基本性质1、 dIa】和dIa2同时成立的充要条件是,对任意的x”x2^Z,有dIaiXi+a2x2o2、 aIb和bIa同时成立的充要条件是IaI=IbI乂0。3-设aIbo若bKO,贝ljIaI<IbIo不等于0的整数只能有有限个除数;4、设ax+my=lo那么,mIab的充要条件是mIbo―般地,对正整数h,k,mhIakb的充要条件是mhIb。二、 带余除法带余数除法的基木形式)对任给的整数a尹0和b,一定存在唯一的一对整数q和r,满足 b=qa+r,OWrV|aI。 (1)上式中的q称为是b被a除所得的部分商,r称为是b被a除所得的最小非负余数。此外,b被a整除的充要条件是r=0。证先证唯一性。假设还有一对整数q'和F满足式(1),即b=q'阳• (KfIao这样就有qaH-『q'aH-ro不妨设Kr'。若f=i•,则有q' 所以结论成立。若r<f,可得0<r—r=a缶q')。因而|a|<r一l另一方面,0<r-rIao矛盾。所以,必有r=r,q=q,下面证存在性。若b被a整除,即存在整数1使得b=la,则可取q=l,r-a若b不被a整除,考虑集合如{s=Aja:j€车显见,0不属于$以及集合S中必有正整数的什么)。由最小正整数原理知,在集合S中必有最小的正整数,设为&必有(火so<a|o若不然,则有Ia<知因b不被a整除,所以a|<so的什么)。因此(Xs=so-|a=b-joa-|a|<&是属于S的正整数,这和so是S中的最小的正整数矛盾。这样,取q=jo,z,就得到式(Do最后,由式(1)知,b被a整除的充要条件是r被a整除。由此及r<a|,就推出r被a整除的充要条件是证毕。三、 最大公约数和最小公倍数性质1①a”a2,…,ak的最大公约数与这些数的次序无关,即若%,a12,…,alkSa”a2,…,ak的―个重新排列,贝U(a”a2,…,ak)=(an,a^,…,aQ。任意改变a”a2,…,ak的正负号,它们的最大公约数不变。事实上,总有(ana2,…,ak)=(IaiI,Ia2I,IakI)0若akiIak,贝ij(a”a2,…,aki,ak)=(aPa2,…,aki)o对任意整数x有,(aPa2)=(ai,a2+a|X)o—般的有,(ai,a?,ak)=(ai,az+aix,•••»aQ。设正整数mI(a"a2»…,a。,则有m(ai/m,a2/m,…,ak/m)=(ai,a2»…,a。。特别的,(ai/(a【,a2),a2/(ai,a2))=h及(ai/D,a2/D,…,ak/D)=l,其中D=(a”a2,…,ak)02、装属定理存在整数x,y使得以+yh=(ci,b)四、 素数与唯一分解1、素数有无限多个。、标准分解式:每个大于1的正整数〃都可以唯一的表成〃=P],2一・・・P.」的形状,其中’<〃2V・・・VP.,是素数,而0,%,...,。,是正整数,这叫做〃的素因子标准分解式。例题1设自然数p,q满足,£= +q23」一+L,证明2003p13341335PI11 1 1证明——=1 1 1 q23 13341335Z1 1 1 1 1 、r,1 1=(1—H 1 )—2(—F—••*2 3 1334 1335 2 4〃 1 1 1 1、< 1(1 1 1 )—(1 ...+2 3 1334 1335 2H )1334上)OO/ 1 1 668669 13341335z1111、z11=( 1 )+( 1 )+•••+( F6681335 6691334 10012003 2003 2003= 1 • 668x1335669x1334 1001x10021335!p=2003^,21335!(——-——+ 1668x13351002)于是可得)为整数,从而有1001x10022003|1335!p,而(2003,1335!)=1,所以2003|po例题2求所有的正整数〃、m,满足〃5+/=7,”・("-〃+1)(/+n+1)=7”,.当时,〃3-〃+1=(〃-1)(后+〃)+1>1,/+〃+1>-〃+1=7“,〃2+〃+1=7力,其中a,beN*.于是,(〃-1)(7'-1)=(/1-1)(/广+〃)=7“-,(7“-1)|(7“・1),即(7“・1,7、1)=7"・(7“-1,7方-1)=7即)-1,得到b=(ci,b),即a=kb(keN+).则/-〃+1=7,=7处=(,户+〃+1/.当k=1时,有小-〃+1=/广+〃+1,〃=*22时,有(疽-n+I)_(〃2+n+iy<(/—〃+1)_(〃2+〃+1)2=_n4—〃3_3„2_3〃v0,,〃=2,m=2是原方程的唯一一组解.