数的整除之伪费马小定理的判定

这个方法经过实践发现用于优化计算是毫无用处.用手算差不多可以算一下.

几天前知道了一个数能否被7整除的判定。
最后一位截尾.拿被截的数减去尾数乘以2。
用数学说明一下。假设一个数是ab 其中a是前面的数。b是尾数
则
ab≡a-2b (mod 7)
证明：
设t=[ab/10]  即a       ([]为高斯函数取整)
ab=x
x≡t+(-2)(x-10t) (mod7)
即 -x≡x≡21t (mod7)
21t显然被7整除
已知13的判定。
x≡t+2(x-10t) (mod13)
那么这个有可能被推广
构造m=t+k*(x-10*t)
若干步之后m将变小
构造C程序

# include "stdio.h"
void main()
{
loop:
int t=0,x=0,k=0,y=0,i=0,m=0;
int n;
printf("请输入要判断的数");
scanf("%d",&x);//验证的数
printf("请输入要整除的数");
scanf("%d",&y);//K为整除的数
for(i=-9;i<0;i+=2)
{
  if(1==(-1*y*i)%10)
  {
  k=int(y*i/10); 
     break;
  }//取系数K这个是算法内核
}//end for
m=x;//拖入运算，保留X
if (x>100)
{ while(m>100)//这个是人工化简过程
  {
  t=int(x/10);
  m=t+k*(x-10*t);
  }//end while}
}//end if
if(m%y==0)
{printf("%d可以被%d整除/n",x,y);}
else
{printf("%d不可以被%d整除/n",x,y);}
printf("输入0则继续");
scanf("%d",&y);
if (0==y)  {goto loop;}
else ;
}//end

说明：
这个就是任意一个数X能否被Y整除的人工判定算法。
适用范围，y是非2，5的全体奇数。
不过如果Y值比较大则需要在while附近把100往上拓展。

这个原理证明是W同学证明的。我推广了一下。分别用C和VB写了一下。呵呵
为什么说这个算法是伪费马小定理呢？其实我没有证明。
如果说截尾取有可能是取的数是和模数互质的。比如 28 7 截尾 7和8*2互质
而这个运算其实是构造10K+1 等于模数的倍数。所以不能用于2和5。
而费马小定理是R^(P-1)-1  =nP （n∈N） 这个变形
R^(P-1)=NP+1 看到没有？ N就是K或者P  我猜是P也许是非K和非P
理论证明暂时到这里。不管了。

后来一看又有点类似蒙哥马利算法.呵呵