初等数论.pdf

第二十章 初等数论第二十章 初等数论 本章简要地介绍了初等数论的基础知识.共分六节.前五节讨论了整数的性质与辗转相除 法,连分数与费波那奇序列,同余式与孙子定理,介绍了几种重要的数论函数和麦比乌斯变换,并 列出几类不可约多项式的判别方法.最后一节对代数数等基本概念和性质作了简单的介绍. 1 1 整数 整数 整数部分与分数部分 设为一实数,不超过的最大整数称为的整数部分,记作 . 而 =称为的分数部分. 例如 ,11=. 232=,等等 . = 354 整数部分具有下列关系式: s aaal (为素数) s ppp 0, d,则(, ). a c b c d c = 5 p ) ) 若a,b为二正整数,为它们的素因数,且标准分解式分别为 p s1, ,l appais bppbis a s a i b s b i s s = = 1 1 1 1 1 01 l l ,( ,( 0 pps 1 0, pn,若p为奇素数，则二次同余式 xn 2 (mod ) l p 的解数为 + p n 1. 当p=2时,l=1时 有一解. = 4) (mod3, 4) (mod1, 2 n n l 当解无 当有二解 时 8) mod( 1/ , ) 8 (mod1, 2 n n l 当解无 当有四解 时 对模m的次数 设h为一整数,(m,h)=1,满足 hl1(mod m) 的最小正整数l称为h对模m的次数,或h的次数,mod m. 若(mod m),则hn1l n ,这里l为h的次数,mod m 素数模的原根与指数 设p为素数,次数为p1的数称为模p的原根. 设g为模p的一原根,则 ()1 22 , ,modg gg p l p 两两互不同余. 任一整数n( pn),必有一数a使得 nga (modp) , 01 = = ndn n n 1, 0 1, 1 当 当 2 (n)为积性函数,但非完全积性函数. 3 设,若 f(n)为积性函数,则 npp a s as = 1 1l ( ) ( )d f d d n ( ) = = 1 1 f pi i s 也为积性函数.例如 ( )d d d n =()1 1 = pi i s ( ) d d d n =()1 1 = pi i s ( ) = = nd s i i n p n= d d 1, 1 1 1 , 1 1 当 当 ( ) = = nd s i i n p n= d d 1, 1 1 1 , 1 1 当 当 欧拉函数 设 n 为自然数,(n)为不超过 n 且与 n 互素的正整数的个数,称为欧拉函数. 欧拉函数具有下列性质: 1 (n)为积性函数,但非完全积性函数. 2 若,则 npp a s as = 1 1l ( ) () () () nn p n p pp p pp i i s s s i i s i a i a i s ii = = = = = = 1 1 1 1 1 12 1 1 1 l 特别,当 p 为素数时, ()( )()()ppppppp aaaa = 1 12, a 3 ( )dn d n = 4 ( ) ( ) nn d d d n = 除数函数 自然数 n 的全部因数的个数称为除数函数,记作 d(n).除数函数具有下列性质: 1 d(n) 为积性函数,但非完全积性函数,对任意自然数 m,n,常有 ()() ( )d mnd m d n 2 若,则 npp a s as = 1 1l ( )()d na d n i i s =+ = 11 1 冯曼哥特函数 函数 (n) = = 否则 当 ,0 0,logmpnp m 称为冯曼哥特函数.(n)非积性函数. 麦比乌斯反转公式与麦比乌斯变换 1 反转公式一 设0 01 ,又设 h(k)为一非零完全积性函数.若对所有适合于 01 的常有 ( )()( )gf k k = h k 1 1 则对上述也常有 ( )( )()( )fk g k k = h k 1 1 反之也真. 2 反转公式二 设01,又设 h(k)为一非零完全积性函数.若对所有适合于1 0 的常 有 ( )( )gf k h k k = 1 则对上述也常有 ( )( )( )fk g k h k k = 1 反之也真. 3 反转公式三 设为一正整数, 又设 h(k)为一非零完全积性函数.若对所有常有 n0nn 0 ( )( )g nf d h n d d n = =( )f n d h d d n 则对上述 n 也常有 ( )( )( )f nd g n d h d d n = 反之也真. 4 麦比乌斯变换 设 n 为正整数,若 ( )( )g nf d d n =f n d d n 则 ( )( )f nd g n d d n = =( ) n d g d d n g(n)称为 f(n)的麦比乌斯变换,f(n)称为 g(n)的麦比乌斯逆变换. 5 乘积麦比乌斯变换 设 n 为正整数,若 ( )( )g nf d d n = 则 ( )( )f ng d n d d n = g(n)称为 f(n)的乘积麦比乌斯变换,f(n)称为 g(n)的乘积麦比乌斯逆变换. 麦比乌斯变换表 ( )( )g nf d d n = ( )( )f nd g n d d n = g(n) f(n) ( )n ( )nd(n) 11 01 , , n n = ( )n 1 11 01 , , n n = d(n) 1 ( )n ( )n p p p n 2 1 n ( )n n () d d n dn ,= 1 d d n n nd d n 1 n 1 n ()1p p n (n) - ( )nlogn logn (n) 5 多项式 5 多项式 整值多项式 当变数 x 为整数时,一多项式 f(x)的值常为整数， 则这种多项式称为整值多项式。 整系数多项式是整值多项式一特例。 整值多项式表达式： 1 凡 n 次整值多项式必可表为 a x n a x n a x a nn011 11 + + + l 式中为整数， aaan 01 ,l ()() ! 11 k kxxx k x + = l 2 整值奇多项式(满足 f(x)=f(x)必可表为 a x a x a xm m m12 1 1 3 1 21 + + + + l 式中为整数. m aaa, 21 l 3 整值偶多项式(满足 f(x)=f(x) 必可表为 aa x x a x x a x m xm m m012 1 12 1 3 1 21 + + + + + l 式中为整数. aaam 01 ,l 可约多项式与不可约多项式 设 f(x)为一有理系数多项式,若有非常数的有理系数多项式 g(x) 和 h(x),使得 f(x)=g(x)h(x) 则称 f(x)为在有理数域上可约(或可化),否则称 f(x)为有理数域上的不可约多项式(简称不可约多项 式). 高斯定理 设 f(x)为一整系数多项式,在有理数域上可约,则必有二整系数多项式 g(x)和 h(x), 使得 f(x)=g(x)h(x) 爱森斯坦判别法 1 设为一整系数多项式.若有素数 p,使得 ( ) nn nn axaxaxaxf+= 1 1 10 l ()p ain i 1 , 但 p ap an/,/ 0 2 则 f(x)为不可约多项式. 2 设为 2n+1 次整系数多项式,若有素数 p,使得 ( )f xa xa xa xa nn nn =+ + +0 21 1 2 22 l 1 ()()p ainpanjn ij 11 2 + +, 21 但 p ap a n /,/ 0 3 21+ 则 f(x)为不可约多项式. 派朗判别法 1 设 ( )dxaxaxxf n nn += 1 1 1 l 为一首项系数为 1 的 n 次整系数多项式,满足条件: (i) ()ai i n 011 (ii) ()dld ain i ,11 , (iii) 实数) ()acd naac nn + 112 1l( 则 f(x)为不可约多项式. 2 设 ( )f xxa xaxd nn n =+ 1 1 1 l 为一首项系数为 1 的 n 次整系数多项式,满足条件: (i) ()dd ain i 01, 1 (ii) ad bbaa nn =+ 11 21,l 1 2 则 f(x)为不可约多项式. 3 设 ( )f xxaxdad n nn =+ 11 0, 为一首项系数为 1 的 n 次整系数多项式,满足条件: d aad nn 11 3, 则 f(x)为不可约多项式. 4 设 ( ) nn nn axaxaxxf+= 1 1 1 l 为一首项系数为 1 的 n 次整系数多项式,满足条件: ()aaban nn n n + 1 1 22, 2 21 1 += n aabl 则 f(x)为不可约多项式. 5 设 ( )f xxa xaxaa nn nnn =+ 1 1 1 0l 为一首项系数为 1,常数项不为零的 n 次整系数多项式,满足条件: aaa n123 1 +la 则 f(x)为不可约多项式. 多项式的整除性 设 f(x)和 g(x)为二有理系数多项式,g(x)不恒为零,若有一多项式 h(x),使得 f(x)=g(x)h(x) 则称 g(x)可整除 f(x),记作 ( )( )g xf x或 g f 这时 g(x)称为 f(x)的因式,f(x)称为 g(x)的倍式.否则,g(x)不能整除 f(x),记作gf /. 以下f 表示多项式 f(x)的次数. 多项式的整除性具有下列性质: 1 ff 2 若 fg且g f ,则 f 与 g 仅相差一常数因子. 3 若 fg, g h则 fh 4 若 fg,则fg 若 fg,而gf /,则 f 称为 g 的真因式,显然fg. 5 若 p(x)为一不可约多项式,且( )( ) ( )p xf x g x,则( )( )p xf x或( )( )p xg x. 6 若 p(x)为一不可约多项式,且 f(x)=0,p(x)=0 有公共根,则必有( )( )p xf x. 多项式的带余除法 设 f(x),g(x)为任意多项式,g(x)不恒为零,则必有两个多项式 q(x)和 r(x),使 得 f(x)=g(x)q(x)+r(x) 式中 r(x)=0 或r=+aaxa n n l 则a0 为代数整数. 5 若为 n 次代数整数,则的幂可表为 i 1 1,10 += n niii i aaal 式中 i 为非负整数,都为有理整数. ik a 6 若为 n 次代数数,则的幂满足等式 i 1 1,10 += n niii i bbbdl 式中 i 为非负整数,为有理整数. ik bd, 单位数 若与都为代数整数,则称为单位数. 1 单位数具有下列性质: 1 为单位数的充分必要条件是:为首项系数为 1,常数项为1的有理整系数代数方程的根. 2 首项系数和常数项都为单位数,其他系数为代数整数的代数方程的根为单位数. 代数扩域 1 单扩域 设为 n 次代数数,则形为 1 1 2 210 + n n aaaal (系数为有理数) 的数的全体构成一个域.称为在有理数域 q 上添加所得的 n 次单扩域,记作 q().若 0,则 q() 为由代数数经加、减、乘、除(除数非零)所生成的数的最大集合. 2 有限扩域 由有限多个代数数 1, ,l k经加、减、乘、除(除数非零)所生成的域,称为 q 上的有限扩域,记作 k=q( 1, ,l k) 有限扩域必为单扩域,即存在代数数,使得 q( 1, ,l k)=q() 的次数称为有限扩域 q( 1, ,l k)的次数. 共轭数 设为 n 次代数数,满足有理数域上 n 次不可约多项式 * 有理整数即通常意义下的整数,这里是为了与代数整数相区别. a xa n n0 +l 记,又设为该多项式的另外 n1 个根,则称为的共轭根. ( ) = 1( )( ) 2 ,l n( )( ) 2 ,l n 任意代数数q(),则可唯一地表为 ( ) =+= 011 1 l n n (1) 式中() k kn0 1为有理数.记,则 ( ) = 1 ( )( )( ) () jj n j n jn=+= 011 1 2ll, 称为的共轭数. 代数数的迹与矩 设k=q(),记,设是的共轭数,则分别称 ( ) = 1( )( ) 2 ,l n ( ) ( )( )( ) () ( ) ()s nn =+=+ 11 ll ( ) ( )( )( ) () ( ) ()n nn = 11 ll 为代数数的迹与矩,式中如(1)式定义. ( ) ( j ) 注意,这里的迹与矩是对域 k 而言的,矩又称为范数.它们的另一个定义是： 设的极小多项式(以 为根的最低次不可约多次式)为 ( )g xxb xb mm m =+ 1 1 l 令r n m =,则 ( )( ) ()srb n rm m r = = 1 1 b 迹与矩具有下列性质: 1 若为代数数,则的迹与矩均为有理数. 2 若为代数整数, 则的迹与矩为有理整数.若为非零代数整数,则( )( )sn11,. 3 代数整数为单位数的充分必要条件是:( )n= 1. 4 s(+)=s()+s() n() =n()n() 代数数域的基底与整底 1 基底 设 k 为 n 次代数扩域, 1, ,l n为 k 中一组代数数,若 k 中任意代数数都可唯一 地表为 = = jj j n 1 式中 j为有理数,则 1, ,l n称为 k 的一组基底.显然 1, ,l n在有理数域上线性无关. 1, ,l n是域 k 的一组基底的充分必要条件是: ( )( )( ) ( )( )( ) ( )( )( ) 1 1 2 21 1 2 2 22 12 0 l l llllllll l n n nn n n 式中是的共轭数, j=1 2. ( ) () j i in=2,l ( )( j 1 =) j , ,ln 若 k=q(),则1为 k 的一组基底. 1 , ,l n 2 整底 设 k 为 n 次代数扩域, 1, ,l n为 k 中一组代数整数,若 k 中任意代数整数都可 唯一地表为 = = jj j n 1 式中 j为有理整数,则 1, ,l n称为 k 的一组整底. 若 1, ,l n为一组使 ( ) () det j 1 为最小的代数整数,则这组 1, ,l n为一组整底. 二次域 设 d 为一无平方因子的有理整数.则 q(d)为二次域.q(d)中的任意代数数都可 表为 =+ab d 式中 a 和 b 都为有理数. 设 d 为一无平方因子的有理整数. () () + = 4mod3 , 2, 4mod1, 2 1 dd d d 当 当 则1,为二次域 q(d)的一组整底. 一般 n 次域 q不一定能找到代数整数,使 ( )(n 3) 1 1 ,l n 构成 q( )的一组整底. 高斯域 设i