设(p=k imes i+r(0leq r<i,1<i<p))
[k imes i+requiv0(mod p)
]
两端同乘(i^{-1} imes r^{-1})得
[egin{align}
k imes r^{-1}+i^{-1}&equiv 0pmod p\
i^{-1}&equiv-k imes r^{-1}pmod p
end{align}
]
递推公式为:
[inv[i] = egin{cases}
1, & i=1\
-(p/i) imes inv[p\%i], &1<i<p
end{cases}
]