Shall remainder always be positive?

My cousin in grade 10, was told by his teacher that remainders are never negative. In a specific example,

$$-48\mod{5} = 2$$

I kinda agree.

But my grandpa insists that

$$-48 \mod{5} = -3$$

Which is true? Why?

-
$2$ and $-3$ are just two names for the same element in $\mathbb{Z}_5$, i.e. $2 \equiv -3 \mod 5$ – mm-aops May 19 '14 at 13:04
There are various conventions in use, e.g. see the links in this answer. – Bill Dubuque May 19 '14 at 13:08
Python and Ruby say it's 2; C, C#, and Java say it's -3. You could also say it's -8, 7, 12, etc. All are correct. The question is, which do you want? – Tim S. May 19 '14 at 14:00
Who says that remainder and modulus are the same thing? I was taught differently, and the people who developed the Ada programming language apparently thought so, as well. – O. R. Mapper May 19 '14 at 17:36
@John: C++ specification explicitly says (§5.6/4) that / must round towards zero and (a/b)*b + a%b must be equal to a. Which has just one solution, namely that a%b has the same sign as a (unless it is 0). Nothing implementation-defined here. – Jan Hudec May 20 '14 at 21:56

The first one is saying that $-48$ is $2$ more than a multiple of $5$. This is true. The second one is saying that $-48$ is $3$ less than a multiple of $5$. This is also true.

-
Who says short answers are short? – Awal Garg May 20 '14 at 11:42
@AwalGarg I do. Axiomatically. – Cruncher May 20 '14 at 14:10
But what about the division? Would the division with module 2 be -48/5 = 10 remainder 2 ? – Pieter B May 21 '14 at 10:09
@PieterB -48/5 = -10 remainder 2 if you like, but it could also equal -9 remainder -3. – Jack M May 21 '14 at 10:14

The teacher is within his/her authority to define remainders to be numbers $r$, $0\leq r < d$ where $d$ is the divisor. This is just a systematic choice so that all students can apply the same rule and arrive at the same anwer, but the rule is only a convention, not a "truth." The teacher isn't wrong to define remainders that way, but it would be wrong for the teacher to insist that there is no other way to define a remainder. And, anyhow, what your grandpa says is also perfectly true :)

I imagine that ordinary long division is taught with this remainder rule because it makes converting fractions to decimals smoother when students do it later. Another reason is probably that mixed fraction notation (as far as I know) makes no allowance for negatives in the fraction. What I mean is that $1+\frac23=2-\frac13$, but the mixed fraction $1\frac23$ is not usually written as $2\frac{-1}{3}$, although one could make an argument that it makes just as much sense.

As far as modular arithmetic is concerned, you really want to have the flexibility to switch between these numbers, and insisting on doing computations with the positive version all the time would be hamstringing yourself.

Consider the problem of computing $1445^{99}\pmod{1446}$. It should not be necessary to compute powers and remainders of powers of $1445$ when you can just note that $1445=-1\pmod{1446}$, and then $1445^{99}=(-1)^{99}=-1=1445\pmod{1446}$

-
But $(-48) / 5$ as a mixed numeral is $-9 \frac 35$ meaning $-(9 + \frac 35) = -9 - \frac 35$, which lines up more with Grandpa's way than with Teacher's way. – aschepler May 20 '14 at 19:48

The answer depends on whether you want to talk about modular arithmetic or remainders. These two perspectives are closely related, but different. In modular arithmetic, $2\equiv -3 \pmod 5$, so both answers are correct. This is the perspective most answers here have taken. In the division algorithm, though, where remainders are defined, in order to guarantee uniqueness, you need a specific range for the remainder -- when dividing integer $a$ by integer $d$, you get $a=qd+r$, and the integers $q$ and $r$ are unique if $0\leq r<d$ (note that this also places a restriction that $d$ be positive). There are other ways you could set up the condition, but you need some similar range in order to guarantee uniqueness, and this range is the simplest and most common, so in this sense, a negative remainder doesn't work.

-
Excellent answer. The point is that we often want uniqueness of $q$ and $r$, which is guaranteed by requiring $0\leq r < d$. Without this condition, there are $infinitely$ many possible "remainders". – ChocolateAndCheese May 19 '14 at 19:57
@Chocolate: And it's worth noting that other normalizations are possible: sometimes you want $d/2 \leq r < d/2$. Other settings want $0 \leq |r| < d$, but for $rd \geq 0$. Or maybe $rn \geq 0$ or even $rnd \geq 0$. – Hurkyl May 20 '14 at 8:59
We indeed often want uniqueness of $q$ and $r$. But long division algorithm is only practical if $q$ is rounded towards zero (truncated) and that leads to negative (non-positive) remainder for negative numerator. But Euclidean division defines remainder as positive (non-negative). So either definition is sometimes needed with division as well. – Jan Hudec May 21 '14 at 4:57

When -48 is divided by 5 the division algorithm tells us that there is a "unique" reminder r satisfying $0\leq r<5$. In that case there is only one possibility, namely $r=2$.

-
The division algorithm is defined on natural numbers, isn't it? Or I may be mistaken – Cheeku May 19 '14 at 13:30
I think it's usually defined for any integer numerator and any positive integer denominator. – poolpt May 19 '14 at 15:32
Negative denominator is not a problem. But long division needs negative remainders when numerator is negative. – Jan Hudec May 21 '14 at 4:52

Here is a different perspective which is more technical but is also reflected e.g. in Hardy and Wright.

On the whole it is best to regard the expression $"-48 \mod 5"$ on its own as representing the set of numbers $a:a\equiv -48 \mod 5$, so it isn't equal to a number at all, but to a set.

[Technically it is a coset in $\mathbb Z$ of the ideal generated by $5$, and consists of the numbers $-48 + 5 b$, where $b$ is an arbitrary integer].

Quite often it is useful to work with numbers rather than sets, and we choose a representative element of the set to work with. There are different ways in which this can be done (least positive, smallest absolute value etc). In this case $2$ and $-3$ are members of the set and could be used to represent it.

-

Maybe the teacher was thinking about Euclidean division, which states:

Given two integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b

We indeed have the remainder ("r") being positive in this case, but if we talk strictly about congruences the grandpa's expression as well as the teacher's are both true.

-

For integers $a,b,c$ the following statements are equivalent:

1) $a\equiv b\text{ mod }c$

2) $a+c\mathbb{Z}=b+c\mathbb{Z}$

3) $c\mid a-b$

Note that $5\mid-48-2=-50$ and $5\mid-48-\left(-3\right)=-45$.

-

By convention, for a division $\frac{a}{b}=c$, if we are looking for a whole integer for $c$ (with no further stipulations) , the rounding method is towards zero. If $a<0$ and $b>0$, this means that in the equation $\frac{a}{b}=c+\frac{r}{b}$, $r$ must be $\leq 0$.

Also remainders and modulus are two different things.

-

This question touches parts of my old message Algebraic abstractions related to (big) integers in C++ on the boost developers mailing list.

Why should "modulo" be identical to "remainder"? Having a "remainder" function such that "r=remainder(a,m)" satisfies "0 <= r < m" is something convenient to have in a programming language. The quoted message presents some evidence that a "sremainder" function such that "s=sremainder(a,m)" satisfies "-m/2 <= s < m/2" would also be a good idea.

The meaning of modulo and modular arithmetic is not directly addressed by these considerations.

-

For variety, I want to point out that when doing division with remainder (as opposed to, e.g., modular arithmetic), there is sometimes utility in having "improper" results; e.g. saying $17 / 5$ is $2$ with remainder $7$.

An example where this would be useful is if you just need a value that is close to the correct quotient, and you can compute something close (and the appropriate remainder) relatively more easily.

-