0

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

LeppyR64
  • 135
  • 5
  • This is not clear. There are lots of linear congruences $\pmod c$. Take $a\times 1\equiv a\pmod c$ for instance. What are you looking for? – lulu Dec 23 '19 at 15:26
  • 2
    You're thinking about $\mod{}$ as an operation. I would personally advise that you try to think about it as a relation. It makes much of the theory a lot easier to phrase and understand. – Arthur Dec 23 '19 at 15:27
  • 1
    @lulu I think he's looking for a way to calculate the modular $\frac db$. – Arthur Dec 23 '19 at 15:29
  • @Arthur But...he appears to be saying that $a$ alone is given. Not even $c$! – lulu Dec 23 '19 at 15:31
  • @lulu I am given b, c, and d. Solve for a. Arthur is correct in what I am trying to solve. – LeppyR64 Dec 23 '19 at 15:34
  • 1
    I suggest you look at the problems listed under Related, Leppy – the ones like "How to solve $227x\equiv1\pmod{2011}$?" – Gerry Myerson Dec 23 '19 at 16:15
  • $a=b^{-1}d$ unless some parts aren't coprime. then divide out the gcd ... and multiply it back in later. –  Dec 27 '19 at 16:32

2 Answers2

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

fleablood
  • 124,253
0

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

Abhishek Vangipuram
  • 366
  • But presumably OP doesn't know how to find $b^{-1}$. I think that's the real question. – Gerry Myerson Dec 23 '19 at 16:14
  • Ok, then either just try a number of values if you are working with relatively small numbers, or by Euler's Theorem, b^(phi(c)) = 1(mod c) for relatively prime b and c. So b^-1(mod c) = b^(phi(c) -1) (mod c). – Abhishek Vangipuram Dec 23 '19 at 16:18
  • By inverse you mean "modular multiplicative inverse"? – LeppyR64 Dec 23 '19 at 16:26
  • Yes, the inverse let's you find a in terms of other known values. Like normal division, but we have to use inverse when dealing with modular arithmetic. – Abhishek Vangipuram Dec 23 '19 at 16:29
  • The trouble with Euler's theorem, Abhishek, is that you have to know the prime factorization of $c$, which can be difficult when $c$ is large. Euclid's algorithm doesn't have that drawback. – Gerry Myerson Dec 23 '19 at 16:46