Computers and Technology
Given two integers r,y, one may wonder what numbers can be obtained by adding integer multiples of r and y, i.e., what integers can be written as arby for some (not necessarily positive) integers a, b. It turns out that g ged(, y) is the smallest positive integer that can be written as g = az+ by; this fact is known as Bezout's identity. (You will not need to prove this In this exercise, we'll modify the standard Euclidean algorithm to give us not only g gcd(, ), but also a pair (a, b) of integers, called Bzout coefficients, such that ar + by g We give part of the algorithm below: