Comun divisori
Ciao a tutti, ho un dubbio su una dimostrazione.
Dati due numeri interi, come è possibile dimostrare che il comun divisore più grande è sempre divisibile per qualunque altro dei divisori comuni?
Grazie.
Dati due numeri interi, come è possibile dimostrare che il comun divisore più grande è sempre divisibile per qualunque altro dei divisori comuni?
Grazie.
Risposte
Come fa lui ... 
- Prendo due interi $a$ e $b$ (per non complicarci la vita li prendiamo positivi, per gli altri casi ci si pensa dopo ...
)
- Prendo tutti i divisori comuni di $a$ e $b$
- Adesso definisco un oggetto che chiamerò "pippo" e che ha le seguenti caratteristiche (se esiste o meno non importa, io vi dico come deve essere fatto): è un numero intero positivo, è un divisore comune di $a$ e $b$ ed è un multiplo tutti i divisori comuni di $a$ e $b$
- Adesso definisco un altro oggetto che chiamerò "paperino" il quale invece ha queste caratteristiche (anche questo se esiste o meno non importa, io vi dico come deve essere fatto): è un numero intero positivo, è un divisore comune di $a$ e $b$ ed è maggiore (o uguale) di tutti i divisori comuni di $a$ e $b$
- Dimostro che sono la stessa "cosa", lo stesso oggetto (prendo a prestito la dimostrazione di bobus): sappiamo che "paperino" è un divisore comune di $a$ e $b$ ed è maggiore (o uguale) di ogni divisore comune $c$; sappiamo anche che, essendo "pippo" un divisore comune, $\text(pippo )<=\text( paperino)$.
Supponiamo per assurdo che sia $\text(pippo )<\text( paperino)$, per quanto detto finora sappiamo che "pippo" è un multiplo di "paperino" (vedi sua definizione) perciò sarà $\text(pippo )=k*\text(paperino)$ con $k$ intero positivo.
Sostituendo otteniamo $k*\text(paperino)<\text(paperino)$ da cui $k<1$. Assurdo, perciò $\text(pippo )=\text( paperino)$.
Attenzione: ho dimostrato solo l'eguaglianza tra i due oggetti non ne ho dimostrato l'esistenza né lo supposta, ho solo utilizzato le caratteristiche, le proprietà dei due oggetti per dimostrarne l'uguaglianza.
Quindi "pippo" e "paperino" sono la stessa cosa ovvero un oggetto che è un numero intero positivo, è un divisore comune di $a$ e $b$ , è maggiore (o uguale) di tutti i divisori comuni di $a$ e $b$ ed è un multiplo di tutti i divisori comuni di $a$ e $b$.
Dulcis in fundo, questo oggetto mi va di chiamarlo MCD ... però non ne ho ancora dimostrato l'esistenza ... ...
Cordialmente, Alex
- Prendo due interi $a$ e $b$ (per non complicarci la vita li prendiamo positivi, per gli altri casi ci si pensa dopo ...
)- Prendo tutti i divisori comuni di $a$ e $b$
- Adesso definisco un oggetto che chiamerò "pippo" e che ha le seguenti caratteristiche (se esiste o meno non importa, io vi dico come deve essere fatto): è un numero intero positivo, è un divisore comune di $a$ e $b$ ed è un multiplo tutti i divisori comuni di $a$ e $b$
- Adesso definisco un altro oggetto che chiamerò "paperino" il quale invece ha queste caratteristiche (anche questo se esiste o meno non importa, io vi dico come deve essere fatto): è un numero intero positivo, è un divisore comune di $a$ e $b$ ed è maggiore (o uguale) di tutti i divisori comuni di $a$ e $b$
- Dimostro che sono la stessa "cosa", lo stesso oggetto (prendo a prestito la dimostrazione di bobus): sappiamo che "paperino" è un divisore comune di $a$ e $b$ ed è maggiore (o uguale) di ogni divisore comune $c$; sappiamo anche che, essendo "pippo" un divisore comune, $\text(pippo )<=\text( paperino)$.
Supponiamo per assurdo che sia $\text(pippo )<\text( paperino)$, per quanto detto finora sappiamo che "pippo" è un multiplo di "paperino" (vedi sua definizione) perciò sarà $\text(pippo )=k*\text(paperino)$ con $k$ intero positivo.
Sostituendo otteniamo $k*\text(paperino)<\text(paperino)$ da cui $k<1$. Assurdo, perciò $\text(pippo )=\text( paperino)$.
Attenzione: ho dimostrato solo l'eguaglianza tra i due oggetti non ne ho dimostrato l'esistenza né lo supposta, ho solo utilizzato le caratteristiche, le proprietà dei due oggetti per dimostrarne l'uguaglianza.
Quindi "pippo" e "paperino" sono la stessa cosa ovvero un oggetto che è un numero intero positivo, è un divisore comune di $a$ e $b$ , è maggiore (o uguale) di tutti i divisori comuni di $a$ e $b$ ed è un multiplo di tutti i divisori comuni di $a$ e $b$.
Dulcis in fundo, questo oggetto mi va di chiamarlo MCD ... però non ne ho ancora dimostrato l'esistenza ...
...Cordialmente, Alex
"axpgn":
Come fa lui ...
- Prendo due interi $a$ e $b$ (per non complicarci la vita li prendiamo positivi, per gli altri casi ci si pensa dopo ...
- Prendo tutti i divisori comuni di $a$ e $b$
- Adesso definisco un oggetto che chiamerò "pippo" e che ha le seguenti caratteristiche (se esiste o meno non importa, io vi dico come deve essere fatto): è un numero intero positivo, è un divisore comune di $a$ e $b$ ed è un multiplo tutti i divisori comuni di $a$ e $b$
- Adesso definisco un altro oggetto che chiamerò "paperino" il quale invece ha queste caratteristiche (anche questo se esiste o meno non importa, io vi dico come deve essere fatto): è un numero intero positivo, è un divisore comune di $a$ e $b$ ed è maggiore (o uguale) di tutti i divisori comuni di $a$ e $b$
- Dimostro che sono la stessa "cosa", lo stesso oggetto (prendo a prestito la dimostrazione di bobus): sappiamo che "paperino" è un divisore comune di $a$ e $b$ ed è maggiore (o uguale) di ogni divisore comune $c$; sappiamo anche che, essendo "pippo" un divisore comune, $\text(pippo )<=\text( paperino)$.
Supponiamo per assurdo che sia $\text(pippo )<\text( paperino)$, per quanto detto finora sappiamo che "pippo" è un multiplo di "paperino" (vedi sua definizione) perciò sarà $\text(pippo )=k*\text(paperino)$ con $k$ intero positivo.
Sostituendo otteniamo $k*\text(paperino)<\text(paperino)$ da cui $k<1$. Assurdo, perciò $\text(pippo )=\text( paperino)$.
Attenzione: ho dimostrato solo l'eguaglianza tra i due oggetti non ne ho dimostrato l'esistenza né lo supposta, ho solo utilizzato le caratteristiche, le proprietà dei due oggetti per dimostrarne l'uguaglianza.
Quindi "pippo" e "paperino" sono la stessa cosa ovvero un oggetto che è un numero intero positivo, è un divisore comune di $a$ e $b$ , è maggiore (o uguale) di tutti i divisori comuni di $a$ e $b$ ed è un multiplo di tutti i divisori comuni di $a$ e $b$.
Dulcis in fundo, questo oggetto mi va di chiamarlo MCD ... però non ne ho ancora dimostrato l'esistenza ...
Cordialmente, Alex
Scusa se insisto Alex, ma io penso che la tua dimostrazione (e quella di bobus) dimostrino una cosa diversa da quello che chiede l'esercizio.
L'implicazione che a me interessa dell'esercizio dice: Dimostrare che se [tex]d[/tex] è un divisore comune di [tex]a[/tex] e [tex]b[/tex] tale che per ogni altro divisore comune [tex]c[/tex] di [tex]a[/tex] e [tex]b[/tex] si ha che [tex]c[/tex] è minore o uguale di [tex]d[/tex] allora [tex]d[/tex] è il MCD.
Nella tua dimostrazione tu dimostri che SE il MCD esiste allora deve essere per forza uguale al maggiore tra i comun divisori, mentre il teorema intende che tutte le volte che il massimo nell'insieme dei comun divisori esiste allora automaticamente esiste anche il MCD e le due cose sono uguali. Il teorema ti sta dicendo io ho questo numero [tex]d[/tex] che è il massimo di tutti i divisori, dimostrami che tale numero soddisfa anche le condizioni della definizione di MCD. Praticamente data per ipotesi l'esistenza di [tex]d[/tex] ti chiede di provare l'esistenza del MCD e la loro uguaglianza. L'enunciato altrimenti sarebbe dovuto essere: Supposta l'esistenza del MCD, dimostrare che se [tex]d[/tex] è un divisore comune di [tex]a[/tex] e [tex]b[/tex] tale che per ogni altro divisore comune [tex]c[/tex] di [tex]a[/tex] e [tex]b[/tex] si ha che [tex]c[/tex] è minore o uguale di [tex]d[/tex] allora [tex]d[/tex] è il MCD.
Io sono dell'idea che la il teorema andrebbe enunciato solo dopo aver dimostrato l'esistenza a priori del MCD. Dimostrare che una cosa che esiste (o che si suppone tale, come in questo caso [tex]d[/tex] nell'ipotesi dell'enunciato) è uguale ad un altra vuol dire implicitamente mostrare che supposta l'esistenza della prima allora esiste anche l'altra. La conclusione dell'implicazione deve essere vera o falsa, ma se la cosa non esiste neanche non ha proprio senso l'implicazione.
Siano $a$ e $b$ due interi positivi. Sia $E$ l'insieme degli interi positivi esprimibili come combinazione $ax+by$ con $x$ e $y$ interi, sia $d$ il minimo degli elementi di $E$ (chiaramente esiste), e scriviamo $d=as+bt$ con $s$ e $t$ interi.
Fatto 1. $d$ è un divisore comune di $a$ e $b$.
[Infatti facendo la divisione con resto di $a$ per $d$ abbiamo $a = qd+r$ con $0 le r
Fatto 2. $d$ è il massimo dei divisori comuni positivi di $a$ e $b$.
[Infatti se $g$ è un divisore comune positivo di $a$ e $b$ allora $g$ chiaramente divide $as+bt = d$, in particolare $g le d$.]
Fatto 3. Tutti i divisori comuni positivi di $a$ e $b$ dividono $d$.
[Stessa dimostrazione del fatto 2.]
Convince?
Fatto 1. $d$ è un divisore comune di $a$ e $b$.
[Infatti facendo la divisione con resto di $a$ per $d$ abbiamo $a = qd+r$ con $0 le r
Fatto 2. $d$ è il massimo dei divisori comuni positivi di $a$ e $b$.
[Infatti se $g$ è un divisore comune positivo di $a$ e $b$ allora $g$ chiaramente divide $as+bt = d$, in particolare $g le d$.]
Fatto 3. Tutti i divisori comuni positivi di $a$ e $b$ dividono $d$.
[Stessa dimostrazione del fatto 2.]
Convince?
Si Martino convince, l'unico problema è che tale dimostrazione nel libro viene dopo l'enunciato, quindi in teoria non si potrebbe usare. In pratica invece secondo me l'unico modo corretto di dimostrare l'enunciato è di usare questo risultato da te citato
Secondo me vi state perdendo e vi state meravigliando dell'ovvio: cioè del fatto che nella soluzione dell'esercizio si dia per buono che esiste, almeno in quel caso, il \( \gcd \). Che è una cosa che succede di continuo: basti pensare alla presentazione assiomatica di \( \mathbb{R} \) o a quella di \( \mathbb{N} \) con gli assiomi di Peano.
"G.D.":
Secondo me vi state perdendo e vi state meravigliando dell'ovvio: cioè del fatto che nella soluzione dell'esercizio si dia per buono che esiste, almeno in quel caso, il \( \gcd \). Che è una cosa che succede di continuo: basti pensare alla presentazione assiomatica di \( \mathbb{R} \) o a quella di \( \mathbb{N} \) con gli assiomi di Peano.
Non è proprio la stessa cosa però, quelli si chiamano assiomi apposta. Comunque alla fine era solo un mio dubbio, non è così importante.
Più tardi aggiungo qualcosa perché in realtà la similitudine c'è, secondo me.
Ma io non ho supposto l'esistenza del mcd. Ho solo definito un altro numero d (la cui esistenza è garantita dal principio del buon ordinamento) che ho mostrato essere uguale al massimo dei divisori comuni.
@Martino
Non ce la fai, non ce la puoi fare ... a convincerlo ...
Non ce la fai, non ce la puoi fare ... a convincerlo ...
Nel testo dell'esercizio si fa esplicita menzione del \( \gcd \).
"Martino":
Ma io non ho supposto l'esistenza del mcd. Ho solo definito un altro numero d (la cui esistenza è garantita dal principio del buon ordinamento) che ho mostrato essere uguale al massimo dei divisori comuni.
Infatti, tu non hai supposto l'esistenza. L'hai semplicemente dimostrata, che è proprio quello che serve...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo