Exercise · ZW-EXTENDED-EUCLIDEAN-ALGORITHM-004 · ★★☆ Intermediate
In the step \(46=4\cdot 10+6\) of the division \(r_{k-2}=q_{k-1}r_{k-1}+r_k\), what is \(q_{k-1}\)?
Choose one option.
Show answer
- A. 4
Explanation
With \(r_{k-2}=46\) and \(r_{k-1}=10\), the quotient \(q_{k-1}=4\) multiplies the divisor 10. The remainder 6 is \(r_k\), not the quotient.
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-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-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-003 ZW-EXTENDED-EUCLIDEAN-ALGORITHM-005 →