1

This is a 2 part question.

part 1 (negative mod calculations):

As part of a larger equation, I have come to a stage where I need to calculate -17 mod 11. By doing it manually I got -6 as the result. (-17 - ((-17 / 11) * 11))

But by checking an online mod calculator, the result is 5.

I don't understand. Can someone shed some light on the process of calculating negative mods?

part 2 (order of operations):

This also involves mod. I am wondering what order to calculate an equation which involves mod and multiplication.

for example: x (f - g) mod y

would you calculate x (f - g) first and then mod the result by y.

or (f - g) mod y first then the result * x?

Thank you for any help you can provide.

Alec
  • 13

1 Answers1

0

This answer treats mod in the context of calculators or programming languages. This is not a pure mathematical approach (with equivalence classes, etc):

Part 1: $(-17 - ((-17 / 11) * 11))$ is incorrect for $(-17) \bmod 11$, a definition for mod is $$ a \bmod b = a - \lfloor a/b\rfloor b,$$ where $\lfloor x \rfloor$ is the floor function (rounding to the next integer in direction $-\infty$). For your example $$ (-17) \bmod 11 = -17 - \lfloor (-17)/11\rfloor \times 11\\ = -17 - \lfloor -1.54545\dots\rfloor \times 11\\ = -17 - (-2)\times 11 = 5.$$ Part 2: The mod operation is completely distributive for addition, subtraction, and multiplication: $$(a \pm b) \bmod m = (a \bmod m) \pm (b \bmod m)\\ (a b) \bmod m = (a \bmod m) (b \bmod m)\\ $$ But note that you may have to reduce mod $m$ more than once with this simple approach, e.g. with $a=17, b=-2, m=11$ $$ (a b) \bmod m = (-34) \bmod 11 = 10 \bmod 11$$ $$(a \bmod m) (b \bmod m) = (17 \bmod 11) (-2 \bmod 11) \\ = (6 \bmod 11) (9 \bmod 11) = 54 \bmod 11 = 10 \bmod 11$$

Thus the above formulas should be written as $$(a \pm b) \bmod m = \Big((a \bmod m) \pm (b \bmod m) \Big) \bmod m\\ (a b) \bmod m = \Big((a \bmod m) (b \bmod m)\Big) \bmod m\\ $$

gammatester
  • 18,827
  • hi! thank you so much for your answer. I have understood part 2 perfectly. BUT, I do have a question about part 1. have you simply rounded $[-1.54545]$ to 2? if we are faced with a decimal number should we round up or down before multiplying by $b$? If so, how do we decide whether to round up or down? <5 = round down. =/> 5 = round up? Thanks. – Alec Oct 16 '13 at 09:17
  • No, $\lfloor −1.54545\rfloor$ is rounded down to -2. Floor always rounds down (if the argument is not an integer), but remember that e.g. $\lfloor -0.1 \rfloor = -1!$, i.e. if $x$ is negative but not an integer, you have $$\lfloor x \rfloor = \lfloor -x \rfloor - 1$$ – gammatester Oct 16 '13 at 09:59
  • ok so if I understand correctly... if we were actually calculating something like $-25 / 11 = -2.2727...$ then we'd round down to $-3$ ? it rounds down to the next $-ve$ integer regardless? – Alec Oct 16 '13 at 10:03
  • Yes, that's correct. So for $(-25) \bmod 11 = 8 \bmod 11$ you compute:

    $$- 25 - \lfloor -25/11\rfloor \times 11 = - 25 - \lfloor−2.2727...\rfloor \times 11 = -25 -(-3)11 = -25 + 33 = 8$$

     – gammatester Oct 16 '13 at 10:11
  • okay excellent. thank you so much. this has been immensely helpful. – Alec Oct 16 '13 at 10:14
  • There is no reason to consider using the remainder-after-division operation to be impure mathematics. It is true that one often prefers working with congruence classes, but something as basic as the Euclidean algorithm does use the value of the remainder, not its conruence class. – Marc van Leeuwen Nov 28 '14 at 11:15