Exercise · ZW-EXTENDED-EUCLIDEAN-ALGORITHM-007 · ★★☆ Intermediate
With \(a=35\) and \(b=15\), the algorithm gives \(\gcd=5\). Which is a valid pair \((x,y)\) with \(35x+15y=5\)?
Choose one option.
Show answer
- B. \((1,-2)\)
Explanation
We have \(35-2\cdot 15=5\), so \((1,-2)\) works. The option \((2,-4)\) gives \(70-60=10\), which is not 5.
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-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-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-006 ZW-EXTENDED-EUCLIDEAN-ALGORITHM-008 →