Il MCD non cambia sottraendo

Testo

Siano $a, b \in \mathbb{Z}$. Dimostra che $\gcd(a, b) = \gcd(a - b,\, b)$.

Soluzione

Basta mostrare che le coppie $\{a, b\}$ e $\{a-b, b\}$ hanno gli stessi divisori comuni; allora avranno lo stesso massimo comun divisore.

• Se $d \mid a$ e $d \mid b$, allora $d \mid (a - b)$; quindi $d$ è divisore comune di $a-b$ e $b$.
• Se $d \mid (a - b)$ e $d \mid b$, allora $d \mid \big((a-b) + b\big) = a$; quindi $d$ è divisore comune di $a$ e $b$.

Gli insiemi dei divisori comuni coincidono, dunque il loro massimo è lo stesso: $\gcd(a,b) = \gcd(a-b,\,b). \qquad \blacksquare$

Collegamenti

Argomenti: Numeri e operazioni
Concetti: Divisibilita · Massimo comun divisore (MCD)
Competenze: Dimostrare
Tipo di esercizio: Dimostrazione