Hi, could someone please answer this question? Provide a proof for the following

Question

Hi, could someone please answer this question?
Provide a proof for the following statements for the Extended Euclid algorithm. (The ExtEuclid algorithm is provided below along with variable definitions)

a) Show that for a >= b >= 0, the values s and t computed by ExtEuclid(a, b) are

relatively prime. Hint: prove this by induction on b.

b) Show that if a >= b > 0, then the values s and t computed by ExtEuclid(a, b)

Satisfy |s| <= b and |t| <= a

Hint: again, induction on b. Be careful, you have to stop the induction before b gets to zero, so

the last step to consider is when b | a.

Algorithm ExtEuclid(a, b): On input a; b, where a and b are integers such that a >= b >= 0 compute (d, s, t), where d = gcd(a, b) and s and t are integers such that as + bt = d, as follows:

ExtEuclid(a,b):

if b = 0 then

d <- a, s <- 1, t <- 0

else

q <- [a/b], r <- a mod b

(d,s’,t’) <- ExtEuclid(b,r)

s <- t’ , t <- s’ – qt’

return (d, s, t)

Explanation / Answer

function extended_gcd(a, b)
x:= 0; old_x := 1
y := 1; old_y := 0
r := b; old_r := a
while r 0
quotient := old_r div r
(old_r, r) := (r, old_r - quotient * r)
(old_x, x) := (x, old_x - quotient * x)
(old_y, y) := (y, old_y - quotient * y)
output "Bézout coefficients:", (old_x, old_y)
output "greatest common divisor:", old_r
output "quotients by the gcd:", (y, x)
The quotients of a and b by their greatest common divisor, which are output, may have an incorrect sign. This is easy to correct at the end of the computation, but has not been done here for simplifying the code. Similarly, if either a or b is zero and the other is negative, the greatest common divisor that is output is negative, and all the signs of the output must be changed.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.