Solving $ab\equiv d \pmod c $ knowing $b, c \text{ and }d.$

Question

Do you know if it's possible to solve the equation :

$$ab\equiv d \pmod c $$

knowing $b, c \text{ and }d?$

It's been a while I'm looking for answer but I can't find nothing.

Could you help me?

Thanks a lot!

Answer 1

It is possible if and only if $\gcd(b,c)$ divides $d$ (we have to use Bézout's identity to prove this). In particular it's always possible if $\gcd(b,c)=1$.

Indeed, let $\delta=\gcd(b,c)$. We have a Bézout's relation $\; ub+vc=\delta$ for some $u,v\in\bf Z$.

Now we want a relation $\; ab+kc=d$ for some $k\in\bf Z$. Setting $\;b_1=\dfrac bδ$, $\;c_1=\dfrac cδ$, $b_1$ and $c_1$ are coprime since $ub_1+vc_1=1$, and the equation can be rewritten as $$ab+kc=(ab_1+kc_1)δ=d,$$ so $δ$ divides d. Conversely, if $δ$ divides $d$: $d_1= \dfrac dδ̓$, and we solve $\;ab_1+kc_1=d_1$, we also have, multiplying both sides by $δ$, $\;ab+kc=d$.

The the only problem is how to solve the congruence when $b$ and $c$ are coprime. But that is easy thanks to Bézout; the extended Euclidean algorithm produces the coefficients of a Bézout's relation between $b$ and $c$: $\;ub+vc=1$, so $u$ is the inverse of $b\bmod c$, and $$ba\equiv d\mod c\iff uba\equiv ud\mod c\iff a\equiv ud\mod c.$$

̓̓̓̓

Answer 2

Citing Modular multiplicative inverse:

As with the analogous operation on the real numbers, a fundamental use of this operation is in solving, when possible, linear congruences of the form,

$a x \equiv b \pmod m $ .

Answer 3

We need $\gcd (b,c)\mid d$. See the following .