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

Could the be computed efficiently as well?

$12260x \equiv 24560 \mod 24755$.

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

• It is more accepted notation to ask about solutions to $154x \equiv 14 \bmod{182}$. In any case the first step is almost always to factor the modulus ($182$ in this case) into its prime power factors ($182 = 2\cdot 91$). – hardmath Dec 10 '16 at 23:06
• After factorng the modulus into prime powers, in this case $2*7*13$, solve in each factor and then use the Chinese remainder theorem. – Scott Burns Dec 10 '16 at 23:13
• Could you possibly demonstrate that in more detail? Utilizing the Chinese Remainder Theorem to solve this equation? And correct me if I am wrong, but I thought that the Chinese Remainder Theorem only applied to values that are co-prime. – Jesse Daniel Mitchell Dec 10 '16 at 23:21

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\!: \ \ \ \ \ [\!\!] &\ 24755\, x\,\equiv\ 0\ \\ [\!\!] &\ \color{c00}{12260\,x\, \equiv\ 24560\equiv -195}\!\!\!\\ [\!\!]\:\!-\:\!2\,[\!\!] \rightarrow [\!\!] &\ \ \ \ \ \color{#90f}{235\,x\, \equiv\ 390}\ \\ [\!\!]\!-\!\color{1orange}52\,[\!\!] \rightarrow [\!\!] &\ \ \ \ \ \ \, \color{#0a0}{40\,x\, \equiv\ 4280}\ \\ [\!\!]\:\!-\:\!\color{}6\,[\!\!] \rightarrow [\!\!] &\:\! \ \ \ \ \ \color{#c00}{{-}5\,x\, \equiv -535}\ \\ [\!\!]\:\!+\:\!\color{1orange}8\,[\!\!] \rightarrow [\!\!] &\:\!\ \ \ \ \ \ \ \ \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 by\ canceling}\ \ 5\ \ \rm\color{darkorange}{everywhere}\\ &\equiv\, 107+4951k\!\!\pmod{\!24755},\ \ 0\le k\le 4\\[0.5em] &\equiv \{107,\, 5058,\, 10009,\, 14960,\, 19911\}\!\pmod{\!24755}\end{align}

Solving $154x \equiv 14 \pmod{182}$ is the same as finding all solutions to $$154x + 182y = 14.$$ In this case, we might think of this as finding all solutions to $$14(11x + 13y) = 14(1),$$ or rather $$11x + 13 y = 1.$$ Finally, solving this is the same as solving $11x \equiv 1 \pmod {13}$, which has solution $x \equiv 6 \pmod{13}$.

So we learn that $x \equiv 6 \pmod{13}$ is the solution. Of course, this isn't a single residue class mod $182$. Thinking modulo $182$, we see that the solutions are $x \equiv 6, 6+13,6+26,6+39, \ldots, 6+13*13 \equiv 6, 19, 32, \ldots, 175.$

This approach works generally --- factor out the greatest common divisor, consider the resulting modular problem, and then bring it back up to the original problem.

• I really like this solution. I'm going to experiment with it a bit more with it, but I believe that this is what I was looking for. – Jesse Daniel Mitchell Dec 10 '16 at 23:40
• @JesseDanielMitchell It's worth mentioning that to be able to solve an equation $ax+by = c$, you must have $\text{gcd}(a,b)$ divides $c$. When you can get it to the point that mixedmath did ($11x+13y = 1$, where $11,13$ are coprime) we have that the gcd is $1$, and this divides everything, and we're done. If after trying to reduce it ended up being $12x+14y = 1$, this would clearly have no solutions, and the formal reason for this is because $\text{gcd}(12,14)\nmid 1$. – Mark Dec 10 '16 at 23:53
• @Mark thank you for pointing that out. Is there another approach for computing these numbers if the $\gcd(a,b) ∤ 1$? For example, $12260x \equiv 24560 \mod 24755$. (107 needs to be one of the computed answers). – Jesse Daniel Mitchell Dec 11 '16 at 0:30
• @JesseDanielMitchell Generically, the approach in this answer works everytime if there are actually solutions. If there are no solutions, then of course there will be no algorithm to produce solutions. – davidlowryduda Dec 11 '16 at 1:44

Note $$\ \gcd( 154,182)=\color{#c00}{14}\,$$ so factoring it out and cancelling it yields

$$\color{#c00}{14}\cdot 13\,\mid\, \color{#c00}{14}\,(11x\!-\!1)\!\!\overset{\rm\ \ cancel\ \color{#c00}{14}_{\phantom{I_I}}\!\!\!\!}\iff\ 13\mid 11x\!-\!1\iff {\rm mod}\ \ 13\!:\ x\equiv \dfrac{1}{11}\equiv \dfrac{-12}{-2}\equiv 6\qquad$$

Below I derive the general solution in fractional form, which often greatly simplifies matters. Then I show how to present the extended Euclidean algorithm succinctly using these (multi-valued) modular fractions. See my other answer above for how this method applies to the OP.

Generally let's consider the solution of $$\ B\, x \equiv A\pmod{\! M}.\$$ If $$\,d=(B,M)\,$$ then $$\, d\mid B,\,\ d\mid M\mid B\,x\!-\!A\,\Rightarrow\, d\mid A\$$ is a necessary condition for a solution $$\,x\,$$ to exist.

If so let $$\ m, a, b \, =\, M/d,\, A/d,\, B/d.\$$ Cancelling $$\,d\,$$ $$\rm\color{darkorange}{everywhere}$$ i.e. from $$\,A,B\,$$ & $$M$$ yields

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

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}.\$$ Note there may be zero, one, or multiple solutions.

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

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

where $$\bmod m\!:\ a/b = ab^{-1}\,$$ uniquely exists as $$\,b^{-1}\,$$ does, by $$\,(b,m)=1$$.

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

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)\,=\,3}\!\!\!\equiv\, \dfrac{2}{1}\!\pmod{\!4}\,\equiv\, \!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\{2,6,10\}}^{\qquad\ \ \Large\{ 2\,+\,4k\}_{\ \Large 0\le k< 3}}\!\!\!\!\!\!\!\!\!\!\!\!\!\pmod{\!12}$$

Remark  Such multiple-valued fractions frequently arise in the extended Euclidean algorithm when performed in fractional form. Let's use it to compute $$\, x\equiv \color{#0a0}{9/5}\pmod{\!18}.\,$$ We obtain

$${\rm mod}\ 18\!:\ \ \ \underbrace{\overbrace{\dfrac{0}{18}\overset{\large\frown}\equiv \color{#0a0}{\dfrac{9}5} \overset{\large\frown}\equiv \dfrac{9}3}^{\Large\ \ 0\,-\,3(\color{#0a0}9)\ \equiv\ 9\ }}_{\Large 18\,-\,3(\color{#0a0}5)\ \equiv\ 3}\overset{\large\frown}\equiv \dfrac{0}{2}\overset{\large\frown}\equiv \color{#c00}{\dfrac{9}{1}}\overset{\large\frown}\equiv\dfrac{0}0\qquad\quad$$

so $$\ {\rm mod}\ 18\!:\ x\equiv\color{#0a0}{9/5}\equiv\color{#c00}{ 9/1}\equiv 9.\,$$ Checking $$\, 5x\equiv 5\cdot9\equiv 45\equiv 9,\,$$ is indeed true.

Above each Euclidean reduction step essentially mods out successive denominators as follows

$$\dfrac{a}{b}\overset{\large\frown}\equiv\dfrac{c}d\overset{\large\frown}\equiv\dfrac{a-qc}{b-qd}\ \ {\rm where}\ \ q = \lfloor b/d \rfloor,\ \ {\rm so }\ \ b\!-\!qd = b\bmod d$$

i.e. the denominators are the values occurring in Euclid's algorithm for $$\,\gcd(18,\color{#0a0}5),\,$$ but we perform those operations in parallel on the numerators too, e.g. the first step above has $$\, q =\lfloor 18/\color{#0a0}5\rfloor = 3\,$$ so the denominator is $$\, 18-3(\color{#0a0}5)\equiv 3.\,$$ Executing the same operation on the numerators yields the next numerator, namely: $$\ 0-3(\color{#0a0}9)\equiv 9.\,$$ The following steps proceed the same way, but all quotients (except final $$\,q=2)$$ are $$\,q=1,\,$$ so we simple subtract successive numerators and denominators.

The invariant in the algorithm is that the common solutions of each neighboring pair of fractions remains constant. It starts as the common solution of $$\,0/18\overset{\large\frown}\equiv 9/5$$ $$\,:= 18x\equiv 0,\ 5x\equiv 9.\,$$ which is equivalent to $$\,5x\equiv 9,\,$$ since $$\,18x\equiv 0\,$$ is true for all $$\,x\,$$ by $$\,18\equiv 0.\,$$ Similarly it ends with the common solution of $$\,9/1 \overset{\large\frown}\equiv 0/0\,$$ $$:= 1x\equiv 9,\ 0x\equiv 0,\,$$ and again the latter can deleted.

The proof that the Euclidean reduction preserves the solution set is as follows.

$$\qquad\ \$$ If $$\,\ dx\!-\!c \equiv 0\,\$$ then $$\,\ bx\!-\!a \equiv 0\! \iff\! \overbrace{(bx\!-\!a)-q(dx\!-\!c)}^{\Large (b-qd)\,x\,-\,(a-qc)}\!\equiv 0$$

This immediately implies that \ \ \begin{align}bx&\equiv a\\ dx&\equiv c\end{align} \!\iff\!\! \begin{align}(b\!-\!qd)x&\equiv a\!-\!qc\\ dx&\equiv c\end{align}

It is instructive to look at the intermediate system $$\, 9/3\overset{\large\frown}\equiv 0/2.\,$$ By above we know that

\begin{align} &\overbrace{\dfrac{9}3\!\!\!\pmod{\!18}}^{{\rm\large cancel}\ \ \Large (3,18)\,=\,3}\!\!\!\equiv\, \dfrac{3}{1}\!\!\!\pmod{\!6}\,\equiv\, \{3,\color{#c00}9,15\}\!\!\!\pmod{\!18} \\[.7em] & \underbrace{\dfrac{0}2\!\!\!\pmod{\!18}}_{{\rm\large cancel}\ \ \Large (2,18)\,=\,2}\!\!\!\equiv\, \dfrac{0}{1}\!\!\!\pmod{\!9}\,\equiv\, \{0,\color{#c00}9\}\ \ \ \pmod{\!18} \end{align}\quad\ \

Notice that the common solution of both is indeed $$\,\ x\equiv \color{#c00}9\pmod{\!18},\,$$ as we found above. Note also that even though we started with a fraction $$\,9/5\,$$ whose denominator $$\,5\,$$ is coprime to the modulus $$\,18\,$$ (so the fraction is single-valued), the Euclidean algorithm passes through various multiple-valued fractions (with non-coprime denominators), even systems with both fractions multiple-valued, such as $$\, 9/3\overset{\large\frown}\equiv 0/2\,$$ above, i.e. the system $$\, 3x\equiv 9,\ 2x\equiv 0\pmod{\!18}.$$

The chosen notation $$\,\large \frac{a}b \overset{\frown}\equiv \frac{c}d\,$$ resembles a padlock (and a congruence combined with intersection) in order to emphasize that the fractions are locked together via intersection - generally we cannot separate the fractions - rather, the solution is the intersection of the adjacent multivalued fractions, so it is not necessarily equal to either one of them (as in the example above).

Such calculations are more commonly expressed without fractions by instead performing operations on systems of equations - operations generalizing Gaussian elimination and triangularization, e.g. reduction of matrices to Hermite /Smith normal form. These topics are studied more abstractly in the theory of modules in abstract algebra (essentially generalizing linear algebra to allow scalars from a ring, not only a field).

To solve $ax\equiv c \mod b$, set $\;d=a\wedge b$, $\;a=a'd, \;b=b'd$. This congruence implies $c$ is divisible by $d$. Actually, it's easy to see that $$ax\equiv c\mod b\iff \begin{cases}c\equiv 0\mod a\wedge b\\\text{and}\\a'x\equiv c'=\dfrac{c}{a\wedge b} \mod b' \end{cases}$$ Thus the problem comes down to the case $a$ and $b$ coprime, after a compatibility condition has been checked.

Added: solution of the second congruence

First we check with the Euclidean algorithm that $\gcd(12260,24755)=5$, and $$\frac{12260}5=2452,\quad\frac{24755}5=4951,\quad\frac{24560}5=4912.$$ Thus the given congruence is equivalent to $\; 2452 x\equiv 4912\mod 4951$, and we have to find the inverse of $2452$ modulo $4951$. This means we have to find a *Bézout's relation between $2452$ and $4951$. It can be obtained with the extended Euclidean algorithm: $$\begin{array}{rrrr} r_i&u_i&v_i&q_i\\ \hline 4951&0&1\\ 2452&1&0&2\\\hline 47&-2&1&52\\ 8&105&-52&5\\ 7&-527&261&1\\ 1&632&-313\\\hline \end{array}$$ Thus $632\cdot2452-313\cdot4951=1$, whence $2452^{-1}=632\bmod4951$, and the solution is $$x\equiv 632\cdot4912\equiv 107\mod4951.$$

• Actually you can do the gcd in parallel with the fraction calculation, and the calculations are simpler - see my 2nd answer.. – Bill Dubuque Dec 11 '16 at 1:44

From your question, I assume you know how to use the extended Euclidean algorithm to compute the modular inverse $a^{-1} \pmod b$ when $a$ is coprime to $b$. Even when $a$ is not coprime to $b$, you can actually solve $ax \equiv c \pmod b$ in almost exactly the same way, assuming that a solution exists.

What the extended Euclidean algorithm actually computes, given the inputs $a$ and $b$, is a triple of integers $(\bar a, \bar b, g)$ such that $g$ is the greatest common divisor of $a$ and $b$, and $a\bar a + b\bar b = g$. When $g = 1$, then $\bar a = a^{-1} \pmod b$, and we can use it to compute the solution $x \equiv c \bar a \pmod b$ to the modular congruence $ax \equiv c \pmod b$.

When $g$ is not $1$, we might call the pair $(\bar a, g)$ the pseudoinverse* of $a$ modulo $b$, as it satisfies the congruence $a \bar a \equiv g \pmod b$, where $g$ is the smallest positive number for which such a congruence exists. Thus, given the congruence $ax \equiv c \pmod b$, we can multiply both sides by $\bar a$ to obtain $gx \equiv c \bar a \pmod b$. If (and only if) $c$ is divisible by $g$, we can also then divide both sides by $g$ (using normal integer division!) to obtain the solution $x \equiv c\bar a / g \pmod b$. Of course, this solution is only unique modulo $b/g$.

Otherwise, if $c$ is not divisible by $g$, no solution exists.

*) You will not find the term "modular pseudoinverse" in any textbooks, since I just made it up. I'm not aware of any more established term for this useful concept, though, and at least it's descriptive, so please indulge me for using it here.

• As written, this method yields only a necessary condition for $x$ to be a solution, since it first multiplies by $\bar a,$ which need not be invertible mod $b$. To avoid this we can first cancel $\,g=(a,b)\,$ then cancel $\,a/g\,$ by multiplying by its inverse $\,\bar a\pmod{b/g},\,$ by $\,\bar a(a/g) + \bar b(b/g) = 1.\,$ The method you described is essentially the same as this standard method (done in fractions in my answer), but it reverses the order of the cancellations, which spoils the bidirectionality of the inferences. – Bill Dubuque Feb 7 '17 at 15:34

Using Euler's Theorem for modular multiplicative inverses:

$\varphi(182) = 72$

$x \equiv 154^{\varphi(182)-1} \pmod{182} \Rightarrow 84 \equiv 154^{71} \pmod{182}$

Now every $x$ of the form $x=84 \pm k\cdot182$ will satisfy $154x \equiv 14 \pmod{182}$

• Euler's Theorem only works if $a$ and $n$ (which is defined as $b$ in my scenario) are co-prime positive integers, but in this situation, they aren't. – Jesse Daniel Mitchell Dec 10 '16 at 23:39
• @JesseDanielMitchell Note that $\gcd(182,154)=14$ so $\gcd(182,154) \equiv 154^{\varphi(182)-1} \pmod{182}$ – kub0x Dec 10 '16 at 23:42

One way to solve the problem ax ≡ c (mod b) would be to treat it as a problem in finding 𝑥0,𝑥1 for the linear equation ax0 − bx1 = c where 𝑎,𝑏,𝑐,𝑥0,𝑥1 ∈ 𝑍. One way to solve the linear equation would be to use substitution in two ways: first to introduce a new variable and a new equation at each step to create a linear system of equations, and second to turn every non-basic variable in the linear system of equation into a basic variable. The motivation for the use of substitution is to express each original variable (𝑥0,𝑥1) as a basic variable that is a function of parameter variables (𝑡0,𝑡1,…) such that for any integer value assigned to the parameter variables would result in the original variables taking on integer values. The computations in the algorithm may be organized using augmented matrices.

I have applied one such algorithm to your example problems in "Solving 154x ≡ 14 (mod 182) and 12260x≡ 24560 (mod 24755) Using Augmented Matrices". It also includes an explanation for the algorithm and an animation of the step-by-step solution to the problems.