Exercise · ZW-EXTENDED-EUCLIDEAN-ALGORITHM-005 · ★☆☆ Basic
What is \(\gcd(240,46)\) according to the algorithm?
Choose one option.
Show answer
- D. 2
Explanation
The last nonzero remainder of the process is 2, which is the greatest common divisor. The 10 appears as an intermediate remainder rather than the final result.
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-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-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-004 ZW-EXTENDED-EUCLIDEAN-ALGORITHM-006 →