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.