need help with inverse modulo

[Guest_imported]

Hi, I'm trying to find a general way to find an inverse modulo. [e.g. inverse of 4(mod 9) is 7]. I'm implementing the Chinese Remainder Theorom, and finding an inverse modulo is a step that I have to do.
I would really appreciate any help.

Thank you.

tony_d

 

[Jeffray]

int r(int x,int y) {
int w = y, z=1;
while( x < w) {
int a = ( y / x ) + 1;
w = x;
x = a * x % y;
z = z * a % y;
}
return(z);
}

int im(int a,int b) {
int x = r(a,b);
int r = a * x % b;
if( r > 1) {
int z = im(r,a);
int k = (r * z - 1 ) / a;
x = x * z - k;
}
return(x % b );
}

void main(){
printf(&quot;%d&quot;, im(4,9));
}