Massimo comun divisore e chiarimenti su dimostrazione.

[bla99hf]

Salve,

ho il seguente teorema:
Siano $a, b$ due numeri interi non entrambi nulli. Allora esiste un MCD positivo di $a$ e $b$. Inoltre esistono $\alpha, \beta \in ZZ$ tali che $d = \alphaa + \betab

non scrivo tutta la dimostrazione ma per ora solo la parte che non ho compreso e poi nel caso sottoporrò anche il resto.

Dimostrazione:
Consideriamo l'insieme

$S = {xa + yb | x \in ZZ, y \in ZZ, xa + yb > 0}$

Allora $S sube NN^**$ ed $S != ø$. Sia $d$ il più piccolo degli elementi di S. Dato che $d \in S$ si ha $d > 0$ e $d = \alphaa + \betab$ per opportuni $\alpha, \beta \in ZZ$. Per concludere la dimostrazione è quindi sufficiente far vedere che $d$ è un MCD di $a$ e $b$.


io penso (corregetemi se sbaglio):
se stiamo stiamo considerando $a, b$ elementi non nulli, dal momento che essi possono anche essere negativi, li moltiplichiamo per opportuni valori di $x$ e $y$ per ottenere valori positivi.
Dice anche che $d$ è il più piccolo degli elementi di $S$ quindi $d$ positivo.

Ora a cosa mi serve la $d = \alphaa + \betab$ ??


se potete gentilmente spiegarmelo perchè altrimenti non riesco ad andare avanti nella dimostrazione.
grazie mille.

[G.D.5]

La risposta alla tua ultima domanda sta nel completamento della dimostrazione. E' normale che arrestando la dimostrazione (e più in generale, una qualunque dimostrazione) ad un punto intermedio, poi non capisci l'utilità di una certa posizione.
Ad ogni modo, quella posizione serve per giungere al fatto che nella divisione di un qualunque intero della forma $ax+by$ con l'intero $d$ il resto è $0$, sicché in virtù di un lemma che dovresti avere precedentemente studiato, $d$ è divisore comune di $a$ e $b$.

[bla99hf]

in virtù di un lemma che dovresti avere precedentemente studiato, d è divisore comune di a e b.

certamente, eccolo:
siano $a$ e $b$ due numeri interi. Un numero intero $d$ si dice MCD di $a$ e $b$ se valgono le seguenti proprietà:
(a) $d | a$, $d | b$;
(b) se $c \in ZZ$, $c | a$ e $c | b$ allora $c | d$.




andando avanti nella dimostrazione bisogna quindi in sostanza dimostrare che:
$d|a$ $d|b$ e $c|d$

quindi abbiamo:
dividiamo $a$ per $d$: si ha $a = dq+r$ e $0 <= r < |d| = d$ per $q, r \in ZZ$
Se per assurdo fosse $r != 0$ allora $r > 0$ e $r = a-dq=a-(\alphaa+\betab)q = (1-\alphaq)a + (-\betaq)b$, segue che $r \in S$ ed $r < d$ in contraddizione col fatto che $d$ era stato scelto come il più piccolo elemento in $S$.
Quindi $r = 0$ e pertanto $a = dq$ ossia $d |a$.

la prima parte è stata risolta, però non mi sono chiare alcune cose per le quali mi piacerebbe ricevere cortesemente dei chiarimenti e se quello che io ho pensato a riguardo delle stesse è giusto o meno:

Sia $d$ il più piccolo degli elementi di $S$

perchè altrimenti non potrebbe essere MCD...

se stiamo stiamo considerando a,b elementi non nulli, dal momento che essi possono anche essere negativi, li moltiplichiamo per opportuni valori di x e y per ottenere valori positivi.

è giusta questa cosa?

Se per assurdo fosse r≠0

quindi la definizione circa la divisione tra numeri interi (a me nota) cos'è? un teorema, un postulato etc? che è indicato sul mio libro se non come nozioni di aritmetica.

$(1-\alphaq)a + (-\betaq)b$, segue che $r \in S$

credo che questa appartenenza a $S$ sia ricondotta al fatto che sia si tratti di un numero positivo come detto in precedenza e sia che rispecchi la forma del numero $xa+yb \in S$?

ed $r < d$

perchè? perchè per $r≠0$ abbiamo $0 < r < d$ ?


sono andato avanti nella dimostrazione e non credo di aver incontrato ulteriori difficoltà.
e il chiarimento di questi piccoli intoppi sarebbe molto importante per me.
potete gentilmente chiarirmi questi dubbi?

ancora grazie.

[G.D.5]

"bla99hf":
certamente, eccolo:
siano $a$ e $b$ due numeri interi. Un numero intero $d$ si dice MCD di $a$ e $b$ se valgono le seguenti proprietà:
(a) $d | a$, $d | b$;
(b) se $c \in ZZ$, $c | a$ e $c | b$ allora $c | d$.

Questo non è il lemma al quale facevo riferimento, questa è la definizione di MCD: un lemma è un enunciato enucleato e provato prima di fornire un teorema con annessa dimostrazione per la quale il lemma di cui prima in oggetto risulta essere propedeutico.

Il lemma al quale facevo riferimento è questo:

"Lemma":
$a|b \wedge a|c \Leftrightarrow a|xb+yc, \forall x,y \in \mathbb{Z}$

Dovresti avere la dimostrazione sul tuo testo: qualora così non fosse, falla per esercizio, è abbastanza semplice.

"bla99hf":
andando avanti nella dimostrazione bisogna quindi in sostanza dimostrare che:
$d|a$ $d|b$ e $c|d$

Questo è parzialmente corretto: bisogna provare che esiste $d>0$ tale che valgano le due seguenti condizioni
1) $d|a \wedge d|b$
2) $d'|a \wedge d'|b \Rightarrow d'|d$
e bisogna anche produrre una prova dell'unicità di questo $d>0$.

"bla99hf":
quindi abbiamo:
dividiamo $a$ per $d$: si ha $a = dq+r$ e $0 <= r < |d| = d$ per $q, r \in ZZ$
Se per assurdo fosse $r != 0$ allora $r > 0$ e $r = a-dq=a-(\alphaa+\betab)q = (1-\alphaq)a + (-\betaq)b$, segue che $r \in S$ ed $r < d$ in contraddizione col fatto che $d$ era stato scelto come il più piccolo elemento in $S$.
Quindi $r = 0$ e pertanto $a = dq$ ossia $d |a$.

Non occorre procedere in questo modo: resterebbe infatti ancora da provare che $d|b$. Conviene sfruttare il lemma che ho proposto: per un qualsivoglia $ax+by \in a\mathbb{Z}\times b\mathbb{Z}$, esistono $q,r \in \mathbb{Z}$ con $0\leq r < d$ tali che $ax+by=qd+r \Rightarrow r=ax+by-qd=ax+by-q(\alpha a + \beta b)=a(x-\alpha q) + b(y -\beta q)$, per il lemma si ha che $d|a \wedge d|b$.
Domanda: ma quella è la dimostrazione scritta sul testo?

"bla99hf":

Sia $d$ il più piccolo degli elementi di $S$

perchè altrimenti non potrebbe essere MCD...

Sì.

"bla99hf":

se stiamo stiamo considerando a,b elementi non nulli, dal momento che essi possono anche essere negativi, li moltiplichiamo per opportuni valori di x e y per ottenere valori positivi.

è giusta questa cosa?

Sì.
Attenzione però: potrebbe essere $a=0 \wedge b!=0$ o viceversa.

"bla99hf":

Se per assurdo fosse $r!=0$

quindi la definizione circa la divisione tra numeri interi (a me nota) cos'è? un teorema, un postulato etc? che è indicato sul mio libro se non come nozioni di aritmetica.

Teorema della divisione euclidea in $ZZ$.
Dati $a,b \in \mathbb{Z}$ con $b!=0$, esistono unici gli interi $q,r$ tali che $a=bq+r$ con $0\leq r <|b|$.
Ti faccio notare che l'operazione di divisione non esiste: questa operazione è una finta operazione, è un surrogato della moltiplicazione. La definizione algebrica di operazione è infatti la seguente: dato l'insieme $A$ si dice operazione definita in $A$ ogni applicazione $\circ : A\times A to A$; da questa definizione è evidente che la divisione non è un operazione vera e propria.
Che classe fai?

"bla99hf":

$(1-\alphaq)a + (-\betaq)b$, segue che $r \in S$

credo che questa appartenenza a $S$ sia ricondotta al fatto che sia si tratti di un numero positivo come detto in precedenza e sia che rispecchi la forma del numero $xa+yb \in S$?

Certo.

"bla99hf":

ed $r < d$

perchè? perchè per $r≠0$ abbiamo $0 < r < d$ ?

Per il teorema che ti ho fornito sulla divisione euclidea, si ha che è $0\leq r < d$, se non è $r=0$, allora è $0

Cita

Segnala

[bla99hf]

Ti ringrazio davvero tantissimo per i tuoi chiarimenti.

No sul mio stesso libro che contiene la dimostrazione il lemma che tu dici non c'è ma su un altro testo ho trovato qualcosa a riguardo e penso sia lo stesso:

Se $c$ è un divisore comune di $a$ e $b$, allora $c$ divide ogni intero della forma $sa+tb$ con $s$ e $t$ in $ZZ$, cioè $c|a$ e $c|b \Rightarrow c|sa + tb AA s,t \in ZZ$.

in base a quello che tu mi hai detto:

Questo è parzialmente corretto: bisogna provare che esiste d>0 tale che valgano le due seguenti condizioni
1) $d|a ^^ d|b$
2) $d'|a ^^ d'|b ⇒ d'|d$
e bisogna anche produrre una prova dell'unicità di questo d>0.

che $d$ esista e che è maggiore di zero l'abbiamo detto all'inizio infatti avevamo $d \in S$, $d > 0$ e $d=\alphaa+\betab$.

L'unicità di questo $d$ è data quindi da questi opportuni $\alpha$ e $\beta \in ZZ$ che incontrerò nella seconda parte della dimostrazione?
infatti avanti nella dimostrazione (dopo aver dimostrato $d|b$ in modo analogo a $d|a$...) avrò la seguente:
Per dimostrare che $d$ è un MCD di $a$ e $b$ resta da dimostrare che se $c \in ZZ$, $c|a$ e $c|b \Rightarrow c|d$. Se $c|a$ e $c|b$, si ha $a=a'c, b=b'c$ con $a',b' \in ZZ$ e quindi $d=\alphaa+\betab=(\alphaa'+\betab')c$, cioè $c|d$.

Domanda: ma quella è la dimostrazione scritta sul testo?

Sì. Quindi seguendo tale dimostrazione non c'è bisogno di tenere conto del lemma che mi hai fornito all'inizio?

spero possiate darmi per favore questi ultimi chiarimenti di cui ho bisogno.
grazie.

[G.D.5]

La dimostrazione scritta sul tuo testo non tiene conto del lemma che ho citato: infatti mi informi che il tuo libro dimostra $d|b$ in maniera analoga a quanto fatto per provare $d|a$; ovviamente non è legge dimostrare il fatto oggetto del contendere seguendo quello che ho fatto io, la liceità della tua dimostrazione non è intaccata dal non utilizzo del lemma.

Il lemma che hai trovato sull'altro testo è qualche cosa di meno forte del mio: il mio è una coimplicazione, il tuo una implicazione.

Quanto alla questione dell'esistenza e unicità di $d$, non è vero che $d$ esiste ed è maggiore di $0$ perché lo si è detto all'inizio: per definizione si ha che $S={ax+by : x,y \in \mathbb{Z} \wedge ax+by>0}$ e $d$ è il minimo di questo insieme, ergo per posizione iniziale sappiamo che $d$ è maggiore di $0$ e esiste sì, ma con il ruolo di minimo di $S$, non con il ruolo di $MCD(a,b)$; il nostro obiettivo è provare che $d$ è il $MCD(a,b)$ e in questo modo avremo provato l'esistenza di $d$ con ruolo di $MCD(a,b)$.
L'unicità non si prova con l'argomentazione di $c \in \mathbb{Z}$ tale che $c|a \wedge c|b \Rightarrow c|d$: questa argomentazione è necessaria sempre per provare che $d$ è un $MCD(a,b)$, essa è infatti la proprietà 2) di cui ti parlo nello spezzone di post cha hai quotato.
La prova dell'unicità si esegue ammettendo che esista un ulterio $e \in \mathbb{Z}$ tale da rispettare le proprietà 1) e 2) e mostrando che in ragione dell'osservanza delle predette proprietà allora risulta $e=d$.

[bla99hf]

riportando quanto da te detto

La prova dell'unicità si esegue ammettendo che esista un ulterio e∈ℤ tale da rispettare le proprietà 1) e 2) e mostrando che in ragione dell'osservanza delle predette proprietà allora risulta e=d.

il testo non riporta niente a riguardo. E la dimostrazione l'ho già postata interamente anche se pezzo per pezzo:

Dimostrazione:
Consideriamo l'insieme

S={xa+yb|x∈ℤ,y∈ℤ,xa+yb>0}

Allora S⊆ℕ⋆ ed S≠ø. Sia d il più piccolo degli elementi di S. Dato che d∈S si ha d>0 e d=αa+βb per opportuni α,β∈ℤ. Per concludere la dimostrazione è quindi sufficiente far vedere che d è un MCD di a e b.

dividiamo a per d: si ha a=dq+r e 0≤r<|d|=d per q,r∈ℤ
Se per assurdo fosse r≠0 allora r>0 e r=a-dq=a-(αa+βb)q=(1-αq)a+(-βq)b, segue che r∈S ed r Quindi r=0 e pertanto a=dq ossia d|a.

e similmente si dimostra $d|b$

Per dimostrare che d è un MCD di a e b resta da dimostrare che se c∈ℤ, c|a e c|b⇒c|d. Se c|a e c|b, si ha a=a'c,b=b'c con a',b'∈ℤ e quindi d=αa+βb=(αa'+βb')c, cioè c|d.

questo conclude la dimostrazione.

quindi questa unicità che a quanto ho capito non è stata dimostrata, rende questa dimostrazione incompleta? e quindi è necessario dimostrarla?
Ma nel teorema che precede la dimostrazione c'è scritto:

Siano a,b due numeri interi non entrambi nulli. Allora esiste un MCD positivo di a e b. Inoltre esistono α,β∈ℤ tali che d=αa+βb

Quell' "un" vuol dire che è unico e che quindi considera a priori l'unicità di tale elemento senza dimostrarlo?

Inoltre ho trovato su un altro testo tale frase:

Si parla di un MCD e non del MCD tra due elementi, perchè se $d$ gode delle proprietà (a) e (b), anche ogni associato di $d$ (e quindi $\pmd$ nel caso di $ZZ$) gode delle stesse proprietà. In generale ,quando si parla del MCD in $ZZ$, si intende il MCD positivo.

essa comunque non parla di unicità come da te intesa. ma solo di valore positivo.

[G.D.5]

La dimostrazione che hai trovato sul testo cui fai riferimento non è incompleta, per il semplice fatto che nell'enunciato del teorema non si fa riferimento all'unicità.
In $\mathbb{Z}$, dati gli interi $a,b$ esistono due $MCD$, uno positivo e uno negativo, ma quello cui si fa riferimento quando si parla del $MCD(a,b)$ è quello positivo: è per questo che si prova che esso è unico.

[bla99hf]

perdonami ma non mi è chiaro.
prima dici che:

nell'enunciato del teorema non si fa riferimento all'unicità.

poi mi dici che:

In ℤ, dati gli interi a,b esistono due MCD, uno positivo e uno negativo, ma quello cui si fa riferimento quando si parla del MCD(a,b) è quello positivo: è per questo che si prova che esso è unico.

e questo poi l'ho detto anche io

Ma nel teorema:

Siano a,b due numeri interi non entrambi nulli. Allora esiste un MCD positivo di a e b. Inoltre esistono α,β∈ℤ tali che d=αa+βb

viene fatto riferimento all'unicità all'interno del teorema o sbaglio?
(se per unicità stiamo considerando per l'appunto solo un valore positivo... perchè ancora non l'ho capito poiche mi hai datto che:)

La prova dell'unicità si esegue ammettendo che esista un ulterio e∈ℤ tale da rispettare le proprietà 1) e 2) e mostrando che in ragione dell'osservanza delle predette proprietà allora risulta e=d.

[G.D.5]

Se tu mi chiedi "Questa dimostrazione è completa?" io non posso fare altro che risponderti "sì" o "no" a seconda di quella che la dimostrazione vuole provare.

Il tuo enunciato, col quale hai aperto il topic è

"bla99hf":
Siano $a, b$ due numeri interi non entrambi nulli. Allora esiste un MCD positivo di $a$ e $b$. Inoltre esistono $\alpha, \beta \in ZZ$ tali che $d = \alphaa + \betab

quindi, se vogliamo dimostrare questo teorema non dobbiamo dimostrare che $d>0$ tale che $d=MCD(a,b)$ è unico, per il semplice fatto che non è richiesto nel teorema.
Ciò non toglie che di $d>0$ tale che $d=MCD(a,b)$ ce ne sia uno solo.
Il fatto che $d$ sia positivo non implica la sua unicità.
Dire "esiste un" non esclude l'esistenza di "altri".

[bla99hf]

E' chiaro.
Quindi abbiamo finito. Sei stato molto chiaro e paziente e hai tolto ogni mio dubbio.


mille grazie tantissimo davvero!!

[G.D.5]

Figurati, per così poco.