6 lines
173 B
Text
6 lines
173 B
Text
|
fcn gcdExt(a,b){
|
||
|
|
if(b==0) return(1,0,a);
|
||
|
|
q,r:=a.divr(b); s,t,g:=gcdExt(b,r); return(t,s-q*t,g);
|
||
|
|
}
|
||
|
|
fcn modInv(a,m){i,_,g:=gcdExt(a,m); if(g==1) {if(i<0)i+m} else Void}
|