Modulo Operation/Examples/18 mod -3

Theorem

$18 \bmod -3 = 0$

where $\bmod$ denotes the modulo operation.

Proof

By definition of modulo operation:

$x \bmod y := x - y \floor {\dfrac x y}$

for $y \ne 0$.

We have:

$\dfrac {18} {-3} = -6 + \dfrac 0 3$

and so:

$\floor {\dfrac {18} {-3} } = -6$

Thus:

\(\ds 18 \bmod -3\)

\(=\)

\(\ds 18 - \paren {-3} \times \floor {\dfrac {18} {-3} }\)

\(\ds \)

\(=\)

\(\ds 18 - \paren {-3} \times \paren {-6}\)

\(\ds \)

\(=\)

\(\ds 18 - 3 \times 6\)

\(\ds \)

\(=\)

\(\ds 0\)

$\blacksquare$

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $9$