第二十章       初等数论

    本章简要地介绍了初等数论的基础知识.共分六节.前五节讨论了整数的性质与辗转相除法,连分数与费波那奇序列,同余式与孙子定理,介绍了几种重要的数论函数和麦比乌斯变换,并列出几类不可约多项式的判别方法.最后一节对代数数等基本概念和性质作了简单的介绍.

§1   整数

    [整数部分与分数部分]  a 为一实数,不超过a 的最大整数称为α 的整数部分,记作.称为a 的分数部分.

    例如  ,,等等

    整数部分具有下列关系式:

           

            ,n为自然数

            n为自然数

           

             

    注意,在计算机程序中的“取整运算”与这里的“整数部分”意义是有差别的:时是一致的;时不一致,例如,但计算机上取整后为.

    [整除性]  若有一整数c,使得整数ab之间适合于

    则称b可整除a,记作。这时a称为b的倍数,b称为a的因数(或约数).

b不能整除a,则记作ba.

    整除性具有下列性质(下列各式):

    1°  ,, ;

    2°  , ;

    3°  ,,则对于任意整数m,n

    4°  ba的真因数(),

  

    [素数与爱拉托斯散筛法] 恰有1和本身两个自然数为其因数的大于1的整数称为素数,记作.2为偶素数外,其余素数都是奇数.

    素数具有性质:

    1°  素数有无限多个. 如果不超过自然数n的素数个数记作 p(n),则当,*,进一步有

                             

    2°  p为素数,,.

    3°  中含素数p的方次数等于

                        

    4°  为正整数,它不能被不超过的所有素数所整除,n必为素数.这种判别自然数是否为素数的方法称为爱拉托斯散筛法.由此法可建立素数表.

    [唯一分解定理]  大于1的自然数都可唯一地分解为素数幂的积.,为自然数,n可唯一地表为

              

             (为自然数)

               (为素数)

这称为n的标准分解式。n所含不同素因数的个数s不超过.

    显然,任意自然数n可表为

                  (k,m 为自然数或零)

这种表达式是唯一的.

    [麦森数]  整数

                  ( p为素数)

为素数者称为麦森数.至今仅发现27,

   

是否有无穷个麦森数还未证明.

    [费马数]  整数

                    (n为自然数)

称为费马数.至今只发现5个费马数为素数,

            

下列46个费马数皆非素数:

        

    [辗转相除法*] 每一个整数a可以唯一地通过正整数b表为

              

式中q称为ab除所得的不完全商,r称为ab除所得的余数.辗转相除法是指下列一串有限个等式:

                               ( 1 )

    1  a=525 ,b=231 ,根据(1)式可列出下面的算式和草式:

                                 

                     

    [最大公因数与最小公倍数]  a,b为整数.既能整除a,又能整除b的正整数称为a,b的公因数,其最大者称为a,b的最大公因数*,记作,

特别当,a,b互素.

    a,b为正整数.a,b都能整除的正整数称为a,b公倍数,其最小者称为a,b最小公倍数*,记作,

                         

    n个正整数,用归纳法定义其最大公因数为

                    

其最小公倍数为

                         

    最大公因数与最小公倍数具有下列性质:

    1° 存在整数x,y,使得.并可由辗转相除法具体求出x,y.也由辗转相除法的一串等式得到,

         

    2  由例1(525,231)=21.因为由例1的算式有

         

所以得到 x=4,y=9.

    2° 对任意二整数x,y,必有.

    3° ,,.

    4°

       ,

    5° a,b为二正整数,为它们的素因数,且标准分解式分别为

           
                         

                    

    6°

    7° 为互素的正整数,,

              


* 数论中通常把自然对数记作.

* 我国古代数学家秦九韶于1247年在《数书九章》中讨论过辗转相除法(也称欧几里得算法).

* 国外书刊中,ab的最大公因数常记作g.c.d.(ab)ab的最小公倍数常记作l.c.m.(ab)