Sunday, May 1, 2016

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 xA/B(modM), i.e. the solutions of  BxA(modM). Let d=gcd(B,M). Then dB, dMBxAdA  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



xAB(modM)MBxA  cancel dmbxaxab(modm)



where the fraction  xa/b(modm) denotes all solutions of axb(modm), and similarly for the fraction  xA/B(modM). 



The above argument implies that if solutions exist then we can compute the complete solution set by cancelling d=(B,M) from the numerator A, the denominator B 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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...