Modulus of negative numbers

Question

I had a doubt regarding the ‘mod’ operator So far I thought that modulus referred to the remainder, for example $8 \mod 6 = 2$ The same way, $6 \mod 8 = 6$, since $8\cdot 0=0$ and $6$ remains.

When I perform an operation such as 1) $-8 \mod 6 = 4$ And 2) $-6\mod 8 = 2$

I understood part 2) because on multiplying $8 \cdot (-1) =-8$, the remainder becomes $+2$ (I feel that multiplying by $(-1)$ is correct, because in theory $-8$ is a smaller number than $-6$).

However part 1) does not make any sense to me

Could somebody please give me an explanation regarding the above (part 1) Also do tell me if my way of thinking is wrong.

Thanks In advance.

Answer 1

$4$ is the unique number in $\{0,1,2,3,4,5\}$ such that it differs from $-8$ by a multiple of $6$, namely $-8=(-2)\cdot 6+4$.

Answer 2

For every integer $m$ there are are unique integers $q$ and $r$ where $m = 6q + r$ and $0 \le r < 6$. In the case of $m = -8$ the $q= -2$ and $r = 4$ because $-8 = 6(-2) + 4$.

If the remainder has to be an integer $r$ so that $0 \le r < n-1$ then $- 8 \equiv 4 \mod 6$ because $-8 + 2* 6 = 4$. $4$ is the ONLY possible integer between $0$ and $6$ that you can get to from $8$ by adding or subtracting multiples of $6$.

Answer 3

Not sure how familiar with modular arithmetic you are, but deriving a few basic results and appealing directly to definitions, those results become much more obvious:

Proposition 1.1: For any two integers $a,b$, with $a \gt 0$, there exist integers $q,r$ such that $$ b=qa +r , \qquad 0 \leq r \lt a.$$

Proof:

Consider the rational number $\frac{b}{a}$. There exists a unique integer $q$ such that $$q \leq \frac{b}{a} \lt q +1$$ $$\implies qa \leq b \lt qa + a$$ $$\implies 0 \leq b - qa \lt a,$$ and, letting $r=b - qa $, the result follows.

$\square$

Definition 1.2: Let $a,b \in \mathbb{Z}$. We say $a$ divides $b$, if, for some integer $c$, $$b=ac.$$

$\quad$

Definition 1.3: Let $m$ be a positive integer. For any $a,b \in \mathbb{Z}$, if $m$ divides $a-b$, we write $a \equiv b \pmod{m}$.

$\quad$

Proposition 1.4: Every integer is congruent to exactly one of the integers $0,1,2 \cdots, m-1$ $\pmod{m}$.

Proof:

Note that $$a \equiv b \pmod{m} \iff a-b=qm,$$ for some integer $q$, and so Proposition 1.4 follows immediately from Proposition 1.1.

$\square$

Evaluating the example in your question, by Proposition 1.4, $-8$ is congruent to exactly one of the integers $0,1, 2,3,4,5, \pmod{6}$.

Now, it is clear that $-8=-2 \cdot 6 + 4$ and so $$-8 \equiv 4 \pmod{6},$$ or, in your notation $$-8\pmod{6}=4.$$

Answer 4

In systems for performing integer arithmetic, one typically has a pair of operators:

• $a \mathbin{\mathrm{div}} b$ returns an integer estimating the quotient of $a/b$ (some amount of rounding required)
• $a \mathbin{\mathrm{rem}} b$ returns a 'reduced' number that is congruent to $a$, modulo $b$

(mod is a common symbol for the latter operator)

There are a lot of choices to make regarding the fine details of these operations, but they are almost universally chosen to satisfy the given equation:

$$a = b \cdot (a \mathbin{\mathrm{div}} b) + (a \mathbin{\mathrm{rem}} b)$$

which is the condition for the pair of values to be the result of 'division with remainder'.

Some common examples of how to make this choice are:

• Always round towards zero when computing $(a \mathbin{\mathrm{div}} b)$
• Always round down when computing $(a \mathbin{\mathrm{div}} b)$
• Always have $0 \leq (a \mathbin{\mathrm{rem}} b) < \mathbin{\mathrm{abs}}(b)$

It looks like your source is using the last of these three conventions.

Occasionally you even see more relaxed conventions; e.g. there are applications for things like

• Give me any remainder satisfying $-\mathrm{abs}(b) < (a \mathbin{\mathrm{rem}} b) < \mathrm{abs}(b)$
• Give me any remainder satisfying $0 \leq a \mathbin{\mathrm{rem}} b < 4 \cdot \mathrm{abs}(b)$
• You can return any value for $a \mathbin{\mathrm{div}} b$ that is within 2 units of the true quotient $a/b$