Question

求算法高手解释一下

(3k+6)的阶乘对(3*k+7)求余，然后将得到的余数加1，再除以(3*k+7)，得到m，求n(n为不超过m的最大整数),k>=1.我看到有人的代码只用判断(3*k+7)是否为素数，就能判断n的值了，如果(3*k+7)是素数，n =1,否则n =0;求解释为什么只用判断(3*k+7)是否为素数就能判断n的值，在线等！！！！！！！！

Answer 1

因为{ [(3*k+6)!] % (3*k+7) + 1 } / (3*k+7) = m;
而[(3*k+6)!] % (3*k+7)的取值范围是[0,3*k+6];
所以m的取值只有两种可能：
当[(3*k+6)!] % (3*k+7) < 3*k+6 时，m = 0;
当[(3*k+6)!] % (3*k+7) = 3*k+6 时，m = 1;
根据费马小定理：
若一个数是素数P，令 W = (1*2*3***P-1)，则 W≡W(mod p） 注释：≡是同余符号。
所以当(3*k+7)为素数的时候，[(3*k+6)!] % (3*k+7) = 3*k+6， m = 1; 此时n可取1。
同理当(3*k+7)不是素数的时候n可取0。
费马小定理网上有很多知识，你可以自己去搜搜看。
下面我给你贴上百度百科里面的解释：
　
一、准备知识：
　　引理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为整数且m>1,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]=i-1,1<i<=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是一个整数，且m>1，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)
　　二、证明过程：
　　构造素数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）

Answer 2

如果(3*k+7)是素数,(3k+6)的阶乘对(3*k+7)求余，剩下的就是3k+6；
如果不是那就小于3k+6！

追问

如果(3*k+7)是素数,(3k+6)的阶乘对(3*k+7)求余，剩下的就是3k+6；这句是怎么得出来的？？请教解释一下