Exercise · ZW-EUCLIDEAN-ALGORITHM-010 · ★★★ Advanced
Which pair does the first Euclidean step \((a,b)\to(b,\,a\bmod b)\) produce when applied to \((35,91)\)?
Choose one option.
Show answer
- B. (91, 35)
Explanation
Since \(35<91\), \(35\bmod91=35\); the pair becomes \((91,35)\): the step just swaps the numbers when \(a<b\).
Review the concept: Euclidean algorithm
The Euclidean algorithm computes the greatest common divisor of two integers \(a\) and \(b\) by dividing repeatedly, replacing each pair by the divisor and the remainder, until the remainder is 0.
\[\gcd(a,b)=\gcd(b,\,a\bmod b)\]
More practice problems: euclidean algorithm
- ZW-EUCLIDEAN-ALGORITHM-001 Compute gcd(252,105) with the Euclidean algorithm.
- ZW-EUCLIDEAN-ALGORITHM-002 What is the remainder when 100 is divided by 36?
- ZW-EUCLIDEAN-ALGORITHM-003 Applying the first Euclidean step to the pair (84,30), which pair results?
- ZW-EUCLIDEAN-ALGORITHM-004 Compute gcd(1071,462).
- ZW-EUCLIDEAN-ALGORITHM-005 How many divisions (the last with remainder 0) does the Euclidean algorithm need for gcd(1071,462)?
- ZW-EUCLIDEAN-ALGORITHM-006 Compute gcd(391,221).
- ZW-EUCLIDEAN-ALGORITHM-007 Reduce the fraction (143)/(221) to lowest terms.
- ZW-EUCLIDEAN-ALGORITHM-008 For any positive integer n, what is gcd(n,n+1)?