离散数学5-4秦九韶定理euler函数课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,5.4,秦九韶定理,Euler,函数,5.4 秦九韶定理 Euler函数,5.4.1 一次同余式组 秦九韶定理,定理5.4.1,设,m,1,m,2,为,m,1,，m,2,的最低公倍数。则同余式组,x,a,1,(mod m,1,),x,a,2,(mod m,2,).(,1,),在,modm,1,m,2,下有唯一解的充要条件为,(,m,1,m,2,)|(a,1,-a,2,).(,2,),5.4.1 一次同余式组 秦九韶定理 定理5.4.1,证明：,必要性,。记,m,1,，m,2,的最高公因数和最低公倍数分别为,d，m，,即,d=(m,1,m,2,)，m=m,1,m,2,。,若,(,1,),有解,x,0,，,则,x,0,a,1,(mod d)，x,0,a,2,(mod d)，,从而,d|(a,1,-a,2,)。,充分性,。若,d|(a,1,-a,2,)，,往证,(,1,),在模,m,下有唯一解。,证明：必要性。记m1，m2的最高公因数和最低公倍数分别为d，,证明：,因为,x,a,1,(mod m,1,),解的形式为,x=a,1,+m,1,y，,代入,(,1,),的二式中，得,a,1,+m,1,y,a,2,(mod m,2,)，,即,m,1,y,a,2,-a,1,(mod m,2,)。,于是(,m,1,/d)y,(a,2,-a,1,)/d(mod m,2,/d)，,且(,m,1,/d,m,2,/d)=1。,由上节的定理5.3.1知，关于模,m,2,/d，y,有唯一解,y,1,。,因此，,x,有解,x,1,=a,1,+m,1,y,1,。,若,x,，,x”,都是,(,1,),的解，则,x-x”,0(mod m,1,),，,x-x”,0(mod m,2,),。,即,m,1,|(x-x”),，,m,2,|(x-x”),。,从而,m|(x-x”),，,即,x,x”(mod m,1,m,2,),。,证明：因为xa1(mod m1)解的形式为 x=a1+m1,定理,5.4.2(,秦九韶定理,),设,m,1,m,2,m,k,两两互质。,a,1,a,2,a,k,为,k,个整数，则下列同余式组有解，且在模,m,1,m,2,m,k,下解唯一：,x,a,1,(mod m,1,)，x,a,2,(mod m,2,)，.，x,a,k,(mod m,k,)。,(,3,),定理5.4.2(秦九韶定理)设m1,m2,mk,证明:,先不讨论普遍情形而先求,l,i,，i=1,k，,使适合下列特殊的合同式：,l,i,1(mod m,i,)，l,i,0(mod m,j,)，j,i(,4,),今,j,i,时，,m,i,和,m,j,互质，故,m,i,和 互质，从而由上节定理5.3.1，有,c,i,使,证明:先不讨论普遍情形而先求li，i=1,k，使适合下,证明:,取,，,则,l,i,适合(,4,)。今取,x=a,1,l,1,+a,k,l,k,(,5,),则模,m,i,，,故,x,适合,(,3,),。,证明:取 ，则l,证明:,现在证唯一性。若,x，x,都适合(,3,)，则,xx,(mod m,i,)，i=1,k，,故由5.2定理5.2.4，,xx,(mod m,1,m,k,),使用了构造性证明方法，先构造一些满足局部合同式的局部解，再把这些局部解合起来构造成整体解。,证明:现在证唯一性。若x，x都适合(3)，则xx(m,证明:,这里的局部合同式就是(,3,)中每一个同余式，即构造,y,i,，,使得,y,i,a,i,(mod,m,i,)，,而,y,i,对其余合同式无影响，即,y,i,0(mod,m,j,)，,j,i,。,特别构造,l,i,使得(,4,)成立。若,l,i,已得到，则令,y,i,=,a,i,l,i,，,于是,y,i,满足,y,i,a,i,(mod,m,i,)y,i,0(mod,m,j,)j,i,再令,x,=y,1,+y,k,，,则,x,为所求。,证明:这里的局部合同式就是(3)中每一个同余式，即构造yi,例5.4.1,求,x,满足同余式组：,x,1(mod 4),x,2(mod 5),x,3(mod 7),解：,因为模,4,，,5,，,7,两两互质，所以可以用上述定理的构造性证明过程求解。先求,l,1,，,l,2,，,l,3,使得,例5.4.1求x满足同余式组：x1(mod 4)x2,例5.4.1,l,1,1(mod 4),l,2,1(mod 5),l,3,1(mod 7),l,1,0(mod 5),l,2,0(mod 4),l,3,0(mod 4),l,1,0(mod 7),l,2,0(mod 7),l,3,0(mod 5),得,l,1,=35,c,1,，,l,2,=28,c,2,，,l,3,=20,c,3,，,c,1,满足35,c,1,1(mod 4)，,即 3,c,1,1(mod 4)，,从而,c,1,3(mod 4)。,故,l,1,=105。,同理得,l,2,=56，,l,3,=120。,于是,x,=1,105+2,56+3,120=577,17(mod 140),。,例5.4.1l11(mod 4)l21(mod 5),5.4.2,一元高次同余式的化简,不讲,5.4.2 一元高次同余式的化简 不讲,5.4.3剩余系遍历,Euler,函数,在(,5,)中，让,a,1,经过,mod m,1,的一个完全剩余系变化，,a,k,经过,mod m,k,的一个完全剩余系统变化，这样，我们共得到,m,1,m,k,个,x,。,设,x,=,a,1,l,1,+,a,k,l,k,，,x,=,a,1,l,1,+,a,k,l,k,。,是两个这样的,x,。,5.4.3剩余系遍历 Euler函数 在(5)中，,5.4.3剩余系遍历,Euler,函数,于是，,x,a,1,(mod m,1,)，,x,a,k,(mod m,k,)；,x,a,1,(mod m,1,)，,x,a,k,(mod m,k,)。,所以，若,a,1,a,k,和,a,1,a,k,不全同，则,x,x,(mod m,1,m,k,),5.4.3剩余系遍历 Euler函数 于是，x,5.4.3剩余系遍历,Euler,函数,这就是说，我们得到的,m,1,m,k,个,x,mod m,1,m,k,在不同的剩余类内，但,mod m,1,m,k,只有,m,1,m,k,个剩余类，所以下面的定理成立。,5.4.3剩余系遍历 Euler函数 这就是说，我,定理,5.4.4,（遍历定理）,设,m=m,1,m,k,，,而,m,1,m,k,两两互质。在(,5,)中，使,a,1,a,k,分别遍历,mod m,1,mod m,k,的各一个完全剩余系，则,x,遍历,mod m,的一个完全剩余系。,定理5.4.4（遍历定理）设m=m1mk，而m1,m,Euler,函数,设,n,是任意正整数，试看,mod n,的任意剩余类,A,。,设,a,A,。,若,a,和,n,互质，则,A,中任意数和,n,互质。此时我们称剩余类,A,和,n,互质。,事实上，若,b,a(mod n)，,则,a=b+qn，,倘若,b,和,n,有一个大于1的公因数,d，,则,d,也是,a,的因数，因而是,a,和,n,的公因数，此为矛盾。可见，若,A,中有一个数和,n,互质，则其中所有的数都和,n,互质。故,A,中的数或者都和,n,互质，或者都和,n,不互质。,Euler函数 设n是任意正整数，试看mod n的任意剩余类,Euler,函数,和,n,互质的剩余类的个数记为,(,n)，,称为,Euler(,欧拉)函数,。从和,n,互质的每一个剩余类中取出一个数，这样得到的,(,n),个数便称之为作成,mod n,的一个,简化剩余系,。,显然，从,mod n,的一个完全剩余系中取出与,n,互质的那些数就得到,mod n,的一个简化剩余系，因而,(,n),等于,n,的正数中和,n,互质的数的个数。,例如，,n=10,，,则,mod n,的一个完全剩余系为,0,，,1,，,，,9,，一个简化剩余系为,1,，,3,，,7,，,9,，,(10)=4,。,Euler函数 和n互质的剩余类的个数记为(n)，称为Eu,定理5.4.5,设,m=m,1,m,k,，,而,m,1,m,k,两两互质。则,(,m)=,(m,1,),(m,2,),(m,k,)(,9,),这个结论实质是说在秦九韶定理证明中构造的,x,=,a,1,l,1,+,a,k,l,k,，,若每个,a,i,各自遍历,mod m,i,(i=1,k),的一个简化剩余系，则,x,遍历,mod m,的一个简化剩余系。因为,a,i,有,(,m,i,),个取法，所以得,x,有,(,m,1,),(m,k,),个取法。,定理5.4.5 设m=m1mk，而m1,mk两两互,证明：,设,mod m,i,的一个简化剩余系为,D,i,(i=1,k)，mod m,的一个简化剩余系为,D，,我们证明：,D,1,D,2,D,k,与,D,可以建立1-1映射。,定义映射,如下,:(,a,1,a,k,),x,=,a,1,l,1,+,a,k,l,k,对任意,(,a,1,a,k,),D,1,D,2,D,k,，,有,a,i,与,m,i,(i=1,k),互质，而,x,a,i,(mod m,i,),，,从而有,x,与,m,i,互质，,i=1,k,，,由定理,5.2.3,，,x,和,m,互质。即,是,D,1,D,2,D,k,到内的一个映射，由遍历定理知,是单射。,证明：设mod mi的一个简化剩余系为Di(i=1,证明：,再证,为满射，对任意,x,，则由遍历定理知，存在,a,1,a,k,分别属于,mod m,，mod m,k,的完全剩余系，使得,x,=,a,1,l,1,+,a,k,l,k,。,下面证明,(,a,1,a,k,),D,1,D,2,D,k,，,由于,x,与,m,互质，所以,x,与,m,i,互质。而,x,a,i,(mod m,i,)，,因而,a,i,与,m,i,互质，即,(,a,1,a,k,),D,1,D,2,D,k,。,因此,为1-1映射。于是,D,的元素个数与,D,1,D,2,D,k,的元素数相同。,注意到,D,1,D,2,D,k,的元素数为,(,m,1,),(m,k,)，,的元素数为,(,m)，,故,(,m),(m,1,),(m,k,)。,证明：再证为满射，对任意x，则由遍历定理知，存在a1,定理5.4.6,设,是,n,的质因数分解式，,p,1,p,k,都不同，于是,定理5.4.6 设 是n的质,证明：,首先考虑最简单情形；,n=p,为质数，则,(,n)=p-1=p(1-1/p)，,结论成立。,其次考虑,n=p,r,，p,为质数，而求,(,p,r,)。,一个数,a,和,p,r,互质等于说,a,不是,p,的倍数。今在从1到,p,r,的,p,r,个数中，是,p,的倍数的共,p,r-1,个，即,p，2p，p,r-1,p,因而和,p,互质的共,p,r,-p,r-1,个，故,(,n)=,(p,r,)=p,r,-p,r-1,=p,r,结论成立。,证明：首先考虑最简单情形；n=p为质数，则(n)=p-1=,证明：,第三考虑一般情况，,，,p,1,p,k,互不相同，则(,p,i,p,j,),=1(i,j),。,从而,。,由定理,5.4.5,及上述第二中情形证明有,证明：第三考虑一般情况，p1,根据定理5.3.1：若(,a,m)=1，,则,ax,b(mod m),有唯一解。用另一种方法证明解的存在性，只需考虑,ax,1(mod m)。,因为若,x,0,是,ax,1(mod m),的解，则可得,x,0,b,为,ax,b(mod m),的解。,设,r,1,，r,(m),是,mod m,的一个简化剩余系，则(,r,i,m)=1，i=1，,(m)，,从而(,r,1,r,(m),，m)=1。,根据定理5.3.1：若(a,m)=1，则 axb(m,再看,ar,1,ar,(n),，,因为(,a,m)=1，,所以(,ar,i,m)