Exercise · ZW-EXTENDED-EUCLIDEAN-ALGORITHM-002 · ★☆☆ Basic
What are the initial values of \(s_{-1}\) and \(t_{-1}\)?
Choose one option.
Show answer
- C. \(s_{-1}=1\), \(t_{-1}=0\)
Explanation
One starts from \(a=1\cdot a+0\cdot b\), so the coefficient of \(a\) is 1 and that of \(b\) is 0. The option with both coefficients equal to 1 corresponds to no valid initial identity.
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-001 What does the extended Euclidean algorithm guarantee at termination?
- 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…
← ZW-EXTENDED-EUCLIDEAN-ALGORITHM-001 ZW-EXTENDED-EUCLIDEAN-ALGORITHM-003 →