数论中一个问题求解c语言实现.txt

c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了搜罗的,希望大家喜欢.

数论中一个问题求解C语言实现[原创] 
如果两个数a和M互素，则存在整数m和n，使得a*m+M*n=1。

对结论做整理得：a*m-1=(-n)*M，即a*m≡1 (mod M)，即同余式。从而可以很容易求得m，进而根据a*m+M*n=1求得n。

代码如下：

int gcd(int a,int M)
{
  int r;
  if(a<0||M<0)
  {
    printf("\nDATA ERROR for p&q\n");
    exit(-1);
  }
  while((r=a%M)!=0)
  {
    a=M;
    M=r;
  }
  return M;
}
void ceshi(int a,int M,int *m,int *n)
{
  int p,q;
  if(gcd(a,M)!=1)
  {
     printf("\nDATA ERROR\n");
     exit(-1);
  }
  p=1;
  while((p*a)%M!=1)
       p++;
  q=1;
  while((p*a+q*M)!=1)
       q++;
  *m=p;
  *n=q;
}

void main()
{
   int a,M,m,n;
   a=3;
   M=11;
   ceshi(a,M,&m,&n);
   printf("\nm=%d;n=%d\n",m,n);
   printf("\n%d*%d+%d*%d=%d\n",a,m,M,n,a*m+M*n);
}