Exercise · ZW-EXTENDED-EUCLIDEAN-ALGORITHM-001 · ★☆☆ Basic
What does the extended Euclidean algorithm guarantee at termination?
Choose one option.
Show answer
- D. A pair of integers \(x,y\) with \(ax+by=\gcd(a,b)\)
Explanation
The algorithm returns Bézout coefficients for the greatest common divisor. The option about counting steps yields no linear combination.
Review the concept: Extended Euclidean algorithm
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-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?
- ZW-EXTENDED-EUCLIDEAN-ALGORITHM-009 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 pr…