 Modular multiplicative inverse

A modular multiplicative inverse of $a$ modulo $n$ is a residue $a^{-1}$ satisfying $a{a}^{-1}\equiv 1(\mathrm{mod}n)$. It exists exactly when $\gcd (a,n)=1$.

The modular multiplicative inverse of an integer \( a \) with respect to a modulus \( m \) is another integer \( x \) such that the product \( ax \equiv 1 \mod m \). In other words, when \( a \) is multiplied by \( x \) and then divided by \( m \), the remainder is 1.