我的专业我来.ppt

费马定理 一：费马小定理 二：费马大定理 费马小定理： 假如p是素数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）。假如p是素数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。 一、准备知识： 　　 引理1．剩余系定理2 若a,b,c为任意3个整数，m为正整数，且（m,c)=1，则当ac≡bc(mod m）时，有a≡b(mod m) 　　证明：ac≡bc(mod m）可得ac–bc≡0(mod m）可得（a-b)c≡0(mod m）因为（m,c)=1即m,c互质，c可以约去，a–b≡0(mod m）可得a≡b(mod m) 　　 引理2．剩余系定理5 　　若m为整数且m1,a[1],a[2],a[3],a[4]，…a[m]为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。 　　 证明：构造m的完全剩余系（0,1,2，…m-1），所有的整数必然这些整数中的1个对模m同余。取r[1]=0,r[2]=1,r[3]=2,r[4]=3，…r=i-1,1i=m。令（1）：a[1]≡r[1](mod m),a[2]≡r[2](mod m),a≡r(mod m）（顺序可以不同），因为只有在这种情况下才能保证集合{a1,a2,a3,a4，…am}中的任意2个数不同余，否则必然有2个数同余。由式（1）自然得到集合{a1,a2,a3,a4，…am}对m构成完全剩余系。 引理3．剩余系定理7 　　设m是一个整数，且m1，b是一个整数且（m,b)=1。如果a1,a2,a3,a4，…am是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4]，…ba[m]也构成模m的一个完全剩余系。 　　 证明：若存在2个整数ba和ba[j]同余即ba≡ba[j](mod m），根据引理1则有a≡a[j](mod m）。根据完全剩余系的定义和引理4（完全剩余系中任意2个数之间不同余，易证明）可知这是不可能的，因此不存在2个整数ba和ba[j]同余。由引理5可知ba[1],ba[2],ba[3],ba[4]，…ba[m]构成模m的一个完全剩余系。 引理4．同余定理6 　　 如果a,b,c,d是四个整数，且a≡b(mod m),c≡d(mod m），则有ac≡bd(mod m) 　　 证明：由题设得ac≡bc(mod m),bc≡bd(mod m），由模运算的传递性可得ac≡bd(mod m) 传递性：如果a≡b mod m,且b≡c mod m,那么a≡c mod m. 二、证明过程： 构造素数p的完全剩余系P={1,2,3,4…（p-1)}，因为（a,p)=1，由引理3可得A={a,2a,3a,4a，…（p-1)a}也是p的一个完全剩余系。令W=1*2*3*4…*(p-1），显然W≡W(mod p）。令Y=a*2a*3a*4a*…（p-1)a，因为{a,2a,3a,4a，…（p-1)a}是p的完全剩余系，由引理2以及引理4可得a*2a*3a*…（p-1)a≡1*2*3*…（p-1)(mod p）即W*a^(p-1）≡W(modp）。易知（W,p)=1，由引理1可知a^(p-1）≡1(modp) 有一个函数：f(x)=5*x^13+13*x^5+k*a*x 给定一个非负的 k 值，求最小的非负的 a值使得对任意的整数x都能使f(x)被65 整除。每输入一个k 值，对应输出一个 a值，若不存在a值则输出 no ，其中(k, a 都是整型)。 算法分析： f(x)=5*x^13+13*x^5+k*a*x=x(5*x^12+13*x^4+k*a)，这个函数的形式直接就是费马小定理的形式 f(x)=x(5*x^12+13*x^4+k*a)用此定理分析： （1）如果x是65的倍数，那么已经符合65整除f(x) （2）如果x是5的倍数，只要5*x^12+13*x^4+k*a被13整除即可，去掉13的倍数13*x^4，也即5*x^12+k*a被13整除，由费马小定理，5与13互质，13是质数，所以x^(13-1)模13余1，所以5*x^12模13余5，要使5*x^12+k*a被13整除，k*a必须模13余8(k*a≡8(mod 13)) （3）如果x是13的倍数，类似（2），需要13*x^4+k*a被5整除，由费马小定理类似得到x^4模5余1，所以13*x^4模5余3，k*a必须模5余2(k*a≡8(mod 13)) （4）如果x不含5和13这两个因子，则需要5*x^12+13*x^4+k*a被65整除了，等价于既要被5整除，又要被13整除，就相当于以上(2)(3)两种情况的条件要同时满足，所以有k*a≡2(mo