As #a-=b(mod m)#,
this means when #a# and #b# are divided by #m#, quotients, say #q_1# and #q_2#, are different but remainder, say #r#. will be same. Therefore
#a=q_1m+r# and #b=q_2m+r#.
Let us first consider #a=q_1m+r#. Assume that #d# is the GCD of #a# and #m# and hence divides both #a# and #m#. Now if #a=da'# and #m=dm'#, then
#da'=q_1dm'+r# and then #r=d(a'-q_1m')#, which means
#d# also divides both #m# and #r# and hence #d# must also be the GCD of #m# and #r# too. We can go now divide #m# by #r# and if remainder is #r_1#, then similarly #d# will be the GCD of #r# and #r_1# too. We can go on this way till remainder is #0# and the divisor at that stage will be GCD of #a#and #m#.
This is the logic behind long division method of finding GCD.
Similarly if #b=q_2m+r#, GCD of #b# and #m# is also the GCD of #m# and #r#.
As GCD of #a# and #m# and GCD of #b# and #m#, both are equalt to GCD of #m# and #r#, we have
#GCD(a,m)=GCD(b,m)#
