A sample run °GCD(75,28) ·75=2×28+19 28=1×19+9 ·19=2×9+1 9=9×1 GCD(75, 28)=1, relative primeA sample run • GCD(75, 28) • 75 = 2  28 + 19 • 28 = 1  19 + 9 • 19 = 2  9 + 1 • 9 = 9  1 • GCD(75,28) = 1, relative prime