3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 {\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 implies that if solutions exist then we can compute them by cancelling $\,d = (B,M)\,$ from the numerator $\,A,\,$ the denominator $\,B\,$ and the modulus $\,M,\,$ i.e.

$$ x\equiv \dfrac{ad}{bd}\!\!\!\pmod{\!md}\iff x\equiv \dfrac{a}b\!\!\!\pmod{\! m}$$

If $\, d>1\, $ the fraction $\, x\equiv A/B\pmod{\!M}\,$ is multiple-valued, denoting the $\,d\,$ solutions

$$\quad\ \begin{align} x \equiv a/b\!\!\pmod{\! m}\, &\equiv\, \{\, a/b + k\,m\}_{\,\large 0\le k<d}\!\!\pmod{\!M},\ \ M = md\\ &\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)\,=\,3}\!\!\!\!\equiv \dfrac{2}{1}\!\pmod{\!4}\equiv \!\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\{2,6,10\}}^{\qquad\ \ \,\Large\{ 2\ +\ 4k\}_{\ \Large 0\le k< 3}}\!\!\!\!\!\!\!\!\!\!\!\!\!\pmod{\!12}$

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.

$\endgroup$
2
$\begingroup$

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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.