Intuitive Understanding of Distributive Multiplication Property for Modulo

Question

I can follow an algebraic proof that

$(ab)\textrm{ mod } n \equiv \big((a\textrm{ mod } n)\cdot(b\textrm{ mod } n)\big)\textrm{ mod } n$

However, I'd like to find a way to "see" it that makes it really obvious, perhaps with reference to number lines or clocks.

One attempt of mine was

$(22*15)\textrm{ mod } 8 \equiv \big((22\textrm{ mod } 8)\cdot(15\textrm{ mod } 8)\big)\textrm{ mod } 8$

is like saying that advancing the hands on a clock whose numbers range form 0-7 22 positions 15 times is the same as advancing the hands on the same clock 22 spaces 15 times, but it seems a bit too tautological to add any insight.

Any ideas on how to fully "grock" this without using algebra?

Answer 1

Make an $a \cdot b$ rectangle of points. We are working modulo $n$, so partition the rows and columns as follows:

• starting from the left edge, into blocks of $n$ columns, with perhaps some small number of columns left in a single block on the right edge and
• starting from the bottom edge, into blocks of $n$ rows, with perhaps some small number of rows left in a single block on the top edge.

This divides the rectangle into four similar pieces

• the "bulk" of the rectangle, starting in the lower-left corner is made of $n \cdot n$ blocks,
• along the right edge of the rectangle, starting from the bottom, is some $k \cdot n$ blocks with $0 \leq k < n$,
• along the top edge of the rectangle, starting from the left, is some $n \cdot \ell$ blocks with $0 \leq \ell < n$, and
• finally, in the upper right is a single $k \cdot \ell$ block where $0 \leq k < n$ and $0 \leq \ell < n$. Note that we allow the dimensions of the non-$n \cdot n$ blocks to be zero, so from a particular choice of $a$ and $b$, any of the last three regions might contain zero points.

Now observe: $k = (a \bmod n)$, $\ell = (b \bmod n)$, and all the blocks in the first three regions contribute $0 \bmod n$ because they contain multiples of $n$ points. Only the $k \cdot \ell$ block in the fourth region can have a nonzero contribution. Since that block can contain more than $n$ points, we should reduce one last time modulo $n$.