一个求乘法逆元的方法

一个求乘法逆元的方法
以下介绍一个素数求逆元的方法，与其它四种常见的求乘法逆元有所不同，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
求a在p中的逆，其中p为素数，按以下公式求余：
ar1≡q1(mod p) 其中ar1>p, a>q1
q1r2≡q2(mod p) 其中q1r2>p, q1>q2
q2r3≡q3(mod p) 其中q2r3>p, q2>q3
.
.
.
q(n-1)rn≡1(mod p) 其中q(n-1)rn>p, q(n-1)>1
以上相乘得：
arq1r2…q(n-1)rn≡q1q2*…1(mod p)
因假设p为素数，所以上式两边除q1q2…得：
a*(r1r2…rn)≡=1(mod p)
即:a与r1r2…*rn在p中互逆

例如
求24在83的逆元：
244≡13(mod 83)
137≡8 (mod 83)
811≡5 (mod 83)
517≡2 (mod 83)
242≡1 (mod 83)
471117*42≡45 (mod 83)
即24的逆元为45

求25在83的逆元：
254≡17(mod 83)
175≡2 (mod 83)
224≡1 (mod 83)
45*42≡10 (mod 83)
即25的逆元为10

求25在131的逆元：
256≡19 (mod 131)
197≡2 (mod 131)
266≡1 (mod 131)
67*66≡21 (mod 131)
即25的逆元为21

求34在131的逆元：
344≡5 (mod 131)
527≡4 (mod 131)
433≡1 (mod 131)
427*33≡27 (mod 131)
即34的逆元为27

程序如下：

#include <stdio.h>
main()
{
unsigned long a,b,n;
unsigned long r,q,res;

printf("输入两个数：\n");
scanf("%ld%ld", &a, &n);

b=a;
if( a > n )
{
   a=n;
   n=b;
}
res=1;
while(1)
{
   r=n/a;
   r++;
   q=r*a-n;
   res=(res*r)%n;
   if( q == 1 )
   {
      printf("%ld的逆%ld\n",b,res);
      printf("%ld*%ld=%ld(mod %ld)\n",b,res,(res*b)%n,n);
      break;
   }
   if( q == 0 || q == a )
   {
         printf("%ld存在因子%ld\n",n,a);
         break;
   }
   a=q;
}

}