<s>[INST] Finding Modular Multiplicative Inverses (Quickly!) as part of an upcoming number theory exam I will need to find the modular multiplicative inverse of every element of ${Z_n}$ (the ones that exist anyway) very quickly. The only way I know is using the Extended Euclidean Algorithm. Is there no way that is faster? The question isn't worth many marks but will take an inordinate amount of time.
 [/INST] Solve $ax \equiv 1 \pmod{n}$
I would tackle these problems keeping this trick in mind and applying the basic tactic of making $a$ smaller by 'multiplying to the modulus'.
Example 1: Solve $12x \equiv 1 \pmod{19}$.
$\; 12x \equiv 1 \pmod{19} \; \text{ iff}$
$\; -7x \equiv 1 \pmod{19}$
and
$\;-7 \cdot (3) \equiv -21 \equiv -2 \pmod{19}$
$\;-2 \cdot (9) \equiv -18 \equiv 1 \pmod{19}$
and therefore the solution is given by $x \equiv 3 \cdot 9 \equiv 8 \pmod{19}$.
Example 2: Solve $67x \equiv 1 \pmod{97}$.
$\; 67x \equiv 1 \pmod{97} \; \text{ iff}$
$\; -30x \equiv 1 \pmod{97}$
and
$\;-30 \cdot (3) \equiv -90 \equiv 7 \pmod{97}$
$\;7 \cdot (14) \equiv 98 \equiv 1 \pmod{97}$
and therefore the solution is given by $x \equiv 3 \cdot 14 \equiv 42 \pmod{19}$.
Example 3: Solve $7x \equiv 1 \pmod{23}$.
$\;7 \cdot (4) \equiv 5 \pmod{23}$
$\;5 \cdot (5) \equiv 2 \pmod{23}$
$\;2 \cdot (12) \equiv 1 \pmod{23}$
and therefore the solution is given by $x \equiv 4 \cdot 5 \cdot 12 \equiv 10 \pmod{23}$.
Example 4: Solve $6x \equiv 1 \pmod{10}$.
$\; 6x \equiv 1 \pmod{10} \; \text{ iff}$
$\; -4x \equiv 1 \pmod{10}$
and
$\;-4 \cdot (2) \equiv 2 \pmod{10}$
$\;2 \cdot (5) \equiv 0 \pmod{10}$
If $6x \equiv 1 \pmod{10}$ then $5 \cdot (6x) \equiv 5 \pmod{10}$, so there are no solutions.
</s>