Suppose that m,n,q,r are integers satisfying the identity n=mq+r. Then gcd(m,n)=gcd(m,r).

Let gcd(m,n)=k where k is some integer, then k|m and k|n. n=mq+r can be expressed as r=n-mq=k|n+k|m. Therefore k|r.

Let gcd(m,r)=p where p is some integer, then p|m and p|r. n=mq+r=p|m+p|r. Therefore p|n.

Therefore, p|m,n,r and k|m,n,r.

Next step is where my notes do not make sense for me.

If k|m and p|m then kx=m and py=m for some integers x and y. Therefore kx=py and k=p. Q.E.D.