1071 mod 465 is 141. 465 mod 141 is 42. 141 mod 42 is 15, 42 mod 15 is 12, 15 mod 12 is 3, and 12 mod 3 is 0. The last non-zero remainder, 3, is the greatest common divisor, and each step is legitimate for the same reason: any number dividing both a and b also divides a − qb, so the pair and its remainder have exactly the same divisors. Nothing here needs factoring, which is the practical point — 3 is the answer long before anyone knows why 1071 is 3·357.
The number of steps is the thing to watch. Lamé proved in 1844 that the Euclidean algorithm on a pair of integers never takes more than about five times the number of decimal digits of the smaller, and that the worst cases are consecutive Fibonacci numbers — which is why 141, 42, 15, 12, 3 on this page shrink fast: nothing here is a Fibonacci neighbour. The extended version of the same remainder table also returns coefficients with 3 = 1071s + 465t, the ingredient of every modular-division routine in a computer algebra system.
Answer
3
How to read it
15 mod 12, the last non-zero remainder. The first two links are the opening steps, 1071 mod 465 = 141 and 465 mod 141 = 42.
Source
Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give
Work it in the calculator
These links open the right calculator with this problem's numbers already typed in. The line above is what the screen should show — check it yourself.