,

UVA -- 10104

Solution :

 ** nothing but Extends Euclid Algorithm.