How to Solve an equation with mod for a variable?

Question

I have following equation to be solved, but I am having some trouble in making an understanding and doing so.

(d * e) % v = 1

e and v are known. How to solve this to get value of d ?

Any help is appreciated.

Answer 1

There are multiple ways to solve this modular equation. First is to start adding $v$'s to $1$ until $1 + nv$ for some arbitrary number $n$ is a multiple of $d$. so we have:

$$de \equiv 1 \equiv 1 + nv \pmod v$$

So after division we have:

$$e \equiv \frac{1 + nv}{d} \pmod v$$

If the modular equation have solution, in worst case you would have to add $v$'s in $d$ times.

Also you could solve it by Linear Diphantene Equation using Euclidean Algorithm. We have:

$$de \equiv 1 \pmod v \iff de - 1 = vk$$

So you need to solve the equation and find integer solution $de - vk = 1$, where variables are $e$ and $k$. Note that if $gcd(d,v) \neq 1$ this equation doesn't have solution, this follows from Bezout's Lemma.

And other method is using Gauss method. Your goul would be to bring the fraction: $\frac{1}{d}$ to an integer using multiplication, division and modular arithmetics. But note that you mustn't divide or multiply by factors of $v$, otherwise the calculation will go wrong.