# How to compose given add, sub, mult, div functions to map an integer M to N?

Given six integers ($M$, $N$, $a$, $b$, $c$, $d$), is it possible to create a function $H$ such that $H(M) = N$, with the restriction that $H$ is a composition of the following four functions (which may be applied zero or more times, and may be applied in any order):

$$A(x) = x + a\qquad B(x) = x - b\qquad C(x) = x\cdot c\qquad D(x) =\frac{x}{d}$$

These functions correspond with add, subtract, multiply, divide.

For example, suppose $M = 21$, $N = 32$, $a = 10$, $b = 4$, $c = 2$, $d = 3$.

The following is a solution:

$$H = C\ \circ \ D\ \circ\ B\ \circ\ A\ \circ\ C$$

$$H(21) = \left(\frac{((21 \cdot 2) + 10) - 4}{3}\right) \cdot 2 = 32$$

Here is what I have considered so far.

If $a$ and $b$ are relatively prime, so $\gcd(a,b) = 1$, we can make $H$ from just add and subtract operations. When that isn't the case, such as in the example above, where the $\gcd(a,b) = 2$, we are in a different situation. Above, using just add and/or subtract, we can arrive at all odd numbers.

In general, if $\gcd(a,b) = g$, then we can make an $H$ such that $H(M) = M + gk$, where $k \in \mathbb{N}$. In other words, one can map $M$ to any integer $j$ such that $M\equiv j \pmod{g}$. In the above example, we could use multiply by 2 in order to expand to an even number, and then use adds or subtracts in order to arrive at any even integer.

At this point I got stuck. I am not sure how to apply multiply and divide to equivalence classes modulo $g$. (In particular the divide operation, since it can take integer dividends into non-integral quotients). Lastly, although I think this approach could prove the existence of such an $H$, I am unsure how to extract the ordering of function compositions to build it.

Later on, I will be interested in a method for finding the $H$ with the least number of function transpositions.

This question was inspired by a question posted on StackOverflow here. I am interested in the case where division is applied normally, i.e. 3 / 2 = 1.5 and not integer division such as in C++ (decimals truncated toward zero). This means $H$ may be a mapping from $\mathbb{Z}$ to $\mathbb{Q}$.

• Sorry, I'm used to writing $a\equiv b \bmod m$ because I prefer to write the modulus without the parentheses; as I've just edited, if you want parentheses, you should use \pmod instead of \bmod (they mean the same thing, some people write it differently, is all). You can find some good starting points on how to format mathematics on the site here. This AMS reference is very useful. – Zev Chonoles Apr 8 '13 at 7:13
• Thanks, the formatting is a lot nicer. I appreciate it. – Xantix Apr 8 '13 at 7:14

An equivalent question is for what $M$, $N$, $a$, $b$, $c$, $d$ does the equation $Mc^m + k\cdot \gcd(a,b) = Nd^n$ have a solution. Any composition of $A, B, C, D$ can be transformed into this form. The above equation can also be written as $Mc^m \equiv Nd^n \pmod{\gcd(a,b)}$. Even when the answer isn't immediately apparent, because $c^m$ and $d^n$ attain only finitely many values $\pmod{\gcd(a, b)}$, a solution can be found by brute force.