中国高校课件下载中心 》 教学资源 》 大学文库

北京大学:《高等代数》课程教学资源(讲义)第八章 有理整数环 8.2 同余式

文档信息
资源类别:文库
文档格式:DOC
文档页数:2
文件大小:175KB
团购合买:点击进入团购
内容简介
8-2同余式 8.2.1有理整数环中的同余的定义 定义8.5设m是一个正整数,若a,b∈Z,且ba∈(m),亦即m(b-a),则 称b与a模m同余,记作b=a(modm)。不难得到,b与a模m同余就是它们用m做带 余除法所得的余数相同。整数模m同余为一等价关系,验证如下: 1、反身性:a=a(modm) 2、对称性:若b=a(modm),则a=b(modm) 3、转递性:若a=b(modm),b=c(modm),则
刷新页面文档预览

第二学期第十五次课 §2同余式 821有理整数环中的同余的定义 定义8.5设m是一个正整数,若a,b∈Z,且b-a∈(m),亦即m|(b-a),则 称b与a模m同余,记作b≡a(modm)。不难得到,b与a模m同余就是它们用m做带余 除法所得的余数相同。整数模m同余为一等价关系,验证如下: 1)反身性:a≡a(modm); 2)对称性:若b≡a(modm),则a≡b(modm); 3)转递性:若a=b(modm),b≡c(modm),则 a=c(mod m) Z关于这个等价关系划分为等价类,给定整数a,所有与a模m同余的整数属于一个 类,称为以a为代表的同余类。 822 Euler-函数 定义8.6(与m互素的剩余类的定义)设m是一正整数。如果a∈Z,(a,m)=1,则 a+(m)称为与m互素的剩余类。在全部模m剩余类中,与m互素的剩余类的数目记作 q(m),称作 Euler函数。 r+(m),l2+(m),…,r+(m)(t=p(m) 是全部互不相同的与m互素的剩余类,有设k∈Z,(k,m)=1,则 k+(m)k2+(m)…{+(m) 也是全部互不相同的与m互素的剩余类。 简证因为(,m)=1,故(k,m)=1,即k+(m)为与m互素的剩余类;由若 k+(m)=+(m)≠j),则k≡k(modm),于是r≡r(modm),从而 r+(m)=r1+(m),矛盾 定理( Euler定理)设k是与正整数m互素的整数,则 ktn=l(mod m) 证明设全部互不相同的与m互素的剩余类为 F+(m),2+(m)…F1+(m)(t=(m), 则由引理 k+(m),k2+(m),…,+(m) 与上述I个剩余类仅是排列次序不同而已,所以把它们连乘起来应该相等,即

第二学期第十五次课 §2 同余式 8.2.1 有理整数环中的同余的定义 定义 8.5 设 m 是一个正整数,若 a b, Z ,且 b a m − ( ) ,亦即 m b a | ( ) − ,则 称 b 与 a 模 m 同余,记作 b a m  (mod ) 。不难得到, b 与 a 模 m 同余就是它们用 m 做带余 除法所得的余数相同。整数模 m 同余为一等价关系,验证如下: 1) 反身性: a a m  (mod ) ; 2) 对称性:若 b a m  (mod ) ,则 a b m  (mod ) ; 3) 转递性:若 a b m  (mod ) ,b c m  (mod ) ,则 a c m  (mod ) 。 Z 关于这个等价关系划分为等价类,给定整数 a ,所有与 a 模 m 同余的整数属于一个 类,称为以 a 为代表的同余类。 8.2.2 Euler  -函数 定义 8.6(与 m 互素的剩余类的定义) 设 m 是一正整数。如果 a a m  = Z,( , ) 1 ,则 a m + ( ) 称为与 m 互素的剩余类。在全部模 m 剩余类中,与 m 互素的剩余类的数目记作 ( ) m ,称作 Euler 函数。 引理 设 1 2 ( ), ( ), , ( ) ( ( )) t r m r m r m t m + + + = 是全部互不相同的与 m 互素的剩余类,有设 k k m  = Z,( , ) 1 ,则 1 2 ( ), ( ), , ( ) t kr m kr m kr m + + + 也是全部互不相同的与 m 互素的剩余类。 简证 因为 ( , ) 1 i r m = ,故 ( , ) 1 i kr m = ,即 ( ) i kr m + 为与 m 互素的剩余类;由若 ( ) ( )( ) i j kr m kr m i j + = +  , 则 (mod ) i j kr kr m  ,于是 (mod ) i j r r m  ,从而 ( ) ( ) i j r m r m + = + ,矛盾。 定理(Euler 定理)设 k 是与正整数 m 互素的整数,则 ( ) 1(mod ) m k m   证明 设全部互不相同的与 m 互素的剩余类为 1 2 ( ), ( ), , ( ) ( ( )) t r m r m r m t m + + + = , 则由引理 1 2 ( ), ( ), , ( ) t kr m kr m kr m + + + 与上述 t 个剩余类仅是排列次序不同而已,所以把它们连乘起来应该相等,即

1G+(m)=+(m)=(k+(m) +(m F+( 于是 k≡∏modm) 因(F;,m)=1,故(…Fm)=1。于是 注意t=g(m),故命题成立。 作为 Euler定理的推论,我们有 定理( Fermat小定理)设p为素数,若p不整除整数k,则kP=1(modm)。 事实上,模p的p个剩余类,除0+(p)外,均为与p互素的剩余类,即p(p)=p-1。 8.2.3中国剩余定理 定理(中国剩余定理)设m1,m2…m是k个两两互素的正整数。任给k个整数 a1,a2…,ak,必存在整数x,使 x≡a(modm)(i=1,2,…,k) 证明首先,对一固定的i。当j≠时,(m,m)=1,则有uy,v∈Z,使 um; +v,n 0(modm)(≠l) 另一方面有 ∏(-m)=1+qm 现在利用上面得到的w,W2…,wk构造整数 aw 当j≠i时,m|w,即=qm,而w=1+qm,带入上式得 >, m, +a,(1+q,m, )=a,(mod m, 定理得证

1 1 1 1 1 ( ( )) ( ) ( ( )) ( ) ( ) t t t i i i i i i t t t i i i i r m r m kr m kr m k r m = = = = = + = + = + = + = +      于是 1 1 (mod ) t t t i i i i k r r m = =   因 ( , ) 1 i r m = ,故 1 2 ( , ) 1 t r r r m = 。于是 1(mod ) t k m  , 注意 t m = ( ) ,故命题成立。 作为 Euler 定理的推论,我们有 定理(Fermat 小定理)设 p 为素数,若 p 不整除整数 k ,则 1 1(mod ) p k m −  。 事实上,模 p 的 p 个剩余类,除 0 ( ) + p 外,均为与 p 互素的剩余类,即 ( ) 1 p p = − 。 8.2.3 中国剩余定理 定理(中国剩余定理) 设 1 2 , , m m mk 是 k 个两两互素的正整数。任给 k 个整数 1 2 , , , k a a a ,必存在整数 x ,使 (mod ) ( 1,2,..., ) i i x a m i k  = 证 明 首先,对一固 定的 i 。当 j i  时, ( , ) 1 m mi j = ,则有 u v j j , Z ,使 1 j i j j u m v m + = 。令 1 0(mod ) ( ) k i j j l j j i w v m m l i =  =    另一方面有 1 (1 ) 1 k i j i i i j j i w u m q m =  = − = +  现在利用上面得到的 1 2 , ,..., w w wk 构造整数 1 k j j j x a w = = 当 j i  时, | m w i j ,即 w q m j j i = ,而 1 w q m i i i = + ,带入上式得 (1 ) (mod ) j j i i i i i i j i x a q m a q m a m  = + +   定理得证

已到末页,全文结束
刷新页面下载完整文档
VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
相关文档