实一算术问赠装(1)整除：设α、βEz[]为复整数且β+0,如果存在复整数使得α=βy，则称β整除α，记为βlα，也称β为α的一个因子如果β整除两个复整数之差α-α，则称α和α模β同余，记为α=α(modp).(2)范数：设α=a+bo，其中a，b为整数，α表示相应的共轭复数，显然α=a+bw=a+b=（a-b）-bo，表明复整数的共轭也是复整数.记N（α）=αα，称为α的范数.直接计算可知N（a+b)=a2-ab+62范数的重要性在于它建立了复整数与通常整数之间的基本关系，而且从N（α）=αα=Iα12即可看出范数其实就是该复数绝对值（也称为模长，对实数x，y，相应复数x+y-1的绝对值定义为1x+y-il=vx+）的平方。两个复整数相除未必还是复整数，即Z［]对除法运算不封闭.如果记Q[w]=|s+twls,tEQl，则Q［]中的元素对加减乘除四则运算封闭.任取αEQ【].仍然定义N（α）=αα为α的范数，同样成立N（s+tu）=s2-st+t2.从定义不难看出：每个αEQ【]的范数N（α）总是非负的有理数，当α为复整数时，N（α）还是非负整数.显然N（α）=0当且仅当α=0.另外，范数还保持乘积，即对任意α，βEQ［]，有N(a)=N(α)N(β).(3)单位：称范数为1的复整数α为单位.设α=α+b，则N(a+b）=α2_ab+b2=1.因为a，b均为整数，故1-ab=a2-2ab+62=（a-6）≥0,即ab≤1.另一方面，如果ab<0,则ab>0,表明a,b均不为零且-ab≥1,必有2-ab+b2>1,矛盾.所以有0≤ab≤1,只有a=±1,b=0,或a=0,b=±1,或a=b=±1这六种情形，相应的复整数为α=±1，±，±2.反之，上述六个复整数的范数显然为1.这样，就证明了在2【]中共有六个单位。31
数学的100个基本问题单位其实就是1的因子，换句话说，α为单位当且仅当α整除1,或等价地，1/α也是Z［］中的复整数.这从范数的定义即可得出：如果α为单位，则N（α）=αα=1,表明α整除1；反之，如果α整除1，则存在复整数β使得1=αβ，两边取范数得1=N（α）N（β）,因范数为非负整数，只有N（α）=1.如果两个复整数α和β相差个单位，即存在单位ε使得β=eα，则称α和β相伴，记为α~β.不难看出，两个非零的复整数相伴当且仅当它们能相互整除，（4)带余除法：在整数集合2中，有所谓的带余除法或称欧氏算法，即对任意两个整数a，b，只要b≠0,则存在整数g，r使得a=bq+r并且0≤r<1bl,其中g称为a除以b所得的商，而r称为余数，带余除法是整数理论中的一个最为基本的法则，也是证明许多定理的出发点，现在也来建立复整数的带余除法，即对任意两个复整数α，β且β+0,将证明存在复整数8满足α=份+并且N()<N(β).事实上，从α/β=αβ/N(β)可知存在有理数st使得α/β=s+tw.在数轴上用整数去逼近有理数，即可选取整数m，n使得Is-ml≤1/2以及lt=nl≤1/2.令8=m+，则?为复整数.再令=α-β，则也是复整数.需要证明的是N()N(β).根据【]中范数的定义，有N[（s-m）+（t-n）w]=（s-m）2-(s-m)(t -n)+(t - n)≤1/4+1/4+1/4< 1,所以N() =N(β)N(a/β-8)=N(β)N[(s-m)+(t-n)w)<N()（5)最大公因子：设α，βgEZ［]为任意复整数，如果同时整除α和β，则称。为α和β的一个公因子.在α和β的所有公因子中，范数最大的公因子称为最大公因子.如果。为α和β的一个最大公因子，则与。相伴的每个复整数e也是最大公因子.这里将证明α和β的每个最大公因子。均可写为=α+，其中入和为适当选取的复整数32
温一、算术问题事实上，考虑复整数集合=aBI，μE【]，选取A中的非零元素使得N(）最小.对任意EA，根据（4)中的带余除法，存在复整数和使得=+且NN.注意到EA，它的每个倍数也在A中，而且A的两个元素之差也在其中，所以Y=-E.根据的最小选取，只有N(）=0,亦即整除中的每个元素.特别地，整除α和β表明为α和β的一个公因子.从可令=，其中入，μ为复整数.现在证明还是最大公因子.事实上，如果是α和β的任意一个公因子，则从整除α和β可知也整除入α+=从而是的一个因子，故N（）≤N（）按定义确为α和β的一个最大公因子.因为已经预先给定了α和β的一个最大公因子，把上述换为即知N（）≤N（），根据最大公因子的定义，只有N（）=N（）.又因为整除，令=，两边取范数即得N（e）=1,表明e为单位，从而e-也是复整数.最后就有a=e-ly=(e-la)a+(e-μ)p.总之，通过上述讨论实际上证明了任意两个不全为零的复整数α和β均存在最大公因子：任何一个公因子均整除最大公因子；任意两个最大公因子相差一个单位，亦即任意两个最大公因子都相伴；每个最大公因子均可写为=入α+的形式，其中的入、都是复整数如果两个复整数α和β的最大公因子只有单位，等价于说1是α和β的一个最大公因子，则称α和β互素（6素元：作为素数概念的推广，在【中定义相应的素元概念设α为非零非单位的复整数，如果α的因子只有1和α以及它们的相伴元，则称α为【]中的一个素元，素元的基本性质如下：设e为素元，α，β为复整数，如果e整除aβ，则p必然整除α或β.这是因为当e不整除α时，1就是它们的一个最大公因子.根据（5）可知存在复整数入，μ使得1=入α+33
数学的100个基本问题Mp.两边同乘β得β=aβ+B因为等式右边的两项分别被p整除，从而左边的β也能被β整除由此可推出：如果素元p整除若干复整数的乘积α""αn，则p必能整除其中的某个αi（7）惟一因子分解：类似于整数中的算术基本定理，下面将证明复整数具有惟一因子分解性质.设αEz【]为非零非单位的复整数，则α可表示为一个单位和一些素元的乘积，简称为素元分解，即α=ep"Pa，其中e为单位而诸p,均为素元.进而，如果α=e㎡也是这样个表示，即e为单位且Y均为素元，则n=m，并且把足标适当重排后可使每个p:与相伴.换句话说，α的任意两个素元分解在相伴的意义下是惟一的。分解的存在性是显然的：如果α本身为素元，则α=α即为素元分解；如果α不是素元，则可令α=αα2,其中α1,α2均不是单位，从而N(α）和N(α2)都大于1,又N(α）=N(α）Nα2),所以N(α）<N(α）且N(α2）<N（α）.通过对N（α）做归纳法，由归纳假设可知α，和α2都具有素元分解，合并后即得α的素元分解现证分解的惟一性：设α=p1"P=e'"m为上述两个素元分解，则pi整除em.根据素元的性质，PI必然整除某个，适当重排足标后不妨假设pi整除1.因为也是素元，从而P与相伴，即存在单位e使得=E1P1.从α的两个素元分解式中两边除去pi即知ep2"Pn=（ee）Y2m.显然e'e还是单位对p2重复p的论证，不妨设p2与2相伴,同理存在单位e2满足Y2=e2P2，代人消去后又得等式ep3Pm=（e'e1e2）Y3m再对p3，P4，.不断重复该论证过程，最终得到n=m，且适当编号后可使得每个p与Y相伴。（8）素元1-：以下总记元=1-W.显然N（元）=3.表明元的因子只有单位和元的相伴元，即元确为素元.这是一个相当特殊的元素，在高斯的证明中起着关键的作用.为此，先建立有关元的34
一算术问题三条基本性质：性质1：设α为复整数，则α除以元所得的余数为0，±1.性质2：设α为复整数，则α=α（mod元）性质3：设元不整除复整数g，则。3±1（mod元4）事实上，对任意复整数α=a+bu，有α=a+bw=(a+b)-b(1-w)a+b(mod元).因为整数a+b除以3的余数为0，±1，而元整除3=元元，所以a+b除以元的余数也只能是0，±1，从而任意复整数α模元的余数只有三个取值：0，-1，1，说明性质1成立.另一方面，对任意整数n，显然n2和n除以3后所得的余数相等，即n2n（mod3)，更有nmn（mod元）.所以，Q3-α=(a+b)3_(a+b)=0(mod元),表明性质2也成立.最后，如果元不整除α，则α=±1（mod元）.分两种情形当α除以元的余数为1时，可令α=1+入元，入为某个复整数，则α3-1 =(α-1)(α-)(α-)=入（元+入元)(1-2+入）=元(1+a)(入-)注意到=1（mod元），根据性质2，有(1+)(-2)=入(1+入)(-1)=3_入=0(mod 元),由此表明α3_1被元*整除，即α3=1（mod元）.当α除以元的余数为-1时，即-α=1（mod元），在上述讨论中换α为-α，同理可得（-α）3=1（mod元4），亦即α=-1（mod元4）.总之，性质3得证在高斯的证明中还涉及另外一个概念：设α为非零的复整数，则可令α=e元"β，其中e为单位，β为复整数且不被元整除.根据（7)中有关素元分解之惟一性的论述，可知非负整数n由α惟一确定，称为α关于元的指数，记为n=ord，（α）.因为预先固定了素元元，在不致引起混淆时可把α关于元的指数简记为o（α）.不难35