Algoritmo di Euclide

Factoring two large numbers into primes can be slow. Euclid (in the Elements, Book VII) describes a method for the GCD that requires no factorisation at all: only divisions with remainder. It is one of the oldest algorithms still in use.

Method — Euclid's algorithm (successive divisions)

To compute $\text{MCD}(a,b)$ with $a\ge b>0$:

1. divide $a$ by $b$: $a = q\cdot b + r$, with $0\le r < b$;
2. if $r=0$, the GCD is $b$;
3. otherwise repeat with $b$ and $r$ in place of $a$ and $b$.

The GCD is the last non-zero remainder (that is, the last divisor).

The idea is that $\text{MCD}(a,b) = \text{MCD}(b,r)$: every common divisor of $a$ and $b$ also divides $r = a - q b$, and vice versa. Replacing the pair with a “smaller” one leaves the common divisors unchanged, but the numbers shrink until a remainder is zero.

Example: GCD(48, 32)

$48 = 1\cdot 32 + 16, \qquad 32 = 2\cdot 16 + 0.$

The last non-zero remainder is $16$: hence $\text{MCD}(48,32)=16$ — the same value found with the factorisations.

Example: GCD(1071, 462)

$1071 = 2\cdot 462 + 147, \quad 462 = 3\cdot 147 + 21, \quad 147 = 7\cdot 21 + 0.$

Last non-zero remainder: $21$. Therefore $\text{MCD}(1071,462)=21$. Trying to factor $1071$ and $462$ into primes would have been much more laborious.

The "subtraction" version of Euclid's algorithm

In its original form Euclid did not use division but repeated subtractions: you subtract the smaller from the larger until the two become equal, and that value is the GCD. Division with remainder is simply “many subtractions in one go”.

Links

Topics: Numeri e operazioni
Concepts: Massimo comun divisore (MCD)
Skills: Scomporre
People: Euclide