I know that you can apply Euclid's Extended Algorithm, but I was wondering if there were "tricks" for guessing modular inverses. For example, if you have something like $ 13 \pmod{25}$ then you easily just guess $2$. But if you have something like $37 \pmod{12*18}$ is there a good way? I considered $6$, because 36 is one less than 37 and is a factor of 12*18, but that (obviously) gives $6$ not $1$. So are there other "tricks" for guessing modular inverses?
[Math] Tricks for Find Modular Inverses
modular arithmetic
Related Solutions
$bx\equiv a\pmod{\!m}$ has a unique solution $\!\iff\!b\,$ is coprime to the modulus $m$. If so, by Bezout $\,b\,$ is invertible $\!\bmod m,\,$ so scaling $\,bx\equiv a\,$ by $\,b^{-1}\,$ we obtain the unique solution $\,x\equiv b^{-1}a =: a/b.\,$ We can quickly compute $\,b^{-1}\pmod{\!m}\,$ by the extended Euclidean algorithm, but there are often more convenient ways for smaller numbers (e.g. here and here are a handful of methods applied). We describe a few such methods below, viewing $\, x\equiv b^{-1}a \equiv a/b\,$ as a modular fraction. [See here for the general method when the solution is not unique, i.e. when $\gcd(b,m)>1$].
The first, Gauss's algorithm, is based on Gauss's proof of Euclid's lemma via the descent $\,p\mid ab\,\Rightarrow\, p\mid a(p\bmod b).\,$ Generally it only works for prime moduli, but we can also execute the general extended Euclidean algorithm in fraction form too (using multi-valued "fractions").
It works by repeatedly scaling $\rm\:\color{#C00}{\frac{A}B}\overset{\times\ N} \to \frac{AN}{BN}\: $ by the least $\rm\,N\,$ with $\rm\, BN \ge 13,\, $ then reducing mod $13$
$$\rm\displaystyle \ mod\ 13\!:\,\ \color{#C00}{\frac{7}9} \,\overset{\times\ 2}\equiv\, \frac{14}{18}\, \equiv\, \color{#C00}{\frac{1}5}\,\overset{\times \ 3}\equiv\, \frac{3}{15}\,\equiv\, \color{#C00}{\frac{3}2} \,\overset{\times\ 7}\equiv\, \frac{21}{14} \,\equiv\, \color{#C00}{\frac{8}1}\qquad\!\! $$
Denominators of the $\color{#c00}{\rm reduced}$ fractions decrease $\,\color{#C00}{ 9 > 5 > 2> \ldots}\,$ so reach $\color{#C00}{1}\,$ (not $\,0\,$ else the denominator would be a proper factor of the prime modulus; it may fail for composite modulus)
Simpler: $ $ using $\rm\color{#0a0}{least}$ residues: $\displaystyle\ \ \frac{7}9\,\equiv\, \frac{7}{\!\color{#0a0}{-4}\!\ \,}\,\overset{\times\ 3}\equiv\,\frac{21}{\!\!-12\ \ \ \!\!}\,\equiv\, \color{#c00}{\frac{8}1}$
This optimization using $\rm\color{#0a0}{least\ magnitude}$ residues $\,0,\pm 1, \pm 2.\ldots$ often simplifies mod arithmetic. Here we can also optimize by (sometimes) cancelling obvious common factors, or by pulling out obvious factors of denominators, etc. For example
$$\frac{7}9\,\equiv\, \frac{\!-6\,}{\!-4\,}\,\equiv\frac{\!-3\,}{\!-2\,}\,\equiv\frac{10}{\!-2\,}\,\equiv\,-5$$
$$\frac{7}9\,\equiv\,\frac{\!-1\cdot 6}{\ \ 3\cdot 3}\,\equiv\,\frac{\!\,12\cdot 6\!}{\ \ \,3\cdot 3}\,\equiv\, 4\cdot 2$$
Or twiddle it as you did: $ $ check if quotient $\rm a/b\equiv (a\pm\!13\,i)/(b\pm\!13\,j)\,$ is exact for small $\rm\,i,j,\,$ e.g.
$$ \frac{1}7\,\equiv \frac{\!-12}{-6}\,\equiv\, 2;\ \ \ \frac{5}7\,\equiv\,\frac{18}{\!-6\!\,}\,\equiv -3$$
When working with smaller numbers there is a higher probability of such optimizations being applicable (the law of small numbers), so it's well-worth looking for such in manual calculations.
Generally we can choose a congruent numerator giving an exact quotient by Inverse Reciprocity.
$\bmod 13\!:\ \dfrac{a}{b}\equiv \dfrac{a-13\left[\color{#0a0}{\dfrac{a}{13}}\bmod b\right]}b\,\ $ e.g. $\,\ \dfrac{8}9\equiv \dfrac{8-13\overbrace{\left[\dfrac{8}{\color{#c00}{13}}\bmod 9\right]}^{\large\color{#c00}{ 13\ \,\equiv\,\ 4\ }}}9\equiv\dfrac{8-13[2]}9\equiv-2$
Note that the value $\,\color{#0a0}{x\equiv a/13}\,$ is exactly what we need to make the numerator divisible by $b,\,$ i.e.
$\qquad\quad\bmod b\!:\,\ a-13\,[\color{#0a0}x]\equiv 0\iff 13x\equiv a\iff \color{#0a0}{x\equiv a/13}$
This is essentially an optimization of the Extended Euclidean Algorithm (when it takes two steps).
Note $ $ Gauss' algorithm is my name for a special case of the Euclidean algorithm that's implicit in Gauss' Disquisitiones Arithmeticae, Art. 13, 1801. I don't know if Gauss explicitly used this algorithm elsewhere (apparently he chose to avoid use or mention of the Euclidean algorithm in Disq. Arith.). Gauss does briefly mention modular fractions in Art. 31 in Disq. Arith.
The reformulation above in terms of fractions does not occur in Gauss' work as far as I know. I devised it in my youth before I had perused Disq. Arith. It is likely very old but I don't recall seeing it in any literature. I'd be very grateful for any historical references.
See here for further discussion, including a detailed comparison with the descent employed by Gauss, and a formal proof of correctness of the algorithm.
Beware $ $ Modular fraction arithmetic is valid only for fractions with denominator coprime to the modulus. See here for further discussion.
Below we compare the related forms. First is the iterated descent $\,a\to 103\bmod a\,$ used by Gauss. Second is that rearranged into the form of descending multiples of $60.\,$ Third is the fractional view, and fourth is the graph of the descending multiples of $60$ (denominator descent graph).
$$\begin{align} 103\bmod{60} &= 103 - 1(60) = 43\\ 103\bmod 43 &= 103\color{#0a0}{-2(43)=17}\\ 103\bmod 17 &= 103-6(17) = 1 \end{align}\qquad\qquad\quad$$
$$\begin{array}{rl} \bmod{103}\!:\qquad\ (-1)60\!\!\!\! &\equiv\, 43 &\Rightarrow\ 1/60\equiv -1/43\\[.3em] \smash[t]{\overset{\large\color{#0a0}{*(-2)}}\Longrightarrow}\ \ \ \ \ \ \ \ \ \ (-2)(-1)60\!\!\!\! &\equiv \color{#0a0}{(-2)43\equiv 17}\!\! &\Rightarrow\ 1/60\equiv\ \ \ 2/17\\[.3em] \smash[t]{\overset{\large *(-6)}\Longrightarrow}\ \ \color{#c00}{(-6)(-2)(-1)}60\!\!\!\! &\equiv (-6)17\equiv 1 &\Rightarrow\ 1/60 \equiv {\color{#c00}{-12}}/1\\ \end{array}$$
$$ \begin{align} &\dfrac{1}{60}\ \,\equiv\ \ \dfrac{-1}{43}\, \ \equiv\, \ \dfrac{2}{17}\, \equiv\, \dfrac{\color{#c00}{-12}}1\ \ \ \rm[Gauss's\ algorithm]\\[.3em] &\, 60\overset{\large *(-1)}\longrightarrow\color{#0a0}{43}\overset{\large\color{#0a0}{*(-2)}}\longrightarrow\,\color{#0a0}{17}\overset{\large *(-6)}\longrightarrow 1\\[.4em] \Rightarrow\ \ &\,60*(-1)\color{#0a0}{*(-2)}*(-6)\equiv 1\ \Rightarrow\ 60^{-1}\rlap{\equiv (-1)(-2)(-6)\equiv \color{#c00}{-12}} \end{align}$$
The translation from the first form (iterated mods) to the second (iterated smaller multiples) is realized by viewing the modular reductions as modular multiplications, e.g.
$$\ 103\color{#0a0}{-2(43) = 17}\,\Rightarrow\, \color{#0a0}{-2(43) \equiv 17}\!\!\pmod{\!103} $$
This leads to the following simple recursive algorithm for computing inverses $\!\bmod p\,$ prime.
$\begin{align}\rm I(a,p)\ :=\ &\rm if\ \ a = 1\ \ then\ \ 1\qquad\qquad\ \ \ ; \ \ a^{-1}\bmod p,\,\ {\rm for}\ \ a,p\in\Bbb N\,\ \ \&\,\ \ 0 < a < p\ prime \\[.5em] &\rm else\ let\ [\,q,\,r\,]\, =\, p \div a\qquad ;\, \ \ p = q a + r\ \Rightarrow \color{#0a0}{-qa\,\equiv\, r}\!\!\pmod{\!p},\ \ 0 < r < a\,\\[.2em] &\rm\ \ \ \ \ \ \ \ \ ({-}q*I(r,p))\bmod p\ \ \ ;\ \ because\ \ \ \dfrac{1}a \equiv \dfrac{-q}{\color{#0a0}{-qa}}\equiv \dfrac{-q}{\color{#0a0}r}\equiv -q * I(r,p)\ \ \ \ \ \color{#90f}{[\![1]\!]} \end{align} $
Theorem $\ \ {\rm I(a,p)} = a^{-1}\bmod p$
Proof $\ $ Clear if $\,a = 1.\,$ For $\,a > 1,\,$ suppose for induction the theorem holds true for all $\,n < a$. Since $\,p = qa+r\,$ we must have $\,r > 0\,$ (else $\,r = 0\,\Rightarrow\,a\mid p\,$ and $\,1< a < p,\,$ contra $\,p\,$ prime). Thus $\,0 < r < a\,$ so induction $\,\Rightarrow\,{\rm I(r,p)}\equiv \color{#0a0}{r^{-1}}$ so reducing equation $\color{#90f}{[\![1]\!]}\bmod p\,$ yields the claim.
Best Answer
No guessing is needed. Both are easy using Gauss's algorithm
$\qquad{\rm mod}\ 25\!:\ \ \ \dfrac{1}{13}\equiv \dfrac{2}{26}\equiv \dfrac{2}1$
$\qquad {\rm mod}\ 216\!:\ \dfrac{1}{37}\equiv \dfrac{5}{185}\equiv \dfrac{5}{-31}\equiv\dfrac{35}{-217}\equiv\dfrac{35}{-1}$
You can find many more examples (and other methods) in prior posts. Note that Gauss's algorithm won't always work for composite moduli, and you must keep all denominators coprime to the modulus (that's why I chose $5$ vs. $6$ in the 2nd example). See the linked posts for further details.