Modular inversion
= Modular inversion
The computation of an <integer> $x$ satisfying $ax\equiv1\pmod m$. An inverse exists exactly when $\gcd(a,m)=1$. The <extended Euclidean algorithm> produces such an $x$ from a <Bezout identity> $ax+my=1$.
= Modular inversion
The computation of an <integer> $x$ satisfying $ax\equiv1\pmod m$. An inverse exists exactly when $\gcd(a,m)=1$. The <extended Euclidean algorithm> produces such an $x$ from a <Bezout identity> $ax+my=1$.