6

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.

Cornman
  • 11,065
  • 4
  • 30
  • 57
Agnay Srivastava
  • 59
  • 1
    If it isn't $4$ then what non-negative integer between $0$ and $6$ would it be. It can't be $-8$ because $-8 < 0$. It can't be $-8 + 6 = -2$ because $-2 < 0$. It can't be $-8 + 6 + 6 + 6 = 10$ because $10 > 6$ so what other possible number can you get from $-8$ be adding or subtracting multiples of $6$? What is $-8 + 6 + 6$? – fleablood Aug 15 '18 at 05:52
  • One way to get a feel for "negative_value mod positive_value" is to keep adding the modulus until you get a value >= 0. So -8+6+6 = 4. – ToolmakerSteve Jan 23 '19 at 22:14

4 Answers4

5

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

fleablood
  • 124,253
1

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

Mo Pol Bol
  • 1,338
  • What is the convention when a < 0? Also, I have always seen mod with integers. So, does all of these hold true for floats? – Sourav Kannantha B Jan 20 '22 at 09:56
  • @Sourav Kannantha B Note that if $m|b-a$ then immediately we get $-m|b-a$ so that $m$ and $-m$ share the same residue class $0,1,...,m-1$, no need to start from $a\lt 0$ and try to build up to negative modulus. More abstractly, modular arithmetic $\mathbb{Z}/m\mathbb{Z}$ is an example of a quoteint ring $R/pR$, where $p$ can be any element in the ring $R$. In our case, $\mathbb{Z}/m\mathbb{Z}$ is the quotient of $\mathbb{Z}$ by the ideal $m\mathbb{Z}$. – Mo Pol Bol Jan 20 '22 at 13:54
  • Don't know much about floats sorry, but as $\mathbb{R}$ is a field, every element is invertible and hence it does not contain proper ideals-so, at the very least you cannot have a quotient ring $\mathbb{R}/x\mathbb{R}$. Angle is treated somewhat like modular arithmetic, though, e.g $\mathbb{R}/\mathbb{Z}\mathbb{S}^1$, so there might be something for floats. – Mo Pol Bol Jan 20 '22 at 13:54
0

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

Hagen von Eitzen
  • 374,180
0

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$