Question

• Prove that \(z(x\bmod y)=(zx)\bmod(zy)\)

Credits: TAOCP, vol. 1, E1.2.4 Q15

Solution

Let \(x\bmod y=a\), where \(a<y\), and \(n\) be an integer.

$$ \begin{align*} x\bmod y&=a\bmod y\\ (zx)\bmod(zy)&=(za)\bmod (zy) \end{align*} $$

\(\because\) \(za<zy\), \((za)\bmod(zy)=za\)

$$ \begin{align*} (zx)\bmod(zy)&=za\\ &=z(x\bmod y) \end{align*} $$