How to calculate $\,(a-b)\bmod n\,$ and $ {-}b \bmod n$ [closed]

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.

Solution 1:

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

Solution 2:

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

Solution 3:

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.