x*y%m=((x%m)*(y%m))%m

to see this

we assume that     

x=am+b

y=cm+d

x*y=a*c*m²+a*d*m+b*c*m+b*d

等式两边同时对m取余

x*y%m=(a*c*m²+a*d*m+b*c*m+b*d)%m

我们这样看

(a*c*m²)%m==0

(a*d*m)%m==0

(b*c*m)%m==0

assume

s=k1*m

t=k2*m

p=k3*m

q=k4*m+z

we know that z<m

so     s+t+p+q=(k1+k2+k3+k4)*m+z

therefore       (s+t+p+q)%m==z

所以

(a*c*m²+a*d*m+b*c*m+b*d)%m=b*d%m

即x*y%m=b*d%m=((x%m)*(y%m))%m得证