Massimo comune divisore dimostrazione

[algibro]

Tra i naturali, con $a,b \ne 0$ allora $MCD(a,b)=MCD(b,r)$ dove $r$ è il resto della divisione di $a$ per $b$.
Essendo $a=bq+r, r<b$ tutti i divisori di $b$ e $r$ sono anche divisori di $a$ inoltre $MCD(b,r) \leq MCD(a,b)$ e ciò mi sembra ovvio in quanto risulta $r<b\leq a$
Non capisco invece come dal fatto che $r=a-bq$, assodato che anche in questo caso ogni divisore di $a $ e $b$ è anche divisore di $r$ possa inequivocabilmente essere che $MCD (a,b) \leq MCD (b,r)$

[G.D.]

... inoltre $MCD(b,r) \leq MCD(a,b)$ e ciò mi sembra ovvio in quanto risulta $r<b\leq a$.

Davvero? Quindi non può essere \( a < b \)?

[algibro]

Certo, ma se $a <b $ abbiamo $a=bq+r , q=0, r=a $ e mi sembrava (sbagliando) fosse escluso questo caso. A questo punto, dato che ogni divisore di $b $ e $r $ è anche divisore di $a $ , se $a <b \Rightarrow r=a$ e $(a,b)=(b,r) $.

Mi rimane difficile comprendere perché se $r=a-bq$ allora i divisori comuni di $a $ e $b$ sono minori o uguali ai divisori comuni di $r $ e $b $.

[G.D.]

Certo, ma se $a <b $ abbiamo $a=bq+r , q=0, r=a $ e mi sembrava (sbagliando) fosse escluso questo caso.

Escluso sicuramente no: le uniche ipotesi fatte su \( a \) e \( b \) sono che \( a, b \in \mathbb{N} \) e \( a, b \ne 0 \).
Al massimo puoi trattare tu a parte questo caso osservando (come hai fatto) che in questo caso, essendo \( r = a \), la tesi è ovvia.

Il punto è che l'ordinamento tra \( a \), \( b \) e \( r \) è irrilevante.

Siano \( d = \operatorname{MCD} (a,b)\) e \( d' = \operatorname{MCD} (b,r) \).
Allora \( a = bq + r = d'h'q + d'k' = d' ( h'q + k' ) \), quindi \( d' \mid a \). Poiché è anche \( d' \mid b \), allora, in forza della definizione di massimo comune divisore¹, si ha che \( d' \mid d \) e, di conseguenza, \( \operatorname{MCD} (b,r) \le \operatorname{MCD} (a,b) \).
Da \( a = bq + r \) si ha \( r = a - bq = dh - dkq = d ( h - kq ) \), quindi \( d \mid r \). Poiché è anche \( d \mid b \), allora, in forza della definizione di massimo comune divisore, si ha che \( d \mid d' \) e, di conseguenza, \( \operatorname{MCD} (a,b) \le \operatorname{MCD} (b,r) \).

---

Note

1. Dati due interi \( a \) e \( b \) non entrambi nulli, un intero \( d \) si dice massimo comune divisore di \( a \) e di \( b \) se e solo se:
   • \( d \mid a \) e \( d \mid b \);
   • per ogni intero \( d' \) tale che \( d' \mid a \) e \( d' \mid b \), si ha che \( d' \mid d \). ↑

[luca69]

Mi riallaccio alla definizione di $M.C.D.$, ricordata in nota da @G.D., per chiedervi un chiarimento.

Nel testo di Herstein "Abstract Algebra", 3rd Ed., pag. 23, si premette che tale definizione "[...] può sembrare strana [...]" in quanto "[...] vogliamo evitare di usare la grandezza di un intero $-$ per ragioni che diventeranno chiare molto più in là, quando parleremo di anelli [...]". Intendo questa cautela come relativa ad utilizzare l'ordinamento degli interi (greatest); se così è, però, perché nel Principio di Buon Ordinamento -alla pagina precedente nel testo citato- si parla "tranquillamente" di smallest member", dando quindi per scontato l'ordinamento di $ZZ$? Forse tale cautela si riferisce limitatamente alla definizione di $M.C.D.$?

[G.D.]

Io non ho capito la domanda.

[luca69]

Perchè non definire $MCD$ tra due interi $a$ e $b$ un intero positivo $c$ che divide entrambi e tale che, se $c'$ è un altro intero positivo che divide $a$ e $b$ risulta $c'<=c$, e derivare invece come lemma che $c'|c$ ?

[algibro]

Certo, ma se $a <b $ abbiamo $a=bq+r , q=0, r=a $ e mi sembrava (sbagliando) fosse escluso questo caso.

Escluso sicuramente no: le uniche ipotesi fatte su \( a \) e \( b \) sono che \( a, b \in \mathbb{N} \) e \( a, b \ne 0 \).
Al massimo puoi trattare tu a parte questo caso osservando (come hai fatto) che in questo caso, essendo \( r = a \), la tesi è ovvia.

Il punto è che l'ordinamento tra \( a \), \( b \) e \( r \) è irrilevante.

Siano \( d = \operatorname{MCD} (a,b)\) e \( d' = \operatorname{MCD} (b,r) \).
Allora \( a = bq + r = d'h'q + d'k' = d' ( h'q + k' ) \), quindi \( d' \mid a \). Poiché è anche \( d' \mid b \), allora, in forza della definizione di massimo comune divisore¹, si ha che \( d' \mid d \) e, di conseguenza, \( \operatorname{MCD} (b,r) \le \operatorname{MCD} (a,b) \).
Da \( a = bq + r \) si ha \( r = a - bq = dh - dkq = d ( h - kq ) \), quindi \( d \mid r \). Poiché è anche \( d \mid b \), allora, in forza della definizione di massimo comune divisore, si ha che \( d \mid d' \) e, di conseguenza, \( \operatorname{MCD} (a,b) \le \operatorname{MCD} (b,r) \).

Ma ovvio ! Mi ero incastrato nella relazione $(\mathbb{N},<)$.
Grazie mille.

---

Note

1. Dati due interi \( a \) e \( b \) non entrambi nulli, un intero \( d \) si dice massimo comune divisore di \( a \) e di \( b \) se e solo se:
   • \( d \mid a \) e \( d \mid b \);
   • per ogni intero \( d' \) tale che \( d' \mid a \) e \( d' \mid b \), si ha che \( d' \mid d \). ↑

[algibro]

Perchè non definire $MCD$ tra due interi $a$ e $b$ un intero positivo $c$ che divide entrambi e tale che, se $c'$ è un altro intero positivo che divide $a$ e $b$ risulta $c'<=c$, e derivare invece come lemma che $c'|c$ ?

Perché credo che, in $\mathbb{N}$, se $c'|c$, con $c',c \ne 0$ abbiamo $c=c'q$ con $q \geq 1$.
Quindi essendo $q-1 \in \mathbb{N}$, possiamo scrivere $q=(q-1)+1$ e $c=c'[(q-1)+1]=c'(q-1)+c'>=c'$
Segue che se $c'|c \Rightarrow c'<=c$

[G.D.]

In verità si potrebbe benissimo definire il massimo comune divisore di due numeri interi relativi come il maggiore tra tutti i divisori comuni dei due interi dati, come viene fatto per esempio in "An Introduction To The Theory Of Numbers" di Hardy e Wright del 1929. Sebbene il testo sia abbastanza datato, non ci sarebbero problemi nel ritrovare, a partire da questa definizione, le due proprietà che definiscono il massimo comune divisore così come esso viene correntemente definito: le due definizioni si equivalgono, potete leggere a tal proposito questo topic ed in particolare le pagine di Algebra di Di Martino in esso citate.

Il punto è che è da preferirsi la definizione "moderna" quantunque all'apparenza un po' strana perché nel momento in cui si cerca di estendere il concetto di massimo comune divisore nel trattare gli anelli, ci si potrebbe ritrovare nella condizione di non poter dare al termine "maggiore" la consueta accezione, quella cioè legata all'ordinamento usuale tra gli interi, perché assente un ordinamento che ricalchi quello tra gli interi: pensate per esempio ai polinomi ed al massimo comune divisore tra polinomi.

P.S.
Piccola precisazione per quanto riguarda la nomenclatura.
Un lemma è una proposizione minore che si enuncia e si dimostra prima di enunciare e dimostrare una proposizione superiore alla quale si dà il ruolo di teorema. Il termine che cerchi è “corollario”, seppure l’uso di tale termine non sia completamente corretto: un corollario di un teorema è di solito una proposizione che segue in modo immediato dal teorema in questione attraverso una semplificazione/riduzione/specificazione delle ipotesi del teorema stesso, i.e. è come se un corollario di un teorema esprimesse un caso particolare del teorema dal quale discende.
Sarebbe in questo caso più corretto parlare di una caratterizzazione alternativa del concetto di massimo comune divisore, una volta che questo sia stato definito in un certo modo.