Try to prove it the other way around. Start with gcd(a,r) and work towards gcd(b,a).