數論中一個問題求解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);
}