0

How is is possible that $-9 \bmod 4 = -1$ or $-9 \bmod 4 = 3$?

How it can be possible that the remainder has these two alternatives?

Particularly this is in computer languages, where Java produces $-1$ and e.g. C++ doesn't decide between $3$ or $-1$.

I understand that $-1$ is a reasonable answer. But I don't understand why $3$ can be an answer.

mavavilj
  • 7,270
  • 2
    Since this question seems to be primarily about how various programming languages interpret / implement the symbol `mod', I don't think this is really a math question. Perhaps the CS stackexchange would be a better fit? –  May 17 '18 at 19:15
  • See your last question - because $$ n \equiv n'\bmod m \Longleftrightarrow m\mid n-n' $$ – Dietrich Burde May 17 '18 at 19:16
  • That's because $-1\equiv 3\mod 4$. – Bernard May 17 '18 at 19:16
  • @T.Bongers Although, it should be mathematical question, because mathematical $\bmod$ is defined so that the result is in $0, 1, ..., m-1$. Getting $-1$ would violate this, even though it's reasonable in some other sense. – mavavilj May 17 '18 at 19:16
  • 1
    To me, mod as an operator is mostly something done in computer programs. It may have its users in math as well, but it is more often than not overshadowed (in usefulness as well as consistency) by the relation. Modulo $4$ we have $-9\equiv-5\equiv-1\equiv 3$, and none of them is the answer, because there is no actual operation going on. Just a comparison. – Arthur May 17 '18 at 19:27
  • 2
    @mavavilj That is not how the mathematical mod is defined. $a\equiv b\pmod m$ just means that $m$ divides $a-b$. Sometimes we choose a complete list of representatives of the equivalence classes but there is nothing unique or fixed about that selection. – lulu May 17 '18 at 19:28
  • "But I don't understand why 3 can be an answer." Write $-9= 4q + r$ where $0 \le r < 4$. There is only one way to do that. If $q = -3$ and $r= 3$. – fleablood May 17 '18 at 19:55
  • "because mathematical mod is defined so that the result is in 0,1,...,m−1" That is incorrect. Completely incorrect. The mathematical mod is not an operator at all that gives any values at all. It is a statement about a relationship between to numbers. $a \equiv b \mod m$ means that $a-b$ is a multiple of $m$. $b\mod m$ by itself usually means a representation of all possible numbers that $a$ could be so that $a-b$ is a multiple of $m$. – fleablood May 17 '18 at 20:05
  • Here and here it says it is implementation-defined, which is explained here. – farruhota May 17 '18 at 20:33

1 Answers1

2

Computer programmers are not mathematicians.

To a mathematician $-9 \bmod 4 =3$ or $-9 \bmod 4 = -1$ are both meaningless garbage.

Instead $-9 \equiv 3 \mod 4$,which is more properly written as $-9\equiv 3\pmod 4$, would mean that the numbers $-9$ and $3$ are equivalent in that they share the property that one is a multiple of $4$ more or less than the other.

So both $-9 \equiv 3 \mod 4$ and $-9 \equiv -1 \mod 4$ and $9 \equiv 14394847 \mod 4$ are all true statements.

tl;dr

$\mod 4$ is not an operation that gives a single answer. It is a statement about two numbers.

INSTEAD for the purpose of programming $a \bmod 4$ has different meaning. It usually means the remainder you get when you divide by $4$.

Now if $a$ is a positive number like $9$ that is simple: $9 = 4*2 + 1$ so $9 \bmod 4 = 1$.

But what about a negative number. What is $-9 \bmod 4$? What is the remainder when you divide $-9$ by $4$? Well, to a mathematician: finding the remainder of $N$ when divided by $q$ is $r$ means that there are unique integers $d$ and $r$ so that $N = d*q + r$ and $0 \le r < q$. And the remainder $r$ is ALWAYS NON-NEGATIVE and is always LESS than what we are dividing.

So $-9 \bmod 4 = 3$ because $-9 = 4*(-3) + 3$

But most non-mathematicians would say "dividing a negative number is just the same thing as dividing a positive number but we are taking the opposite signs". $9 \bmod 4 = 1$ because $9 = 4*8 + 1$ so $-9 = 4*(-2) - 1$ and $-9 \bmod 4 = -1$.

So which is right?

Well, .... whichever one you want. We aren't talking fundamental rules of the universe. We are talking rules that we make up to do what we define things to be and the one that is correct is the one that is consistent with the rules as we made them up.

So one language used one argument and another used another.

Chappers
  • 67,606
fleablood
  • 124,253
  • 1
    No matter how loudly you ignore the places where modulo is used as a binary operation doesn't make them stop existing. – hmakholm left over Monica May 17 '18 at 20:07
  • Did I ever say otherwise? The second 2/3 of my post was entirely about using mod as a binary operation. But every binary operation is defined by people for their purposes. If one programming language defined $\mod m$ so that $-9 \mod 4 =-1$ and another as $-9\mod 4 = 3$ neither one is right or wrong. It just depends on what actaually was the definition. – fleablood May 17 '18 at 20:17
  • x @fleablood: I'm disputing the implied claim that mod as a binary operation only occurs in programming. As one example, using Euler's theorem for tasks like "compute the last three digits of such-and-such power tower" is often easier to explain by rewritings that involve binary modulus. Especially if you're explaining the concrete calculations to a beginner. And those beginners generally have no idea about programming at all. – hmakholm left over Monica May 17 '18 at 20:22
  • I edited your answer to neaten up the \mods: naturally LaTeX has a few variants for different occasions. – Chappers May 17 '18 at 22:16