Alternative way of calculating the multiplicative inverse Suppose I want to find the inverse of $7^{-1} \equiv 1 \mod 19 $, is there a quick way to do instead of extended euclidean algorithm? (Assume the numbers are not large).
Thank you
 A: ${\rm mod}\ 19\!:\,\ \dfrac{1}7\equiv \dfrac{3}{21}\equiv\dfrac{22}{2}\equiv 11\ $ by Gauss's algorithm. $ $  Alternatively
${\rm mod}\ 19\!:\,\ \dfrac{1}7\equiv \dfrac{1}{-12}\equiv\dfrac{\color{#0a0}{-1}}3\,\dfrac{\color{#c00}1}4\equiv\dfrac{\color{#0a0}{18}}3\,\dfrac{\color{#c00}{20}}4\equiv 6\cdot5\equiv 11 $
The extended Euclidean algorithm is also easier in fraction form
${\rm mod}\ 19\!:\,\ \dfrac{0}{19}\overset{\large\frown}\equiv\dfrac{1}7\overset{\large\frown}\equiv\dfrac{-3}{-2}\overset{\large\frown}\equiv\dfrac{11}1\quad $  [see this answer
 for the algorithm]
Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.
A: Yeah, the way most people do it in competitive programming is as follows:
Suppose you have a number $k$ that is coprime to $n$ and you want to find the inverse of $k$ mod $n$. Then it is just $k^{\varphi(n)-1}$.
You can calculate this really fast using exponentiation by squaring.
A: I sometimes look at the two multiples that straddle the modular base.
$\color{blue}{2}\cdot 7 = 14 \equiv \color{green}{-5} \bmod 19 \\
\color{orange}{3} \cdot 7 = 21 \equiv \color{red}{2} \bmod 19 $
And then combine those to get the inverse:
$1\cdot \color{green}{-5}  + 3\cdot \color{red}{2} = 1 \\
\implies (1\cdot \color{blue}{2}+ 3\cdot \color{orange}{3}) \cdot 7  \equiv 1 \bmod 19 \\
\implies  7^{-1}  \equiv 11 \bmod 19$
