Calculating the Modular Multiplicative Inverse without all those strange looking symbols I am sure all those symbols are really easy for you guys to understand, but I would appreciate it if someone could bring it down to earth for me.
How could I do this on a basic calculator? or with a few lines of programmer's code which probably would look strange to you :)
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. Not that I care, but if it is simple, I don't mind reading it that way, if not, I would prefer calculator instructions.
 A: 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;
}

A: 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:


*

*Compute the gcd of $a$ and $m$. If this is not equal to 1, exit. Else continue.

*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.

*Compute $a^{\varphi(m) - 1}$.

*Reduce mod $m$.

*Repeat Step 4 until the result is in $\{0, 1, \ldots, m - 1\}$.

A: One need not understand congruence arithmetic to understand the extended Euclidean algorithm as applied to computing modular inverses. By Bezout's Identity there are integers $\rm\:x,y\:$ such that $\rm\:m\ x + n\ y\:=\:gcd(m,n) = 1\:,\:$ i.e. $\rm\ n\ y = 1 - m \ x\:.\:$ So, mod $\rm\:m\!:\ n\ y = 1\ \Rightarrow\ y = 1/n\:.\:$ To compute $\rm\:x,y\:$ one may use an extended form of the Euclidean algorithm that is analogous to identity-augmented elimination in linear algebra, e.g. see below from one of my old posts.
For example, to solve  m x + n y = gcd(m,n) one begins with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,

Here is an example:  d =  x(80) + y(62)  proceeds as:

                      in equation form   | in row form
                    ---------------------+------------
                    80 =   1(80) + 0(62) | 80   1   0
                    62 =   0(80) + 1(62) | 62   0   1
 row1 -   row2  ->  18 =   1(80) - 1(62) | 18   1  -1
 row2 - 3 row3  ->   8 =  -3(80) + 4(62) |  8  -3   4
 row3 - 2 row4  ->   2 =   7(80) - 9(62) |  2   7  -9
 row4 - 4 row5  ->   0 = -31(80) -40(62) |  0 -31  40

Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,

        row1 row2 row3 row4 row5
namely:  80,  62,  18,   8,   2  = Euclidean remainder sequence
               |    |
for example   62-3(18) = 8, the 2nd step in Euclidean algorithm

becomes:   row2 -3 row3 = row4  on the identity-augmented matrix.


In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:

         [  7 -9] [ 80  1  0]  =  [2   7  -9]
         [-31 40] [ 62  0  1]     [0 -31  40]

row 1 is the particular  solution  2 =   7(80) -  9(62)
row 2 is the homogeneous solution  0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:

       n row1 + m row2  ->  2n = (7n-31m) 80 + (40m-9n) 62

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field, 
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form, 
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.

A: There is an algorithm besides the extended Euclidean algorithm that can be used to solve
$\tag 1 ax \equiv b \pmod{p} \quad \text{where } p \text{ is prime} \land p \nmid a \land p \nmid b$
An outline for the algorithm's logic was given here.
Here is a Python program that calculates $3789 x \equiv  1234 \pmod{7919}$; it ends with
$\tag {ANS} 3789 x \equiv  1234 \pmod{7919} \; \text{ iff } \; x \equiv 4498 \pmod{7919}$
We take the output of the program and paste it into our Latex interpreter:
Multiply by $ 2 $:
$\quad 7578 x \equiv 2468 \pmod{7919}$
$\quad -341 x \equiv 2468 \pmod{7919}$
$\quad 341 x \equiv 5451 \pmod{7919}$
Multiply by $ 23 $:
$\quad 7843 x \equiv 125373 \pmod{7919}$
$\quad -76 x \equiv 6588 \pmod{7919}$
$\quad 76 x \equiv 1331 \pmod{7919}$
Multiply by $ 104 $:
$\quad 7904 x \equiv 138424 \pmod{7919}$
$\quad -15 x \equiv 3801 \pmod{7919}$
$\quad 15 x \equiv 4118 \pmod{7919}$
Multiply by $ 528 $:
$\quad 7920 x \equiv 2174304 \pmod{7919}$
$\quad 1 x \equiv 4498 \pmod{7919}$
Python Program
a = 3789
b = 1234
p = 7919

while 1:
    q, r = divmod(p,a)
    s_L = q * a
    s_R = (q + 1) * a
    M = q
    left = True
    if p - s_L > s_R - p:
        M = q + 1
        left = False
    print()
    print('Multiply by $', M,'$:',)
    print()
    print('$\quad', M*a, 'x \equiv', M*b, '\pmod{7919}$<br>')
    if left:
        a = M*a - p
        b = M*b % p
        print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')
        a = -a
        b = -b % p
        print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')        
    else:
        a = M*a - p
        b = M*b % p
        print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')
    if a == 1:
        break

raise SystemExit

