0 votes 0 votes Let (x′, y′) correspond to gcd(b, a mod b), i.e. gcd(b, a mod b) = x′ ·b + y′ · (a mod b). Then show that gcd(a, b) = y′ · a + (x′ − q)b where q is the quotient of the integer division of a by b. Can anyone help me with this? Algorithms gcd algorithms easy + – UK asked Feb 17, 2016 UK 471 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.