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

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

which is true because $$\ km\bmod dm =\, (\color{#c00}{k\bmod d})\, m\$$ by the mod Distributive Law,  and the RHS takes exactly $$\,d\,$$ values, namely $$\,\color{#c00}0m,\, \color{#c00}1m,\, \color{#c00}2m, \ldots, (\color{#c00}{d\!-\!1})m,\,$$ so ditto for their shifts by $$\,a/b$$.

$${\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.

You can cancel a factor common to both sides of a congruence AND the modulus. The justification for this is that for any non-zero integer $d$ we have $dm\mid (da-db)$ if and only if $m\mid (a-b)$. Written as congruences this reads $$da\equiv db\pmod{dm}\Longleftrightarrow a\equiv b\pmod m.$$

So for example the congruence $$6x\equiv 8\pmod {10}$$ is equivalent to the the congruence $$3x\equiv4\pmod5.$$ This time you ended with a linear congruence where the coprimeness condition $\gcd(3,5)=1$ holds, and you can proceed to solve this congruence with the usual methods.

Observe also that it is often easy to show that a linear congruence has no solutions when to gcd-condition fails. Consider $$6x\equiv 7\pmod{10}.$$ Here $6x$ is always even, as is $10$, but $7$ is not. Therefore this congruence cannot have any solutions in $\Bbb{Z}$.

• This is surely a dupe, but I didn't find a good target. Turning to CW. – Jyrki Lahtonen Aug 29 '17 at 9:58