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.

10 Answers 10

up vote 55 down vote accepted

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

  • 10
    But won't -2 mod 5 give 3? Both seem to be the same to me... – Wonder Jun 18 '14 at 11:27
  • 3
    @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$. – Newb Jun 26 '14 at 19:12
  • 6
    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. – Wonder Jun 26 '14 at 19:14
  • 2
    @Wonder Yes, the two methods given by OP are equivalent. My answer addresses OP's last question ("how is the modulo of a negative number calculated?") – Newb Jun 26 '14 at 19:18
  • 7
    But then your answer states that method 1 is correct while method 2 is not. Or is it not? – Rudy the Reindeer Dec 22 '15 at 2:42

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.)

  • 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. – Dan Lenski May 6 '17 at 6:39

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.

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

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

  • I think your answer is real answer. – Chaudhry Waqas Nov 11 '16 at 4:16
  • 2
    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)$ – Marc van Leeuwen Nov 27 '16 at 8:17

solution is like this

say -144 mod 5 =>

(-144 + 145 - 145) mod 5 as 145 is a multiple of 5 =>

1 mod 5 =>

1...

to get the number 145.. do it like this

-144 and 5 is given => 144/5 => 28 ..add 1 to it => 29 => 29 * 5 = 145 ..add this number to -144 and the value is your modulo...ie 145 - 144 => 1

This may be a little late, but to be able to do this in your head, a good way to think of it as x - y where:

z % x = y

To get -z % x

f(x) { x - y if x > 0 else 0 }


Examples:


167 % 15 = 2

-167 % 15 = 15 - 2

-167 % 15 = 13


193 % 12 = 1

-193 % 12 = 11

  • Is there a condition like $z \ne x$ here? For instance 30%30 = 0 but -30%30 $\ne$ 30 = 0 . Or maybe you shouldve written $f(x) \{x -y \text{ if } y>0 \text{ else } 0 \}$ ? – VenkiPhy6 Jul 10 at 4:23

The Quickest and easiest way to find the mod of a negative number is by using the below property

if a = (b) mod c then a = (c*k + b) mod c (where k = 1,2,3.......) It simply says that the value of a is unchanged when we add a multiple of c to b

Example

a = (10) mod 3 we all know that a = 1 Now

a = (3*1 + 10) mod 3 - a is still = 1

a = (3*2 + 10) mod 3 - a is still = 1

a = (3*3 + 10) mod 3 - a is still = 1

a = (3*4 + 10) mod 3 - a is still = 1

So adding any multiple of 3 (> 0) to 10 does not effect the value of a Now we use this to our advantage in finding mod of negative numbers

Example

a = (-10) mod 3 Now i add 12 to 10 as 12 is a multiple of 3 and hence the value of a will remain unchanged

so a = (3*4 – 10) mod 3 = 2 mod 3 = 2

easy isnt it?

Another example

a = (-340) mod 60 So a = (60*6 – 340) mod 60 = (360-340) mod 60 = 20 mod 60 = 20

\begin{align}-b\mod N &= (-1\cdot b) \mod N\\ &= (-1 \mod N) (b \mod N)\mod N\\ &= (N-1)b \mod N\end{align}

because $-1 \mod N = N-1$ if $b < N$ then it can be as easy as $-b \mod N = N - b$

example ($-33 \mod 26$)

$-1\cdot33 \mod 26 = 25\cdot33 \mod 26 = 19$

or

$-(33 \mod 26) \mod 26 = -7 \mod 26 = 26 - 7 = 19$

I wanted to try and adjust a mistake I think Newb is making. Perhaps I just misunderstood, but basing on what he himself wrote ("Take −100 mod 8=4. This is because 8⋅−13=−104. The remainder is 4." and "qc+r=x"), I get that we should always skip down to the maximum factor of N (N can be found in the following formulations) lower than a.

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

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

I will call the just-cited algorithms "methods".

While in "simpler" modulus calculations (like 11 mod 3) N is already lower than a, in examples reported in the defined answering, it also happens that we find a negative first argument and a positive second argument.

For the instance of (37-54)mod5 it's been said that 3 should result with the first method (which is the correct result as well) and -2 should result from the application of the second method. Modulo operations with negative values such as these appear to me very ambiguous, but I tried to follow what Newb said, finding myself that it seemed correct. But if I apply the rule I mentioned earlier, 3 should actually appear from both methods.

1) ((a mod N) + (-b mod N)) mod N
   ((37 mod 5) + (-54 mod 5)) mod 5 = ((2) + (1)) mod 5 = 3 % 5 = 3

2) ((a mod N) - (b mod N)) mod N
   ((37 mod 5) - (54 mod 5)) mod 5 = ((2) - (4)) mod 5 = -2 mod 5 = 3

Checking with a calculator before posting I find my computations exact, but I'm still open to all points of view.

Unfortunately I did not have enough reputation to comment under Newb's own answer, I guess it might have been better. Also, English is not my main language, so, please, expose any technical (or non) errors.

  • I don't think Newb has made a mistake. It is not clear to me which mistake you think he's made. – Michael Albanese Dec 22 '15 at 2:34
  • He said one method was wrong. I wanted to prove it wasn't. – noize Dec 22 '15 at 2:36
  • This has already been addressed in the comments on Newb's answer. – Michael Albanese Dec 22 '15 at 2:41

Consider two numbers a and b,where a is negative and b is positive then a%b can be calculated simply as (a+b)%b . For example: a=-2 ,b=20 so, (-2+20)%20 gives (18)%20 which is 18. Take another example: a=-3 b=5 so, (-3+5)%5 gives us 2.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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