第二学期第十五次课 §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 = + + 定理得证