Explain negative modulo like I'm five?

Question

I know this has been addressed here, but I confess to not fully understanding that, so I'm hoping someone can chime here.

First, is there a canonical formula for this? In programming language languages, different ones lead to varying results, which would seem to indicate not?

Anyway, in layman's terms, I've always understood modulo to mean something like:

1. Fractional remainder * quotient = x
2. ceiling(x) = result

So an example with 5 mod 3:

1. 5/3 = 1.66666666...
2. fractional = 0.666666 * 3 = 1.998
3. result = ceiling(1.998) = 2

applying that to a negative number though, like -1 mod 18:

1. -1/18 = -0.0555555
2. fractional = -0.055555 * 18 = -0.99999
3. result = ceiling(-0.99999) = 0
4. This seems wrong, so maybe floor() makes sense for negatives, which would yield -1 as the result

(#)4 seems intuitively correct as positive 1 mod 18 = 1. But that's wrong, as it seems -1 mod 18 = 17, and I just don't see how to get to that.

Thanks!

Answer 1

You are computing the fractional part of a negative number wrong.

The fractional part of a negative number is not the negative of the fractional part of its absolute value: that is, the fractional part of, for example, $-1.4$, is not $-0.4$. The fractional part is $0.6$.

This is because the fractional part of $x$ is defined to be $x-\mathrm{floor}(x)$. For $x=-1.4$, $\mathrm{floor}(x) = -2$, so the fractional part of $-1.4$ is $-1.4 - (-2) = 2-1.4 = 0.6$.

Once you do this adjustment, your process will work. You have $$\begin{align*} -\frac{1}{18} &\approx -0.055555\\ \mathrm{floor}\left(-\frac{1}{18}\right) &= -1\\ \mathrm{fractional}\left(-\frac{1}{18}\right) &\approx -0.055555+1\\ \mathrm{fractional}\left(-\frac{1}{18}\right) &\approx 0.944445\\ \mathrm{fractional}\left(-\frac{1}{18}\right)*18 &\approx 16.999992\\ \mathrm{ceiling}\left(\mathrm{fractional}\left(-\frac{1}{18}\right)*18\right) &= 17. \end{align*}$$ But you have to be careful with approximations, lest you get a bit more than $17$ in the final step, for example.

---

That said, it is better to think of this as quotient with remainder, rather than fractional part. The remainder when dividing by $q>0$ must be an integer greater than or equal to $0$ and strictly less than $18$. So when you divide $-1$ by $18$, you get a quotient of $-1$ and a remainder of $17$: more generally, if $m\gt 0$, then to find $a$ modulo $m$, you can do division with remainder to get $$a = qm + r,\qquad 0\leq r\lt m$$ and then the modulo is $r$.