Modulus residue is preserved or honored (sorry, I don't know the correct term. Is it homomorphism?) under addition and multiplication.
For example:
2 + 4 = 6
2 * 4 = 8
Then, making those values be the residue mod 12:
26 mod 12 = 2
40 mod 12 = 4
we can do the same math operations:
26 + 40 = 66
26 * 40 = 1040
The results show that the residue of the modulus are the same values as if we did the operation on the residue instead of the values themselves:
66 mod 12 = 6
1040 mod 12 = 8
However, division doesn't properly preserve the residue. Let's say we want to do 8 / 4.
20 mod 12 = 8
16 mod 12 = 4
20 / 16 = 1.25
1.25 mod 12 = 1.25
That answer is obviously wrong, but in some cases, you CAN get the right answer. For instance, we can reverse the multiplication we did.
1040 mod 12 = 8
40 mod 12 = 4
1040 / 40 = 26
and 26 mod 12 = 2, so it shows us that yes, 8 / 4 = 2.
My question is, why is it that division works some of the time? What properties must be fulfilled to make the residue come out to the correct result when performing division in this way?
I can obviously do a division for any numerator and denominator combo i used in a multiplication to get the numerator, but I can't figure out what makes the result of that multiplication special such that a division will work.
Thanks!!
I looked into this some time ago, and I also found this:
In a way, division destroys residues. If you are working mod 12, dividing $m \cdot n$ by $m$ or $n$ will preserve the residue, provided the result is an integer < 12. Now consider the result modulo 12 is not an integer, like $3 \frac{1}{3}$. This is really 3 + 1/3, so you have to find a way to recover the integer portion of the result, along with the fractional portion. Doing the division modulo 12 will always give what is essentially 3 + 1/3. You could attempt to verify this by creating a table of successive values.
I've found a few tricks. The first thing to note is that residues work best modulo a prime. The real trick is that the operations are always preserved modulo a prime, which is technically called a finite field. The second trick is to use the prime repeatedly. The third trick, which I've found to be somewhat of a letdown, since I haven't been able to find a decent workaround, is that we need to know what we're dividing by ahead of time.
For an example, I will use a single prime, 11. If we want to divide 20 by 16, as in your example, we must split 20 into multiple values. We must find the representation of 20 in base 16, since we're dividing by 16. This is $1*16^1 + 4*16^0$. Then we divide this number by 16. So:
$$\frac{1*16^1 + 4*16^0}{16} = 1*16^0 + \frac{4*16^0}{16} = 1 + \frac{4}{16}$$
We can certainly find what 1 + 4/16 is modulo 11, and this gives us the correct value modulo 11.
I'd like to do a more complicated example to hammer this home. What I'm trying to show is that we can always get the correct result of dividing an integer by an integer modulo any prime.
So say we want to find 2201 / 16 modulo 11. We find:
$$2201 = 8 * 16^2 + 9 * 16^1 + 9*16^0$$
$$\begin{align} \frac{2201}{16} &= \frac{8 * 16^2 + 9 * 16^1 + 9*16^0}{16} \\ &= 8 * 16^1 + 9 * 16^0 + 9 * \frac{1}{16}\\ &\equiv 8 * (16^1) + 9 * (16^0) + 9 * (\frac{1}{16}) \bmod 11\\ &\equiv 8 * (5) + 9 * (1) + 9 * (9) \bmod 11\\ &\equiv 40 + 9 + 4 \bmod 11 \\ &\equiv 9 \bmod 11 \end{align}$$
Now let's take 2201/16 as a decimal representation. We get 137.5625. This is 137 + 9/16. This is 5 + 9/16 modulo 11, which is 9 modulo 11. We have the correct result.
A few thoughts
We can, of course, handle having multiple modulus like a residue number system (RNS), or with the Chinese remainder theorem. The next problem, to me, is still handling your problem. You are doing things modulo 12=2*2*3. I haven't quite figured out how to handle more than one of the same prime, since you have two 2's.
EDIT
We really only need two values for $a / b \bmod p$, with $p$ prime. We need the result and remainder of $a / b$ using long division. In other words, if we have $a$ divided by $b$ equals $c$ with a remainder $d$, then:
$$(a/b) \equiv c + (d * 1/b) \bmod p$$