Exercise · ZW-EXTENDED-EUCLIDEAN-ALGORITHM-009 · ★★☆ Intermediate
If the extended algorithm gives \(s_k\) and \(t_k\) with \(r_k=as_k+bt_k\), what must hold at the end of the process?
Choose one option.
A That \(r_k=0\) with \(s_k=1\) B That all quotients equal 1 C That \(s_k=t_k\) D That the last nonzero remainder \(r_k\) equals \(\gcd(a,b)\) together with its coefficients Show answer D. That the last nonzero remainder \(r_k\) equals \(\gcd(a,b)\) together with its coefficients← Back to the question
Explanation The invariant holds at every step, and at the end the last nonzero remainder is the greatest common divisor with its associated coefficients. Taking a zero remainder as the result is a common mistake.
The extended Euclidean algorithm computes \(d=\gcd(a,b)\) and integers \(x\), \(y\) such that \(ax+by=d\). It is the Euclidean algorithm that also tracks the Bézout coefficients.
\[r_k=r_{k-2}-q_{k-1}r_{k-1}\\s_k=s_{k-2}-q_{k-1}s_{k-1}\\t_k=t_{k-2}-q_{k-1}t_{k-1}\]
More practice problems: extended euclidean algorithm ZW-EXTENDED-EUCLIDEAN-ALGORITHM-001 What does the extended Euclidean algorithm guarantee at termination?ZW-EXTENDED-EUCLIDEAN-ALGORITHM-002 What are the initial values of s_-1 and t_-1?ZW-EXTENDED-EUCLIDEAN-ALGORITHM-003 If gcd(a,b)=d, what relation do a, b and d satisfy in Bézout's identity?ZW-EXTENDED-EUCLIDEAN-ALGORITHM-004 In the step 46=4· 10+6 of the division r_k-2=q_k-1r_k-1+r_k, what is q_k-1?ZW-EXTENDED-EUCLIDEAN-ALGORITHM-005 What is gcd(240,46) according to the algorithm?ZW-EXTENDED-EUCLIDEAN-ALGORITHM-006 For a=30 and b=12, with 6=30-2· 12, what value of y satisfies 30x+12y=6 with x=1?ZW-EXTENDED-EUCLIDEAN-ALGORITHM-007 With a=35 and b=15, the algorithm gives gcd=5. Which is a valid pair (x,y) with 35x+15y=5?ZW-EXTENDED-EUCLIDEAN-ALGORITHM-008 For a=17 and b=5, what is the coefficient y in the identity 17x+5y=1?