Identità di Bézout

The Euclidean algorithm is not only useful for finding the GCD: by tracing it “backwards” we uncover a remarkable fact, Bézout’s identity.

Theorem — Bézout's identity

For every pair of integers $a,b$ (not both zero) there exist two integers $x,y$ such that $a x + b y = \text{MCD}(a,b).$ In particular, $a$ and $b$ are coprime ($\text{MCD}=1$) if and only if there exist $x,y$ with $ax+by=1$.

The coefficients $x,y$ are found by working back up through the divisions of the Euclidean algorithm, replacing each remainder in turn with its expression.

Example: 84 and 60

Let us apply Euclid: $84 = 1\cdot 60 + 24, \qquad 60 = 2\cdot 24 + 12, \qquad 24 = 2\cdot 12 + 0.$

So $\text{MCD}(84,60)=12$. Now we work back up, starting from the second-to-last line: $12 = 60 - 2\cdot 24.$ But from the first line $24 = 84 - 1\cdot 60$; we substitute: $12 = 60 - 2\,(84 - 60) = 3\cdot 60 - 2\cdot 84.$

We have found $x=-2$, $y=3$: $-2\cdot 84 + 3\cdot 60 = -168 + 180 = 12 = \text{MCD}(84,60). \checkmark$

What it is for

Bézout’s identity is the key to many results: it proves Euclid’s lemma (if a prime divides a product, it divides one of the factors), it lets us solve Diophantine equations $ax+by=c$ and compute the modular inverses underlying RSA cryptography.

Links

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