Massimo comun divisore
un altro quesito "accessibile" a tutti
si dimostri l'esitenza e l'unicità del massimo comun divisore di due numeri non entrambi nulli.
buon lavoro, ubermensch
si dimostri l'esitenza e l'unicità del massimo comun divisore di due numeri non entrambi nulli.
buon lavoro, ubermensch
Risposte
quando avro' tempo (significa chissa quando) ci provero', e spero di riuscirci =)
buona fortuna allora!
qualcun altro ci sta provando? o il quesito accessibile e inaccessibile?
qualcun altro ci sta provando? o il quesito accessibile e inaccessibile?
vabbè... allora la metto io la dimostrazione; così la ripasso e così eafkuor avrà un primo notevole esempio di dimostrazione bella e difficile. studiandosela avrà sicuramente dei profitti a livello di ragionamento.
do, per chi non lo conoscesse, il seguente
PRINCIPIO DEL MINIMO:
comunque preso un sottoinsieme dei naturali non vuoto, esso ammette un elemento minimo, ossia più piccolo di tutti gli altri e appartenente all'insieme.
la prima difficoltà consiste nel sapere cosa dimostrare, ovvero nel dare una corretta definizione di MCD.
siano a,b interi, non entrambi nulli, d=MCD(a,b) se e solo se:
1) d>=1
2) d divide a e divide b; abbreviato con d|a,b
3) se d'|a,b allora d'|d
in particolare, la terza condizione ci assicura che il divisore comune sia proprio il massimo comun divisore.
Dimostrazione dell'esistenza e unicità del MCD(a,b)
sia S={ax+by>0, a,b,x,y interi}
dimostriamo innanzitutto che questo insieme è non vuoto
se a>0 allora a=a*1+b*0, quindi a appartiene ad S
se a<0 allora -a=a*(-1)+b*0, quindi -a appartiene ad S
se a=0, allora, per hp, b
0; applicando lo stesso precedente ragionamento su b si ottiene che b o -b appartiene ad S
poichè S è non vuoto ed è contenuto nei naturali, allora, per il principio del minimo, esiste d=min(S)=ax'+by', con x' e y' fissati
vogliamo ora dimostrare che valgono le tre condizioni del MCD
1) d>=1; è vera banalmente perchè d appartiene ad S che è contenuto in N
2) dimostro che d|a,b, utilizzando il seguente fatto, che non dimostro per brevità: d|a,b <---> d|ax+by, comunque scelti x e y
pertanto dimostrare che d|ax+by equivale a dimostrare che d|a,b
dividiamo ax+by per d ( si osservi che questa divisione si può fare perchè d è, per definizione, più piccolo di qualunque numero esprimibile come ax+by) otteniamo:
ax + by = dq + r, essendo q il quoziente e r il resto
quindi 0<=r
sostituiamo nella precedente espressione d=ax'+by', dopo un paio di semplici passaggi si ha:
r = a(x-x'q) + b(y-y'q),
ora, se r<0 allora r appartiene ad S (infatti si avrebbe un numero che si può scrivere nella forma ax+by e che è positivo).
ma r
ne consegue che r=0; da cui, tornando all'espressione iniziale della divisione, si ha:
ax+by=dq, da cui segue che d|ax+by da cui segue, come già detto, d|a,b
ora dimostriamo la terza condizione (questa è semplicissima!)
se d'|a,b allora divide, in particolare ax'+by'=d, quindi d'|d
dimostriamo ora l'unicità:
procediamo nel seguente modo:
abbiamo d=MCD(a,b) tale che 1) d|a,b 2) se d'|a,b allora d'|d
supponiamo di avere un altro d''=MCD(a,b) tale che 1.bis)d''|a,b
e 2.bis) se d'''|a,b allora d'''|d''
dimostriamo che d|d'' e d''|d, pertanto, poichè sono maggiori di 1 per ipotesi, allora d''=d
dalla 1 abbiamo che d|a,b . poniamo d'''=d, dalla 2.bis abbiamo che d|d''
d'altra parte, dalla 1.bis abbiamo che d''|a,b . poniamo d'=d'', dalla 2 abbiamo che d''|d
quindi d''=d
mamma mia che faticaccia!!!
spero che qualcuno mi ricompensi almeno leggendola.
ciao, ubermensch
do, per chi non lo conoscesse, il seguente
PRINCIPIO DEL MINIMO:
comunque preso un sottoinsieme dei naturali non vuoto, esso ammette un elemento minimo, ossia più piccolo di tutti gli altri e appartenente all'insieme.
la prima difficoltà consiste nel sapere cosa dimostrare, ovvero nel dare una corretta definizione di MCD.
siano a,b interi, non entrambi nulli, d=MCD(a,b) se e solo se:
1) d>=1
2) d divide a e divide b; abbreviato con d|a,b
3) se d'|a,b allora d'|d
in particolare, la terza condizione ci assicura che il divisore comune sia proprio il massimo comun divisore.
Dimostrazione dell'esistenza e unicità del MCD(a,b)
sia S={ax+by>0, a,b,x,y interi}
dimostriamo innanzitutto che questo insieme è non vuoto
se a>0 allora a=a*1+b*0, quindi a appartiene ad S
se a<0 allora -a=a*(-1)+b*0, quindi -a appartiene ad S
se a=0, allora, per hp, b
0; applicando lo stesso precedente ragionamento su b si ottiene che b o -b appartiene ad Spoichè S è non vuoto ed è contenuto nei naturali, allora, per il principio del minimo, esiste d=min(S)=ax'+by', con x' e y' fissati
vogliamo ora dimostrare che valgono le tre condizioni del MCD
1) d>=1; è vera banalmente perchè d appartiene ad S che è contenuto in N
2) dimostro che d|a,b, utilizzando il seguente fatto, che non dimostro per brevità: d|a,b <---> d|ax+by, comunque scelti x e y
pertanto dimostrare che d|ax+by equivale a dimostrare che d|a,b
dividiamo ax+by per d ( si osservi che questa divisione si può fare perchè d è, per definizione, più piccolo di qualunque numero esprimibile come ax+by) otteniamo:
ax + by = dq + r, essendo q il quoziente e r il resto
quindi 0<=r
sostituiamo nella precedente espressione d=ax'+by', dopo un paio di semplici passaggi si ha:
r = a(x-x'q) + b(y-y'q),
ora, se r<0 allora r appartiene ad S (infatti si avrebbe un numero che si può scrivere nella forma ax+by e che è positivo).
ma r
ne consegue che r=0; da cui, tornando all'espressione iniziale della divisione, si ha:
ax+by=dq, da cui segue che d|ax+by da cui segue, come già detto, d|a,b
ora dimostriamo la terza condizione (questa è semplicissima!)
se d'|a,b allora divide, in particolare ax'+by'=d, quindi d'|d
dimostriamo ora l'unicità:
procediamo nel seguente modo:
abbiamo d=MCD(a,b) tale che 1) d|a,b 2) se d'|a,b allora d'|d
supponiamo di avere un altro d''=MCD(a,b) tale che 1.bis)d''|a,b
e 2.bis) se d'''|a,b allora d'''|d''
dimostriamo che d|d'' e d''|d, pertanto, poichè sono maggiori di 1 per ipotesi, allora d''=d
dalla 1 abbiamo che d|a,b . poniamo d'''=d, dalla 2.bis abbiamo che d|d''
d'altra parte, dalla 1.bis abbiamo che d''|a,b . poniamo d'=d'', dalla 2 abbiamo che d''|d
quindi d''=d
mamma mia che faticaccia!!!
spero che qualcuno mi ricompensi almeno leggendola.
ciao, ubermensch
ehm non lo so' se potevo farcela... e poi ero bloccato dal fatto che la cosa da dimostrare era talmente ovvia che non mi sembrava utile dimostrarla!! cioe' se i due numeri hanno un divisore comune, allora potrebbe essere quello maggiore. se ce n'e' un altro piu' grande e' automatico che quello diventa il maggiore!! cioe' due divisori comuni non possono essere entrambi il maggiore, mi sembrava ovvio e non dimostrabile. ora mi leggo la dim.
tu ti riferisci all'unicità, infatti è la parte più semplice della dimostrazione, la quale comunque va dimostrata; imparerai che spesso l'intuito porta fuori strada e le cose che sembrano banali non lo sono oppure sono sbagliate. riguardo a questa dimostrazione, io chiedevo soprattutto l'esistenza del MCD, ed è banale che esista, ma come ti accorgerai dalla dimostrazione, non è affatto banale dimostrarlo.
ciao, ubermensch
ciao, ubermensch
scusa l'ingenuità uber, ma se io indico con D l'insieme dei divisori positivi comuni di due numeri interi a e b, sicuramente non è vuoto poichè contiene almeno il numero 1, e sicuramente è finito poichè ha al massimo min(a,b) elementi. Dunque deve avere un elemento massimo (che è unico) per l'ordinamento di Z, che è totale. O no?
la tua osservazione è davvero molto interessante... lasciami un momento per rifletterci.
ciao, ubermensch
ciao, ubermensch
uber al di là di qualche dettaglio tecnico mi sembra che sia la stessa cosa che avevo detto io sul mcm...
è vero maverik... lasciatemi riflettere un momento, vi dirò..
La dimostrazione e' corretta, e l'osservazione della dimostrazione piu' elegante e semplice pure.
Provate ora ad indagare sul M.C.D. tra due polinomi. Scoprirete che non e' piu' unico, anche se esiste sempre.
Buon lavoro!
Luca.
Provate ora ad indagare sul M.C.D. tra due polinomi. Scoprirete che non e' piu' unico, anche se esiste sempre.
Buon lavoro!
Luca.
bene... ho cercato di riflettere un pò sulla questione, cercando anche confronti con teoremi che si dimostrano come conseguenze; la mia modesta conclusione, è che entrambe le vostre dimostrazioni sono singolarmente corrette, ma non convenienti, nel senso che non permettono di dimostrare altri fatti; ad esempio, la dimostrazione classica del MCD, che è quella che ho messo io, dice anche che l' MCD(a,b) si scrive sempre come combinazione lineare di a e b, che è una cosa molto utile per dimostrare altri fatti e per risolvere, per chi li conoscesse, ad esempio i sistemi congruenziali; inoltre, le dimostrazioni classiche permettono di dimostrare quelle semplici regole di calcolo che caratterizzano l'MCD e il mcm "prodotto dei fattori comuni presi con il massimo esponente" e simili...
quindi, poichè io avevo chiesto di dimostrare l'esistenza e l'unicità del MCD e il mcm, le vostre dimostrazioni sono corrette; tuttavia, per i motivi sopra detti, è chiaro che occorre utilizzarne altre per costruirvi sopra.
ciao, ubermensch
quindi, poichè io avevo chiesto di dimostrare l'esistenza e l'unicità del MCD e il mcm, le vostre dimostrazioni sono corrette; tuttavia, per i motivi sopra detti, è chiaro che occorre utilizzarne altre per costruirvi sopra.
ciao, ubermensch
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo