1
$\begingroup$

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!!

$\endgroup$
1
$\begingroup$

I looked into this some time ago, and I also found this:

  • Note: there is a quicker way to do this at the bottom, but I'm including my original answer in case anyone's interested.

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

$\endgroup$
  • $\begingroup$ @AlanWolfe: I'm curious as to why you listed this under Dioplantine-equations. I'm also curious about the case with multiple primes of the same value - like the two 2's. I'm very much hoping that we could collaborate on this. $\endgroup$ – Matt Groff Apr 22 '16 at 18:09
  • $\begingroup$ Matt, this is such great info, thank you so much! I am in the process of digesting it. My usage case is that I'm playing around with "homomorphic encryption over the integers" and am getting off the beaten path a bit. If I can figure out under what conditions division can be preserved, having HE over the integers not work with individual bits, but instead work with integers more directly (for +-*/), it seems useful. As far as why mod 12, i chose it randomly. primes could be used, but would limit my usage case more than i like. I'm doing SIMD and just have a keys are coprime requirement. $\endgroup$ – Alan Wolfe Apr 22 '16 at 18:31
  • $\begingroup$ @AlanWolfe: I'm starting to remember my thoughts and experiments from before even more... I think we may only need two values to divide $n$ by $m$ modulo $p$: something like $n \bmod m \bmod p$ and $n \bmod p$. I'm interested in talking more, I'm sending you a Facebook request... $\endgroup$ – Matt Groff Apr 22 '16 at 19:24
  • $\begingroup$ Hey Matt, in your second example can you explain how 1/16 became 9 on the third from last line? $\endgroup$ – Alan Wolfe Apr 23 '16 at 14:55
  • $\begingroup$ @AlanWolfe: $1/16 \equiv 16^{-1} \bmod 9 \equiv 5^{-1} \bmod 9 \equiv 9 \bmod 9$ $\endgroup$ – Matt Groff Apr 23 '16 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.