mod operation proof

Question

Prove:

$ ab\,\bmod\,d = ((a\,\bmod\,d)\,(b\,\bmod\,d))\,\bmod\,d $ where $a$, $b$ and $d$ are non-negative integers.

Reference : http://en.wikipedia.org/wiki/Modulo_operation#Equivalencies

Context : I was solving the problem 'C. DNA Alignment' in Codeforces Round #195(div.2). To solve the problem, I had to calc (a^b)%n in Big-O(N) without overflow. This could be done simply if above equation is always true. I assumed this equality is always true and solve the problem. But I couldn't prove my solution because of this equation, so I searched it but faild. So I decided to ask the proof of this problem.

Problem Source : http://codeforces.com/contest/520/problem/C

Answer 1

Let $a=\alpha d+j, b=\beta d+k$. $a\mod d =j$, so the right hand side is: $$jb\mod d=(j\beta d+jk) \mod d=jk \mod d$$. Looking at the left hand side:

$$ab \mod d=(\alpha d+j)(\beta d+k)=\alpha\beta d^2 + \alpha dk + \beta dj + jk=jk \mod d$$

and these are equal.