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
Prova ad usare l'identità di Bezout.
Se non vuoi usarla, puoi usare il teorema fondamentale dell'aritmetica e procedere per assurdo.
Se non vuoi usarla, puoi usare il teorema fondamentale dell'aritmetica e procedere per assurdo.
Grazie della risposta. Il fatto è che nel libro "Algebra" di Di Martino questo teorema viene prima sia della scomposizione in fattori primi che dell'identità di Bezout. Per questo mi chiedevo se è possibile dimostrarlo senza ricorrere alla scomposizione
"keineahnung":
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.
Sono confuso, in quanto per come la sapevo io questa proprietà era parte della definizione, tu che definizione usi allora?
Parte della definizione di cosa?
Di massimo comun divisore.
No, la un numero è massimo comun divisore di due interi se verifica due condizioni: è divisore di entrambi e può essere divisi per ogni altro comun divisore.
Qui sto chiedendo un altra cosa. Supponi di considerare l'insieme di tutti i divisori comuni di due numeri e di prendere il massimo tra tutti, come si fa a dimostrare che tale numero è divisibile per tutti gli altri nell'insieme?
Qui sto chiedendo un altra cosa. Supponi di considerare l'insieme di tutti i divisori comuni di due numeri e di prendere il massimo tra tutti, come si fa a dimostrare che tale numero è divisibile per tutti gli altri nell'insieme?
Dati due interi $a$ e $b$, ogni divisore comune ad entrambi deve contenere (nella sua scomposizione in fattori primi) fattori contenuti sia nella scomposizione di $a$ che in quella di $b$; ora poniamo che esista un divisore comune $m$ che non divida l'MCD di $a$ e $b$, questo significa che $m$ conterrebbe un fattore primo non contenuto nell'MCD; ma ciò non è possibile perché basterebbe moltiplicare l'MCD per questo fattore mancante per ottenere un divisore comune maggiore dell'MCD che a questo punto non sarebbe più tale contraddicendo l'ipotesi; ok?
La dimostrazione non è finita perché questo è il caso in cui ho supposto che ci fosse un fattore diverso mentre va esaminato il caso in cui i fattori primi siano uguali ma diversi gli esponenti ... lascio a te (ma la dimostrazione è analoga ...
)
Cordialmente, Alex
La dimostrazione non è finita perché questo è il caso in cui ho supposto che ci fosse un fattore diverso mentre va esaminato il caso in cui i fattori primi siano uguali ma diversi gli esponenti ... lascio a te (ma la dimostrazione è analoga ...
)Cordialmente, Alex
Grazie della risposta Alex, ma come dicevo sopra nel testo di Di Martino questo teorema viene prima della scomposizione in fattori primi quindi mi chiedevo se c'era un modo di dimostrarlo senza ricorrere alla scomposizione ma solo usando la definizione di divisibilità tra numeri interi
Immagino la tua domanda si riferisca al "se" dell'esercizio 4.28, giusto?
Se è così, le ipotesi che abbiamo sono che \(\displaystyle d \) è un divisore comune di \(\displaystyle a \) e \(\displaystyle b \) e per ogni divisore comune \(\displaystyle c \) di \(\displaystyle a \) e \(\displaystyle b \) si ha che \(\displaystyle c \leq d \). Vogliamo dimostrare che \(\displaystyle d=(a,b) \).
Per ipotesi abbiamo che \(\displaystyle (a,b) \leq d \). Supponiamo per assurdo che \(\displaystyle (a,b) < d \), siccome per ipotesi \(\displaystyle d | (a,b) \), abbiamo che \(\displaystyle (a,b) = dk \) dove \(\displaystyle k \) è un intero maggiore o uguale a \(\displaystyle 1 \).
Quindi \(\displaystyle dk < d \), da cui \(\displaystyle k < 1 \), contraddizione. Perciò \(\displaystyle (a,b) = d \).
Se è così, le ipotesi che abbiamo sono che \(\displaystyle d \) è un divisore comune di \(\displaystyle a \) e \(\displaystyle b \) e per ogni divisore comune \(\displaystyle c \) di \(\displaystyle a \) e \(\displaystyle b \) si ha che \(\displaystyle c \leq d \). Vogliamo dimostrare che \(\displaystyle d=(a,b) \).
Per ipotesi abbiamo che \(\displaystyle (a,b) \leq d \). Supponiamo per assurdo che \(\displaystyle (a,b) < d \), siccome per ipotesi \(\displaystyle d | (a,b) \), abbiamo che \(\displaystyle (a,b) = dk \) dove \(\displaystyle k \) è un intero maggiore o uguale a \(\displaystyle 1 \).
Quindi \(\displaystyle dk < d \), da cui \(\displaystyle k < 1 \), contraddizione. Perciò \(\displaystyle (a,b) = d \).
Questo è un po' diverso dal quesito iniziale (sottilmente diverso ma non uguale ... )
)
Si bobus esatto è quello l'esercizio. La tua dimostrazione è sensata però assume a priori l'esistenza del MCD, invece nel testo anche quella è dimostrata successivamente.
Il MCD è definito come quel numero che è sia comun divisore che divisibile a sua volta per ogni altro divisore comune.
Per ipotesi si sa che la prima delle due condizioni è verificata, quindi per dimostrare che d è il MCD bisogna dimostrare che vale anche la seconda, il tutto senza assumere a priori l'esistenza del MCD. Io la interpreto così.
Il MCD è definito come quel numero che è sia comun divisore che divisibile a sua volta per ogni altro divisore comune.
Per ipotesi si sa che la prima delle due condizioni è verificata, quindi per dimostrare che d è il MCD bisogna dimostrare che vale anche la seconda, il tutto senza assumere a priori l'esistenza del MCD. Io la interpreto così.
No, per niente ... premesso che io non conosco il testo originale (che mi piacerebbe conoscere) e quindi mi baso su quanto detto da bobus, lui dimostra che SE esiste un numero che soddisfa quelle ipotesi ALLORA è il massimo tra i divisori ...
Axpgn domani se vuoi ti posto il testo esatto, adesso non ce l'ho sotto mano. Comunque alla fine il tutto si riduce a provare che il più grande divisore comune è sempre divisibile per ogni altro dei comun divisori. Il tutto senza assumere la scomposizione in fattori primi.
P.S: bobus dimostra l'implicazione inversa
P.S: bobus dimostra l'implicazione inversa
Sì, certo, però la tua "richiesta" iniziale era l'implicazione inversa di questa ... cioè volevi provare che dato l'MCD alllora questo è divisibile per ogni divisore comune mentre bobus ha dimostrato che un numero (o meglio un divisore comune) che è divisibile per ogni divisore comune è il massimo dei divisori comuni ... non è una differenza da poco (anche se in questo caso, essendo una doppia implicazione, va bene lo stesso) ... IMHO ...
Cordialmente, Alex
Cordialmente, Alex
Io volevo provare che il più grande divisore comune risulta sempre essere divisibile per ogni altro comun divisore. Il che alla fine implica che è il MCD. Ma che è il MCD è la tesi, non l'ipotesi.
Ho capito il tuo obiettivo (e da un bel po' 
) però se rileggi i tuoi post vedrai che hai posto l'MCD come ipotesi ...
) però se rileggi i tuoi post vedrai che hai posto l'MCD come ipotesi ...
"keineahnung":
Si bobus esatto è quello l'esercizio. La tua dimostrazione è sensata però assume a priori l'esistenza del MCD, invece nel testo anche quella è dimostrata successivamente.
Il MCD è definito come quel numero che è sia comun divisore che divisibile a sua volta per ogni altro divisore comune.
Per ipotesi si sa che la prima delle due condizioni è verificata, quindi per dimostrare che d è il MCD bisogna dimostrare che vale anche la seconda, il tutto senza assumere a priori l'esistenza del MCD. Io la interpreto così.
Ma il testo dell'esercizio dice: "Dimostrare che \(\displaystyle d \) divisore comune di \(\displaystyle a \) e \(\displaystyle b \) (non entrambi nulli) è uguale a \(\displaystyle (a,b) \) se e solo se per ogni divisore comune \(\displaystyle c \) di \(\displaystyle a \) e \(\displaystyle b \) si ha che \(\displaystyle c \leq d \)".
Quindi secondo me si può far riferimento all'intero \(\displaystyle (a,b) \) come è stato definito in 4.26, senza preoccuparsi se esiste o meno.
Penso che lo scopo dell'esercizio sia dimostrare la doppia implicazione. Quella che va dalla proprietà di ordinamento alla proprietà di divisibilità è quella che chiedevi tu nel post iniziale e che ho dimostrato sopra.
Comunque alla fine il tutto si riduce a provare che il più grande divisore comune è sempre divisibile per ogni altro dei comun divisori. Il tutto senza assumere la scomposizione in fattori primi.
P.S: bobus dimostra l'implicazione inversa
Se rileggi la dimostrazione vedi che dimostra l'implicazione che va dalla proprietà di ordinamento a quella di divisibilità.
"axpgn":
Ho capito il tuo obiettivo (e da un bel po'
Non mi sembra sinceramente io ho solo parlato di divisor comune più grande non di MCD
"bobus":
Immagino la tua domanda si riferisca al "se" dell'esercizio 4.28, giusto?
Se è così, le ipotesi che abbiamo sono che \(\displaystyle d \) è un divisore comune di \(\displaystyle a \) e \(\displaystyle b \) e per ogni divisore comune \(\displaystyle c \) di \(\displaystyle a \) e \(\displaystyle b \) si ha che \(\displaystyle c \leq d \). Vogliamo dimostrare che \(\displaystyle d=(a,b) \).
Per ipotesi abbiamo che \(\displaystyle (a,b) \leq d \). Supponiamo per assurdo che \(\displaystyle (a,b) < d \), siccome per ipotesi \(\displaystyle d | (a,b) \), abbiamo che \(\displaystyle (a,b) = dk \) dove \(\displaystyle k \) è un intero maggiore o uguale a \(\displaystyle 1 \).
Quindi \(\displaystyle dk < d \), da cui \(\displaystyle k < 1 \), contraddizione. Perciò \(\displaystyle (a,b) = d \).
Bobus tu nella dimostrazione dici che come ipotesi il MCD è divisibile per d, a me invece sembra che l esercizio chieda di prendere il più grande tra tutti i divisori comuni e dimostrare che questo numero verifica le due condizioni con cui è definito il MCD, senza assumere altre ipotesi. Magari sbaglio, ma io lo interpreto così
Se la traccia dell'esercizio è questa:
allora si richiede implicitamente di assumere l'esistenza di \( \gcd (a,b) \) per due motivi:
1. altrimenti non avrebbe senso parlare di uguaglianza tra \( d \) e \( \gcd (a,b) \);
2. (laddove già il punto 1 dovrebbe essere sufficiente) si richiede di provare un doppia implicazione, su un verso della quale si parte proprio dal \( \gcd (a,b) \).
In altri termini l'esercizio può essere riformulato come segue.
Siano:
• \( a, b \in \mathbb{Z}\);
• \( S = \{ x \in \mathbb{Z} : x \mid a \land x \mid b \} \);
• \( d \in S \);
allora: \( d = \gcd (a,b) \iff \forall c \in S, c \le d \).
Ovvero si ha da provare che:
• se \( d = \gcd (a,b) \), allora \( \forall c \in S, c \le d \);
• se \( \forall c \in S, c \le d \), allora \( d = \gcd (a,b) \).
Ovviamente in tutto questo si deve dare per un attimo per scontato che esista \( \gcd (a,b) \) nella forma in cui è stato definito in precedenza. Nel momento in cui si da per scontato che esista \( \gcd (a,b) \) così come in precedenza definito, il fatto che \( d \mid \gcd(a,b) \) non è un'ipotesi aggiuntiva ma discende direttamente dalla definizione di \( \gcd (a,b) \): siccome \( d \in S \), allora \( d \mid a \land d \mid b\), quindi \( d \mid \gcd (a,b) \) per la seconda proprietà che interviene nella definizione.
"bobus":
Dimostrare che \(\displaystyle d \) divisore comune di \(\displaystyle a \) e \(\displaystyle b \) (non entrambi nulli) è uguale a \(\displaystyle (a,b) \) se e solo se per ogni divisore comune \(\displaystyle c \) di \(\displaystyle a \) e \(\displaystyle b \) si ha che \(\displaystyle c \leq d \)
allora si richiede implicitamente di assumere l'esistenza di \( \gcd (a,b) \) per due motivi:
1. altrimenti non avrebbe senso parlare di uguaglianza tra \( d \) e \( \gcd (a,b) \);
2. (laddove già il punto 1 dovrebbe essere sufficiente) si richiede di provare un doppia implicazione, su un verso della quale si parte proprio dal \( \gcd (a,b) \).
In altri termini l'esercizio può essere riformulato come segue.
Siano:
• \( a, b \in \mathbb{Z}\);
• \( S = \{ x \in \mathbb{Z} : x \mid a \land x \mid b \} \);
• \( d \in S \);
allora: \( d = \gcd (a,b) \iff \forall c \in S, c \le d \).
Ovvero si ha da provare che:
• se \( d = \gcd (a,b) \), allora \( \forall c \in S, c \le d \);
• se \( \forall c \in S, c \le d \), allora \( d = \gcd (a,b) \).
Ovviamente in tutto questo si deve dare per un attimo per scontato che esista \( \gcd (a,b) \) nella forma in cui è stato definito in precedenza. Nel momento in cui si da per scontato che esista \( \gcd (a,b) \) così come in precedenza definito, il fatto che \( d \mid \gcd(a,b) \) non è un'ipotesi aggiuntiva ma discende direttamente dalla definizione di \( \gcd (a,b) \): siccome \( d \in S \), allora \( d \mid a \land d \mid b\), quindi \( d \mid \gcd (a,b) \) per la seconda proprietà che interviene nella definizione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo