73
$\begingroup$

Consider the following expression:

(a - b) mod N

Which of the following is equivalent to the above expression?

1) ((a mod N) + (-b mod N)) mod N

2) ((a mod N) - (b mod N)) mod N

Also, how is (-b mod N) calculated, i.e., how is the mod of a negative number calculated?

Thanks.

$\endgroup$
64
$\begingroup$

It's calculated exactly like the mod of a positive number. In arithmetic modulo $c$, we seek to express any $x$ as $qc+r$, where $r$ must be a non-negative integer.

Why don't we test it out with an example?

Take $-100$ mod $8 = 4$. This is because $8 \cdot -13 = -104$. The remainder is $4$.

So now let's take $(37-54)$ mod $5$. It's equal to $-17$ mod $5 = 3$. Substitute in and do the computation: Method $1$ gives $3$, which is what we want, and method $2$ gives $-2$, so the correct approach is method $1$.

| cite | improve this answer | |
$\endgroup$
  • 16
    $\begingroup$ But won't -2 mod 5 give 3? Both seem to be the same to me... $\endgroup$ – Wonder Jun 18 '14 at 11:27
  • 3
    $\begingroup$ @Wonder: you have $-2 \mod 5$. Now, in arithmetic modulo $c$, we seek to express any $x$ as $qc + r$, where $r$ must be a nonnegative integer. So $-2 = (-1 \cdot 5) + r$, so $r=3$. And that's right, $-2 \mod 5 = 3$. $\endgroup$ – Newb Jun 26 '14 at 19:12
  • 8
    $\begingroup$ All I was saying was that while the first method gives the right answer, method 2 also gives the correct answer because it gives the same answer. $\endgroup$ – Wonder Jun 26 '14 at 19:14
  • 9
    $\begingroup$ But then your answer states that method 1 is correct while method 2 is not. Or is it not? $\endgroup$ – Rudy the Reindeer Dec 22 '15 at 2:42
  • 4
    $\begingroup$ Why would you say that the correct approach is method 1? Both the methods are equivalent and correct. I think you should delete the misleading part of your answer. $\endgroup$ – Kakaji May 26 '18 at 9:37
72
$\begingroup$

Other answers have addressed the immediate question, so I'd like to address a philosophical one.

I think that the way you're thinking of "mod" is a bit misleading. You seem to be thinking of "mod" as an operator: so that "13 mod 8" is another way to write the number "5". This is the way that modulo operators often work in programming languages: in Python you can write "13 % 8" and get back the number 5.

Mathematically, though, I think it is better to think of "mod 8" as an adverb modifying "=": when we say "5 = 13 (mod 8)" we are really saying "5 is equal to 13, if you think of equality as working modulo 8". When you think of "mod" this way, it doesn't really make sense to ask about the expression "((a mod N) + (-b mod N)) mod N": it's not even really an expression, under this interpretation.

I'm not trying to say that you are wrong for thinking of "mod" as an operation, because the operation of "taking a residue mod $m$" is a useful operation. However, I think it is also useful to keep the other meaning of "mod" in mind.

(After writing this answer I see that the question was posted more than a year ago. Well, maybe someone else will find this helpful.)

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ You very nicely made the point about mod as a modifier of the equality assertion, rather than a modifier of the expression on either side. Well said. $\endgroup$ – Dan Lenski May 6 '17 at 6:39
  • $\begingroup$ I don't think this is correct. The correct way to think about modulo is with a complete different arithmetic, and equality has nothing to do with arithmetic. $\endgroup$ – FelipeC Jun 4 '19 at 22:12
39
$\begingroup$

To find $-b \mod N$, just keep adding $N$ to $-b$ until the number is between 0 and $N$.

As an example, $N = 13, b = -27$. Add 13 to -27, you get -14, again you get -1, and again you get 12.

So, $-27 \mod 13 = 12$.

A bit more generally, you might want to realize that $a \mod N = a + kN \mod N$ for any $k \in \mathbb{N}$. That should help with your first question.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ So, can (a-b) mod N be written as: ((a mod N) + N - (b mod N)) mod N? $\endgroup$ – J.P. Oct 9 '13 at 8:06
  • $\begingroup$ To clarify, the number should be in the range { x: x >=0 && x < N } i.e. -7 mod 7 is 0. $\endgroup$ – Kirk Broadhurst Jun 29 '16 at 16:29
6
$\begingroup$

Adding a thumb rule to all the answers above: negative number modulo k = k minus positive number modulo k. To find $(-n)\%k$ just find $k-(n\%k)$.

Ex: $(-144)\%5 = 5 - (144\%5) = 5 - (4) = 1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think your answer is real answer. $\endgroup$ – Chaudhry Waqas Nov 11 '16 at 4:16
  • 6
    $\begingroup$ No, this is wrong when $k$ exactly divides $n$: then $(-n)\bmod k=0$ but your expression gives $k-(n\bmod k)=k-0=k$. The correct symmetry is provided by subtraction from $-1$ rather than from $0$, namely$(-1-n)\bmod k=k-1-(n\bmod k)$, or if you write $-1-x$ as ${\sim}x$ as a more clear analogue $({\sim}n)\bmod k=k+{\sim}(n\bmod k)$ $\endgroup$ – Marc van Leeuwen Nov 27 '16 at 8:17

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