This question is different than other $\bmod M$ where $M < 0$ questions I've found because those don't specifically ask about the 5 relations I ask about below.
When dealing with modular arithmetic like $a\bmod M$ or division inside a floor function like $\big\lfloor \frac{a}{M} \big\rfloor$, I often use the following relations:
$$
\begin{align}
a &= qM + r &&(1)\\
q &= \Big\lfloor \frac{a}{M} \Big\rfloor &&(2)\\
0 &\leq r < M &&(3)
\end{align}
$$
which imply
$$0 \leq r = a – \Big\lfloor \frac{a}{M} \Big\rfloor M < M \qquad(4)$$
Sometimes, I also use
$$r = a \bmod M \qquad (5)$$
but I'm not sure if these relations are self-consistent in all cases, such as when $M$ is negative.
When $M < 0$, it is not possible to satisfy condition $(3)$ which is $0 \leq r < M < 0$. So does condition $(3)$ need to be changed?
For example, if we use $a = \pm 10$ and $M = \pm 3$, then solve for $q$ and $r$, we later find that $r$ does not satisfy $(3)$ when $M < 0$.
First, let's solve for $q = \big\lfloor \frac{a}{M} \big\rfloor$
| $$ \begin{aligned} && M \rightarrow\\ &\;a\\ &\downarrow \end{aligned} $$ | $3$ | $-3$ |
|---|---|---|
| $10$ | $\big\lfloor \frac{10}{3} \big\rfloor = \big\lfloor 3.333\dots \big\rfloor = 3$ | $\big\lfloor \frac{10}{-3} \big\rfloor = \big\lfloor -3.333\dots \big\rfloor = -4$ |
| $-10$ | $\big\lfloor \frac{-10}{3} \big\rfloor = \big\lfloor -3.333\dots \big\rfloor = -4$ | $\big\lfloor \frac{-10}{-3} \big\rfloor = \big\lfloor 3.333\dots \big\rfloor = 3$ |
Now let's solve for $r = a – \Big\lfloor \frac{a}{M} \Big\rfloor M$
| $$ \begin{aligned} && M \rightarrow\\ &\;a\\ &\downarrow \end{aligned} $$ | $3$ | $-3$ |
|---|---|---|
| $10$ | $10 – \Big\lfloor \frac{10}{3} \Big\rfloor 3 = 10 – 3 \cdot 3 = 1 \text{ which satisfies } (3)$ | $10 – \Big\lfloor \frac{10}{-3} \Big\rfloor \cdot (-3) = 10 – (-4) \cdot (-3) = -2 \text{ which does not satisfy } (3)$ |
| $-10$ | $-10 – \Big\lfloor \frac{-10}{3} \Big\rfloor 3 = -10 – (-4) \cdot 3 = 2 \text{ which satisfies } (3)$ | $-10 – \Big\lfloor \frac{-10}{-3} \Big\rfloor \cdot (-3) = -10 – 3 \cdot (-3) = -1 \text{ which does not satisfy } (3)$ |
As we can see, $r$ does not satisfy $(3)$ when $M < 0$. So what is the correct set of relations to use when $M < 0$?
Best Answer
Based on @BillDubuque's comment/Wikipedia link, I made a Desmos that explains 5 types of division and their corresponding quotient, remainder, and Modulo operation.
Summary: Modulo operation, mod(x, M), is defined in terms of remainder of integer division, which in turn, is defined in terms of quotient of integer division, which in turn, depends on the definition of integer division, of which there are several; therefore, there are several definitions of Modulo operation.
From programming, I had always thought of floored division and integer division being synonymous, but now I know floored division is just one possible definition of integer division.
For the particular case of floored division, for divisor $M \in \mathbb M_{\neq 0}$, we have
$$ \begin{cases} 0 \leq r < M &\text{if } M > 0\\ M < r \leq 0 &\text{if } M < 0 \end{cases} $$
which can be consolidated as
$$0 \leq r < \lvert M \rvert$$