Solve for $a$: $ab \text{ mod } c = d$

Question

$ab $ mod $ c = d$

$b$ and $c$ are coprime meaning that $d$ is unique in the range $0$ to $c-1$.

How can I solve for a given $b, c,$ and $d$? Known that $a$ is in range $0$ to $c-1$

Real World Example:
I have 10 people in a queue. If I wanted to split their positions by 7 places in order. I would start with [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] -> [0, 3, 6, 9, 2, 5, 8, 1, 4, 7]

The index of each person after the rearrange is:

(original index * shift in index) mod number of people = new index

I want to find the inverse. Which person in the original queue ended up at the given index in the new queue.

Answer 1

If $b$ and $c$ are coprime there is a class called $b^{-1}$ so that $b^{-1}b \equiv 1 \pmod c$ and thus $ab \equiv d \pmod c$ can be solved by $a \equiv abb^{-1} \equiv db^{-1}\pmod c$.

(Note: if $b$ and $c$ are not coprime there is no solution)

So how to solve this is with Euclids alogorthm:

So in your example you want $7a \equiv 1 \pmod {10}$.

$10 = 7 + 3$ so $3 = 10 - 7$.

$7 = 2*3 + 1 = 2(10-7) + 1 = -2*7 +1 + 2*10$ so $1= 3*7 - 2*10\equiv 3*7 \pmod{10}$.

So $7^{-1}\equiv 3 \pmod {10}$.

....

A more significant example: Solve $7a \equiv 8\pmod 18$.

$18 = 2*7 + 4$ so $4 = -2*7 + 18 \equiv -2*7 \pmod{18}$.

$7 = 4+ 3$ so $3 = -4+7 = 2*7 + 7 -18 =3*7 -18 \equiv 3*7\pmod {18}$

$4 = 3+1$ so $1 = 4-3 \equiv (-2*7) - (3*7) \equiv -5*7\equiv 13\pmod {18}$.

So $7^{-1}\equiv 13 \pmod {18}$

(And just to confirm $1 {? \over\equiv} 7^{-1}*7 \equiv 13*7 \equiv 91 =5*18+1 \equiv 1 \pmod {18}$. Yes it works. $7^{-1}\equiv 13 \pmod {18}$.

So $7a \equiv 8\pmod{18}\implies$

$13*7a \equiv 8*13\pmod {18}\implies$

$a \equiv 104\equiv 14 \pmod{18}$.

(And just to confirm: $7*14 = 98 \equiv 8 \pmod {18}$. Yes, it works.)

Answer 2

ab=d(mod c) => a=d*b^-1 (mod c)

If there is no inverse for b mod c, then the equation is not solvable.

In your example, 3^-1 (mod 10) = 7(mod 10) because 3*7=21=1(mod 10).