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