TAOCP 1.2.4 Exercise 16
By definition (1), x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor .
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 16. [M10] Assume that $y>0$. Show that if $(x-z)/y$ is an integer and if $0 \le z < y$, then $z = x \bmod y$.
Verified: yes
Solve time: 43s
By definition (1),
$$ x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor . $$
Hence
$$ x-(x\bmod y) $$
is an integral multiple of $y$, by property (c). Since $(x-z)/y$ is an integer, $x-z$ is also an integral multiple of $y$. Therefore
$$ x-(x\bmod y)\equiv x-z \pmod y, $$
so
$$ x\bmod y \equiv z \pmod y. $$
Because $y>0$, property (a) implies
$$ 0\le x\bmod y<y. $$
By hypothesis,
$$ 0\le z<y. $$
Two integers congruent modulo $y$ and both lying in the interval $[0,y)$ must be equal; otherwise their difference would be a nonzero multiple of $y$ whose absolute value is less than $y$, which is impossible. Therefore
$$ z=x\bmod y. $$
This completes the proof.
∎