Any time you are working with gcd, you will probably want to start with terms of the form . You might even want to consider the set . The minimum of that set is the gcd. Next show that the right hand side produces a divisor of both ka and ka. Then show it produces a greatest divisor.