elementary number theory - Modular arithmetic: division, fractions, solving linear congruences

I want to ask a question about modular arithmetic. I know, that modular multiplicative inverse exists only if modulo and integer are relatively prime. I want to know, are there any ways of division in modular arithmetic, if modulo and integer aren't relatively prime? I tried to find info about that, but failed.

Answer

Below I explain how to view modular division via (possibly multiple-valued) modular fractions.

Consider $\,x\equiv A/B\pmod{\!M},\,$ i.e. the solutions of $\ B\, x \equiv A\pmod{\!M}.\, $ Let $\,d=\gcd(B,M).\,$ Then $\, d\mid B,\,\ d\mid M\mid B\,x\!-\!A\,\Rightarrow\, d\mid A\ $ is a neccessary condition for existence of solutions.

If so, let $\ m, a, b \, =\, M/d,\, A/d,\, B/d.\ $ Then cancelling $\,d\,$ throughout yields

$$ x\equiv \dfrac{A}B\!\!\!\pmod{\!M}\iff M\mid B\,x\!-\!A\!\! \overset{\large {\ \ \color{#c00}{{\rm cancel}\ d}}}\iff m\mid b\,x\! -\! a \iff x\equiv \dfrac{a}b\!\!\!\pmod{\!m}$$

where the fraction $\ x\equiv a/b\pmod{\! m}\,$ denotes all solutions of $\,ax\equiv b\pmod{\! m},\, $ and similarly for $\, $ the $\, $ fraction $\ x\equiv A/B\pmod{\!M}.\ $

The above argument implies that if solutions exist then we can compute the complete solution set by $\color{#c00}{{\rm cancelling}\ d} = (B,M)\,$ from the numerator $\,A,\,$ the denominator $\,B\,$ $\rm\color{#c00}{and}$ the modulus $\,M,\,$ i.e.

$$ \bbox[8px,border:1px solid #c00]{x\equiv \dfrac{a\color{#c00}d}{b\color{#c00}d}\!\!\!\pmod{\!m\color{#c00}d}\iff x\equiv \dfrac{a}b\!\!\!\pmod{\! m}}\qquad$$

If $\, d>1\, $ then $\, x\equiv A/B\pmod{\!M}\,$ is multiple-valued, having $\,d\,$ solutions in AP, namely

$$\quad\ \begin{align} x \equiv a/b\!\!\pmod{\! m}\, &\equiv\, \{\, a/b + k\,m\}_{\,\large 0\le k&\equiv\, \{a/b,\,\ a/b\! +\! m,\,\ldots,\, a/b\! +\! (d\!-\!1)m\}\!\!\pmod{\! M}
\end{align}$$
$ {\rm e.g.} \overbrace{\dfrac{6}3\pmod{\!12}}^{{\rm\large cancel}\ \ \Large (3,12)\,=\,\color{#c00}3}\!\!\!\!\equiv \dfrac{2}{1}\!\pmod{\!4}\equiv \!\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\{2,6,10\}}^{\qquad\ \ \,\Large\{ 2\ +\ 4k\}_{\ \Large 0\le k< 3}}\!\!\!\!\!\!\!\!\!\!\!\!\!\pmod{\!12},\ $ indeed $\ 3\{2,6,10\}\equiv \{6\}$

Note in particular that a modular "fraction" may denote zero, one, or multiple solutions.

---

Remark $ $ A nice application of modular fractions is the fractional extended Euclidean algorithm described in the Remark here. There you'll find explicit examples of the intersection of solution sets of multiple-valued modular fractions.