Modular multiplicative inverse

general
1

Can someone explain to me how to get this formula in calculatin inverse of the number with respect to modulo :

int fac[N]={1,1};
int inv[N]={0,1};
int invfac[N]={1,1};

for(n=2;n<N;n++)
{
	fac[n]=LL(n)*fac[n-1]%MOD;
	inv[n]=LL(inv[MOD%n])*(MOD-MOD/n)%MOD;
	invfac[n]=LL(inv[n])*invfac[n-1]%MOD;
}

fac and invfac are clear to me. Problem is with inv[]. I know I can get this number qith little fermat’s theorem (inv[n] = n^(MOD-2) ), but I cant derive this equation - inv[n]=(inv[MOD%n])*(MOD-MOD/n)%MOD. If someone know how I can get it, please help me. Thanks.

2

let MOD be MOD=k*n+x, then:

x=-kn[mod MOD] and x=MOD%n

so we have: x=MOD*n-kn[mod MOD] => MOD%n=n*(MOD-k)[mod MOD]

k=MOD/n => MOD%n=n*(MOD-MOD/n)[mod MOD]

divide both sides by n*(MOD%n) and you have:

inv(n)=inv(MOD%n)*(MOD-MOD/n)[mod MOD]

6 Likes
3

Thank you :slight_smile:

4

Cool! That’s my code!

1 Like
5

Yes, you were tester for FEB12 :slight_smile: