74
$\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$
0

4 Answers 4

Reset to default
77
$\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.)

$\endgroup$
2
  • 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, 2017 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, 2019 at 22:12
65
$\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$.

$\endgroup$
11
  • 16
    $\begingroup$ But won't -2 mod 5 give 3? Both seem to be the same to me... $\endgroup$
    – Wonder
    Jun 18, 2014 at 11:27
  • 4
    $\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, 2014 at 19:12
  • 9
    $\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, 2014 at 19:14
  • 10
    $\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, 2015 at 2:42
  • 5
    $\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, 2018 at 9:37
40
$\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.

$\endgroup$
2
  • 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, 2013 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, 2016 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$.

$\endgroup$
2
  • $\begingroup$ I think your answer is real answer. $\endgroup$
    – StealthTrails
    Nov 11, 2016 at 4:16
  • 7
    $\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, 2016 at 8:17

Not the answer you're looking for? Browse other questions tagged .