# How to reverse modulo of a multiplication?

I am primarily a programmer (rather than a mathematician) and have recently come across a coding problem where I must invert a function which is the the modulo of a multiplication (given certain constraints which ensure that there is a 1 to 1 mapping between the inputs and the outputs of the function), and I cannot seem to work out how to do it.

Given the following:

(x * a) % b = c

Where 0 <= x <= b

and 0 <= a <= b

and (in case it matters) where the lowest common multiple of a and b is a * b (is co-prime the correct term for this?).

I want to find the inverse function which will give me x, when I know a, b, and c. More specifically, if b and c are kept constant, and c is varied, I want to work out what x is.

In order to try to work it out myself, I set a = 3 and b = 16. I chose these numbers because the lowest common multiple of 3 and 16 is 3 * 16, which is one of the constraints. I then wrote down a list of all possible values of x (between 0 and 15) and the corresponding values for c, using the equation c = (x * 3) % 16

(0 * 3) % 16 =  0    ( 6 * 3) % 16 =   2    (11 * 3) % 16 =   1
(1 * 3) % 16 =  3    ( 7 * 3) % 16 =   5    (12 * 3) % 16 =   4
(2 * 3) % 16 =  6    ( 8 * 3) % 16 =   8    (13 * 3) % 16 =   7
(3 * 3) % 16 =  9    ( 9 * 3) % 16 =  11    (14 * 3) % 16 =  10
(4 * 3) % 16 = 12    (10 * 3) % 16 =  14    (15 * 3) % 16 =  13
(5 * 3) % 16 = 15


I have arranged this in columns, such that each time the value of c "wraps around", a new column is started. From this, I can derive an equation based on the column number:

x = (c + ((column_number - 1) * 16)) / 3

E.g.:

x = (12 + (0 * 16)) / 3 = 4
x = ( 2 + (1 * 16)) / 3 = 6
x = (10 + (2 * 16)) / 3 = 14


What I cannot see, is how to derive the correct amount to multiply by 16 in order to generalise the equations so that I can use it for any c in the above table (i.e. how to derive the "column_number").

-
If $a,b$ are coprime, then there are integers $u,v$ such that $au+bv=1$, which gives $au \mod b = 1$, that is, $u$ is the multiplicative inverse of $a$. Then $a (cu) \mod b = c$. In the above, for $a=3$, $b=16$ you have $u=11$, so the formula is $x=(11 c \mod 16)$. – copper.hat Feb 21 '14 at 7:22

Look up the Euclidean algorithm, which you can write into your code. Since $a$ and $b$ are coprime, the Euclidean algorithm lets you find $s$ and $t$ such that $$a\cdot s+t\cdot b=1$$ and it does it fairly quickly. This means that $$a\cdot s\equiv1\mod{b}$$ So then you can multiply the sides of your original equation ($x\cdot a\equiv c\mod{b}$) by the $s$ that is output from the Euclidean algorithm, and: \begin{align} x\cdot a\cdot s&\equiv c\cdot s\mod{b}\\ x\cdot 1&\equiv c\cdot s\mod{b}\\ x&\equiv c\cdot s\mod{b} \end{align} and you can reduce $c\cdot s$ down so that you get something in between $0$ and $b$.
There is no significantly quicker algorithm to do this for general $a$, $b$, and $c$ than what is outlined here. That is, there is no closed form formula for $x$ in terms of $a$, $b$ and $c$ that could be programmed to be computed quicker.
FWIW, it'd have been nice to include a link for your “Look up the Euclidean algorithm” part. The relevant Wikipedia link is the Extended Euclidean algorithm (looking up the code for regular gcd, which is what people usually think of for Euclid's algorithm, is not so helpful!). Also useful is Wikipedia's page on Modular multiplicative inverse. – Charphacy Apr 20 '14 at 21:36