Practice question · Put in order
Order the lines of the Euclidean algorithm computing gcd(1071, 462).
- 147 = 7 x 21 + 0
- 462 = 3 x 147 + 21
- 1071 = 2 x 462 + 147
- The last nonzero remainder is 21, so gcd(1071, 462) = 21
Hints
- Each line divides the previous divisor by the previous remainder.
- The algorithm stops the moment a remainder of 0 appears.
Show the answer
- 1071 = 2 x 462 + 147
- 462 = 3 x 147 + 21
- 147 = 7 x 21 + 0
- The last nonzero remainder is 21, so gcd(1071, 462) = 21
Why
Each step replaces the pair (a, b) by (b, r), and the remainders shrink fast: 462, 147, 21, 0. The answer is the LAST NONZERO remainder, 21, taking the final 0, or the final divisor's remainder, is the usual slip. No factoring was needed anywhere.
Practise GCD and the Euclidean Algorithm
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.