Exercise · ZW-EXTENDED-EUCLIDEAN-ALGORITHM-010 · ★★★ Advanced
For \(a=99\) and \(b=78\), with \(\gcd(a,b)=3\), which pair \((x,y)\) satisfies \(99x+78y=3\)?
Choose one option.
Show answer
- C. \((-11,14)\)
Explanation
Using \(3=15-2\cdot 6\) and back-substituting gives \(3=14\cdot 78-11\cdot 99\). So \((x,y)=(-11,14)\), since \(-1089+1092=3\). The pair \((11,-14)\) gives \(-3\) because of a flipped sign.
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-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?