Euclid's algorithm on 1071 and 465 reaches gcd 3 through remainders 141, 42, 15, 12

Take remainders until one is zero; the last non-zero remainder is the greatest common divisor.

Equations and algebra · Level: Classic result · Updated on 2026-11-10

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.

This is an independent third-party tool site. It is not affiliated with, sponsored by, or authorised by Casio, Texas Instruments or their distributors. Model names and product names are trademarks of their respective owners and appear here only to identify devices.

The keystroke sequences in these manuals were written from this site's own layout data — the same data the online calculator renders — plus publicly available product facts. Specifications and regional configurations are confirmed against the physical device and the manufacturer's most recent material.