Wednesday, May 29, 2019

elementary number theory - Solving $ax equiv c pmod b$ efficiently when $a,b$ are not coprime




I know how to compute modular multiplicative inverses for co-prime variables $a$ and $b$, but is there an efficient method for computing variable $x$ where $x < b$ and $a$ and $b$ are not co-prime, given variables $a$, $b$ and $c$, as described by the equation below?



$ a x \equiv c \mod b $



For example, given



$ 154x \equiv 14 \mod 182 $, is there an efficient method for computing all the possibilities of $x$, without pure bruteforce?



Please note that I'm not necessarily asking for a direct solution, just a more optimized one.




I do not believe that the Extended Euclidean Algorithm will work here, because $a$ and $b$ are not co-prime.



Edit:
Follow up question, since the first one had a shortcut:



Could the be computed efficiently as well?



$12260x \equiv 24560 \mod 24755$.



$107$ needs to be one of the computed answers.



Answer



Below we compute $\ x\,\equiv\, \dfrac{24560}{12260}\,\pmod{\!24755}\ $ per your edit, $ $ by the method in my first answer.



${\rm mod}\,\ 24755\!:\,\
\dfrac{0}{24755}\overset{\large\frown}\equiv
\dfrac{24560}{12260}\overset{\large\frown}\equiv
\color{#90f}{\dfrac{390}{235}}\overset{\large\frown}\equiv
\color{#0a0}{\dfrac{4280}{40}}\overset{\large\frown}\equiv
\color{#c00}{\dfrac{-535}{-5}}\overset{\large\frown}\equiv\dfrac{0}0$




$ \begin{array}{rl}
\ \ \ \ {\rm i.e.}\ \ \ \ \bmod 24755\!: \ \ \ \ \ [\![1]\!] &\ 24755\, x\,\equiv\ 0\ \\
[\![2]\!] &\ \color{c00}{12260\,x\, \equiv\ 24560\equiv -195}\!\!\!\\
[\![1]\!]\:\!-\:\!2\,[\![2]\!] \rightarrow [\![3]\!] &\ \ \ \ \ \color{#90f}{235\,x\, \equiv\ 390}\ \\
[\![2]\!]\!-\!\color{1orange}52\,[\![3]\!] \rightarrow [\![4]\!] &\ \ \ \ \ \ \, \color{#0a0}{40\,x\, \equiv\ 4280}\ \\
[\![3]\!]\:\!-\:\!\color{}6\,[\![4]\!] \rightarrow [\![5]\!] &\:\! \ \ \ \ \ \color{#c00}{{-}5\,x\, \equiv -535}\ \\
[\![4]\!]\:\!+\:\!\color{1orange}8\,[\![5]\!] \rightarrow [\![6]\!] &\:\!\ \ \ \ \ \ \ \ \color{90f}{0\,x\, \equiv\ 0}\
\end{array}$



$\begin{align}{\rm Therefore}\ \ \ x\equiv {\color{#c00}{\dfrac{535}5}\!\!\!\pmod{24755}}&\equiv \,107\!\!\pmod{\!4951},\ \ {\rm via\ canceling}\ \ 5\\ &\equiv\, 107+4951k\!\!\pmod{\!24755},\ \ 0\le k\le 4\\[0.5em]

&\equiv \{107,\, 5058,\, 10009,\, 14960,\, 19911\}\!\pmod{\!24755}\end{align} $


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