Calculating the Modular Multiplicative Inverse without all those strange looking symbols

"Particularly, I had a hard time knowing why the (mod m) was off to the right and separate, and I am still not sure what the triple-lined equals symbol is all about."

The notation $(57 \equiv 62) \pmod 5$ means $57$ and $62$ are congruent to each other modulo $5$, i.e. they both leave the same remainder on division by $5$. See Modular arithmetic. That notation was introduced by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae published in 1801, and has been standard since that time.

Later when computer programmers started doing modular arithmetic, they introduced a new notation: $57 \bmod 5$ means the remainder when $57$ is divided by $5$.

Just remember which notation is which and don't confuse them with each other.

The Wikipedia article might benefit from a concrete example or two.

Alright, suppose you want the inverse of $322$ when the modulus is the prime number $701$. Since $701$ is prime, the gcd of $701$ and any number that is not a multiple of $701$ is $1$. We will see that this implies there is a solution to the Diophantine equation $701x+322y=1$ (and if the gcd were something other than $1$, there would be a solution if instead of "$=1$" we put "$=\text{whatever that other number is}$").

So apply the Euclidean algorithm, but remember the quotients. Divide 701 by $322$; get a quotient of $2$ and a remainder of $57$: $$ 701-2\cdot322 = [57]. $$ In Euclid's algorithm, we would next divide $322$ by $57$, getting a quotient of $5$ and a remainder of $37$: $$ 322 - 5\cdot [57] = [37]. $$ Then divide 57 by 37, getting a quotient of $1$ and a remainder of $20$: $$ [57] - 1\cdot[37] = [20]. $$ Divide 37 by 20, getting a quotient of $1$ and a remainder of $17$: $$ [37]-1\cdot[20] = [17]. $$ Divide $20$ by $17$, getting a quotient of 1 and a remainder of $3$: $$ [20]-1\cdot[17]=[3]. $$ Divide $17$ by $3$, getting a quotient of $5$ and a remainder of $2$: $$ [17]-5\cdot[3]=[2]. $$ Divide $3$ by $2$, getting a quotient of $1$ and a remainder of $1$: $$ [3] -1\cdot[2]=[1]. $$ So according to Euclid's algorithm, the gcd is $1$, and if that is all we wanted, we'd have needed only the remainders and not the quotients. But now we use the results above it solve $701x+322y=1$. This will imply that $(322y\equiv1)\pmod {701}$, i.e. the multiplicative inverse of 322 is $y$, when the modulus is $701$.

I've put square brackets around the numbers found to be REMAINDERS but NOT around the QUOTIENTS.

In place of the remainder $2$, in the last line, put the expression found to be equal to $2$ in the line before it: $$ \begin{align} [3]-1\cdot[2] & = [1] \\ {[}3{]}-1([17]-5\cdot[3]) & = [1] \end{align} $$ Simplify, getting linear combination of REMAINDERS: $$ 6[3]-1[17] =1. $$ Now in place of the remainder $3$, put the expression found to be equal to it: $$ 6([20]-1[17])-1[17] = 1. $$ Simplify, getting linear combination of REMAINDERS: $$ 6[20]-7[17] = 1. $$ Now in place of the remainder $17$, put the expression found to be equal to it: $$ 6[20] - 7([37]-1[20])=1. $$ Simplify, getting linear combination of REMAINDERS: $$ 13[20]-7[37]=1. $$ Now in place of the remainder $20$, put the expression found to be equal to it: $$ 13([57]-1[37])-7[37]=1. $$ Simplify, getting linear combination of REMAINDERS: $$ 13[57]-20[37]=1. $$ Now in place of the remainder $37$, put the expression found to be equal to it: $$ 13[57]-20(322-5[57])=1. $$ Simplify, getting linear combination of REMAINDERS: $$ 113[57]-20[322]=1. $$ Now in place of the remainder $57,$ put the expression found to be equal to it: $$ 113([701]-2[322])-20[322]=1. $$ Simplify, getting linear combination of REMAINDERS: $$ 113[701]-246[322]=1. $$ THEREFORE $(-246\cdot322\equiv1) \pmod{701}$.

Or in other words $(455\cdot322 \equiv1)\pmod{701}$.

So modulo $701$, the multiplicative inverse of $322$ is $455$.

Here's old JS code I had for computing the modular inverse of a with respect to the modulus m, based on a modification of the usual Euclidean algorithm. I must admit that I've forgotten the provenance of this algorithm, so I'd appreciate if somebody could point me to where this modification first appeared:

function modinv(a,m) {
    var v = 1;
    var d = a;
    var u = (a == 1);
    var t = 1-u;
    if (t == 1) {
        var c = m % a;
        u = Math.floor(m/a);
        while (c != 1 && t == 1) {
               var q = Math.floor(d/c);
               d = d % c;
               v = v + q*u;
               t = (d != 1);
               if (t == 1) {
                   q = Math.floor(c/d);
                   c = c % d;
                   u = u + q*v;
               }
        }
        u = v*(1 - t) + t*(m - u);
    }
    return u;
}

Consider the element $a \in \mathbb{Z}/m\mathbb{Z}$. It is not hard to show that $a^{-1}$ exists in $\mathbb{Z}/m\mathbb{Z}$ if and only if the gcd of $a$ and $m$ is 1, that is, $a$ and $m$ are coprime. Using Euler's theorem (also sometimes called Fermat's theorem), $a^{\varphi(m)} \equiv 1 \pmod{m}$ for all $a$ coprime to $m$ where $\varphi(m)$ is Euler's totient function. Therefore $$a^{-1} \equiv a^{\varphi(m) - 1} \pmod{m}.$$

So I guess an pseudo-algorithm for computing the inverse of $a \in \mathbb{Z}/m\mathbb{Z}$ could be:

1. Compute the gcd of $a$ and $m$. If this is not equal to 1, exit. Else continue.
2. Compute $\varphi(m)$. One way is to count the number of integers less than $m$, relatively prime to $m$, another way is to use $m$'s prime factorization. There are other much faster ways I think, but these two methods are the most obvious ones.
3. Compute $a^{\varphi(m) - 1}$.
4. Reduce mod $m$.
5. Repeat Step 4 until the result is in $\{0, 1, \ldots, m - 1\}$.